6 ms·

> Engineers irrationally avoid hash tables because of the worst-case O(n) search time. Not sure about other people here but I haven't heard any developers I wo

> Engineers irrationally avoid hash tables because of the worst-case O(n) search time. Not sure about other people here but I haven't heard any developers I work with avoid hash tables for reasons like this. I find most coders treat hash tables as black boxes that offer instant lookups. Also, I found from giving interviews most developers can't explain at a basic level how a hash table works as well as other fundamental data structures like linked lists.

jhdevos 10y ago
After interviewing many more and less experienced programmers (and asking most of them if they can explain a hash table - just for statistics!), I concur that most cannot. There were quite some people that thought trees were faster than hash tables though - mostly the ones that had some incling of what a hash table does, but didn't know the entire picture. At least in all those cases I had the pleasure of educating them a little bit :-)
- seanwilson 10y ago
  > After interviewing many more and less experienced programmers (and asking most of them if they can explain a hash table - just for statistics!), I concur that most cannot. I found this realisation pretty shocking myself. Several experienced Java developers told me they hadn't even heard the phrase "linked list" before when Java even has a class called LinkedList. :( I see threads on here all the time about how interviews are broken and you shouldn't be expected to be quizzed on data structures if you're an experienced programmer but I don't agree with that. If you claim to be an experienced programmer and can't explain roughly how a hash table or a linked list works you've obviously got big holes in your knowledge in the areas of optimisation and scalability.
  - vonmoltke 10y ago
    > If you claim to be an experienced programmer and can't explain roughly how a hash table or a linked list works you've obviously got big holes in your knowledge in the areas of optimisation and scalability. What is your definition of "roughly" and how do you think lack of that knowledge affects knowledge of optimization and scalability? I ask not because I necessarily disagree, but because your statement is very subjective. Also because I used to write large-scale real-time signal processing code that didn't use hash tables at all, so lack of knowledge there wouldn't have this effect on our code.
    - dkersten 10y ago
      > how do you think lack of that knowledge affects knowledge of optimization and scalability? I once wrote a log analysis python script. It took 2.5 hours to execute to completion. I then used Cython to compile it to C. It then took about 2 hours to run to completion. I then stepped back and thought about the data structures I was using. I replaced some lists that were being searched with dictionaries that could were keyed by what I was searching my lists for. Replaced a few other simple data structures. Now the script took, IIRC, 20 seconds to run to completion. Now, I don't think you necessarily need to know all of the internal details of how a data structure is implemented to know its performance characteristics or when to use (or not use) them. However, the point is that by understanding their performance characteristics, code can be optimized or made more scalable. Also, while something like a hash table might not be faster in actual real life terms (ie worse O() complexity can still be better wall clock; eg searching an array linearly can be faster than accessing a hash table since the array can be in cache and prefetched) when run on a single machine, big-O complexity can start mattering much more when you have a distributed workload or TB worth of data. (Although if you have a distributed workload, you have distributed systems problems to deal with too). Having said all of this, without going into specific implementation details, hash tables and linked lists are incredibly simple and I see no reason why anyone calling themselves a programmer would have trouble with these. I mean, I wouldn't expect you to be able to write a good hash function or anything, but explaining the basic concept shouldn't be too hard for most programmers. If someone is self-taught, then ok maybe they haven't ever needed to learn this. Its definitely possible, but I would at least hope they would know basic performance characteristics or at least some rules of thumb as to when to use what data structure. Hopefully based on logic and not just hearsay ;-)
      - seanwilson 10y ago
        > Having said all of this, without going into specific implementation details, hash tables and linked lists are incredibly simple and I see no reason why anyone calling themselves a programmer would have trouble with these. I mean, I wouldn't expect you to be able to write a good hash function or anything, but explaining the basic concept shouldn't be too hard for most programmers. If someone is self-taught, then ok maybe they haven't ever needed to learn this. Even if you're self-taught, if you've been programming for a while you should be able to read up on what linked lists and hash tables are in 15 minutes and virtually all interview preparation guides mention data structures. If you've not had the curiosity to do that then that's a bad sign.
  - emodendroket 10y ago
    To be fair, LinkedList is of very limited use. I can't think of a scenario I'd use it in beyond an LRU cache.
    - seanwilson 10y ago
      > To be fair, LinkedList is of very limited use. I can't think of a scenario I'd use it in beyond an LRU cache. It's more the point that not knowing they exist is a very strong indicator you haven't read even introductory text on algorithms and data structures. I barely use them either but when I'm thinking of solutions to problems they're a useful concept to know.
      - emodendroket 10y ago
        Yeah, agreed. They are extremely simple.
    - Annatar 10y ago
      A smartly designed doubly-linked list can be used for extremely fast deletion or insertion, as well as handling dynamic memory allocation for arbitrarily large data sets. Linked lists are the foundation of operating systems, especially UNIX and AmigaOS.
      - emodendroket 10y ago
        Yeah, OK, that is another good example. But nevertheless, there are a lot of programs you could be asked to write where using a linked list doesn't make any sense.
    - falcolas 10y ago
      If you're not familiar with intrusively linked lists, it's worth having a gander at. Learning and implementing a few of those gave me a lot more usecases for linked lists.
    - vonmoltke 10y ago
      I have used a "light" linked list (a linked list that contains just three pointers) to efficiently sort arrays with very large records in C.
  - Annatar 10y ago
    I see threads on here all the time about how interviews are broken and you shouldn't be expected to be quizzed on data structures if you're an experienced programmer Anyone who thinks that an experienced programmer shouldn't know data structures just isn't programmer material: someone who truly appreciates this profession will have had formal education in algorithms and data structures, and if they do not, they will make sure they learn it on their own. Otherwise - this is how we get bloated crapware. I just cannot up-vote your comment enough, if I could, I would up-vote it with my both hands and feet! I always think back to The Art of UNIX programming: Rule of Representation: Fold knowledge into data, so program logic can be stupid and robust. http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2878263 http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2878...
usrusr 10y ago
Engineers avoiding hash tables, yes, that's one myth. Still waiting for the other four promised in the headline. In the age of javascript everywhere I'd say that hash tables have pretty much won. I was curious about which corner of software technology the author was coming from where hash tables are routinely questioned (embedded C maybe?), but even the followup post does not quite explain it. ( https://hughewilliams.com/2013/06/03/reflecting-on-my-hash-table-post/ https://hughewilliams.com/2013/06/03/reflecting-on-my-hash-t... , also references a previous hn discussion)
- masklinn 10y ago
  > In the age of javascript everywhere I'd say that hash tables have pretty much won. All of Lua, PHP, Ruby and Python are hash tables flying around, and pretty much everything web is going to involve tons of hashtables whatever your language as HTTP headers, QS parameters and form-encoded data have arbitrary named fields.
  - usrusr 10y ago
    Makes me wonder if today's Lisps are actually "Hasps" in disguise. (unwritten rule of hn: don't post terrible puns like this before the majority of voting is over)
falcolas 10y ago
> Not sure about other people here but I haven't heard any developers I work with avoid hash tables for reasons like this. I've found there's a vast difference with many engineers between their willingness to use a structure called a "Hash Table" as compared to a Python/Swift "Dictionary", JavaScript "Object", or Go "Map". Yes, they're all hash tables underneath, but so few people actually ever make that connection consciously. Hash tables have a lot of baggage from our CS classes, and their O(n) is foremost on people's minds when thinking about them. Objects, on the other hand, are so ubiquitous and programmer friendly that you just use them without thinking that they are a hash table, and what that means.

jhdevos 10y ago

After interviewing many more and less experienced programmers (and asking most of them if they can explain a hash table - just for statistics!), I concur that most cannot. There were quite some people that thought trees were faster than hash tables though - mostly the ones that had some incling of what a hash table does, but didn't know the entire picture. At least in all those cases I had the pleasure of educating them a little bit :-)

seanwilson 10y ago
> After interviewing many more and less experienced programmers (and asking most of them if they can explain a hash table - just for statistics!), I concur that most cannot. I found this realisation pretty shocking myself. Several experienced Java developers told me they hadn't even heard the phrase "linked list" before when Java even has a class called LinkedList. :( I see threads on here all the time about how interviews are broken and you shouldn't be expected to be quizzed on data structures if you're an experienced programmer but I don't agree with that. If you claim to be an experienced programmer and can't explain roughly how a hash table or a linked list works you've obviously got big holes in your knowledge in the areas of optimisation and scalability.
- vonmoltke 10y ago
  > If you claim to be an experienced programmer and can't explain roughly how a hash table or a linked list works you've obviously got big holes in your knowledge in the areas of optimisation and scalability. What is your definition of "roughly" and how do you think lack of that knowledge affects knowledge of optimization and scalability? I ask not because I necessarily disagree, but because your statement is very subjective. Also because I used to write large-scale real-time signal processing code that didn't use hash tables at all, so lack of knowledge there wouldn't have this effect on our code.
  - dkersten 10y ago
    > how do you think lack of that knowledge affects knowledge of optimization and scalability? I once wrote a log analysis python script. It took 2.5 hours to execute to completion. I then used Cython to compile it to C. It then took about 2 hours to run to completion. I then stepped back and thought about the data structures I was using. I replaced some lists that were being searched with dictionaries that could were keyed by what I was searching my lists for. Replaced a few other simple data structures. Now the script took, IIRC, 20 seconds to run to completion. Now, I don't think you necessarily need to know all of the internal details of how a data structure is implemented to know its performance characteristics or when to use (or not use) them. However, the point is that by understanding their performance characteristics, code can be optimized or made more scalable. Also, while something like a hash table might not be faster in actual real life terms (ie worse O() complexity can still be better wall clock; eg searching an array linearly can be faster than accessing a hash table since the array can be in cache and prefetched) when run on a single machine, big-O complexity can start mattering much more when you have a distributed workload or TB worth of data. (Although if you have a distributed workload, you have distributed systems problems to deal with too). Having said all of this, without going into specific implementation details, hash tables and linked lists are incredibly simple and I see no reason why anyone calling themselves a programmer would have trouble with these. I mean, I wouldn't expect you to be able to write a good hash function or anything, but explaining the basic concept shouldn't be too hard for most programmers. If someone is self-taught, then ok maybe they haven't ever needed to learn this. Its definitely possible, but I would at least hope they would know basic performance characteristics or at least some rules of thumb as to when to use what data structure. Hopefully based on logic and not just hearsay ;-)
    - seanwilson 10y ago
      > Having said all of this, without going into specific implementation details, hash tables and linked lists are incredibly simple and I see no reason why anyone calling themselves a programmer would have trouble with these. I mean, I wouldn't expect you to be able to write a good hash function or anything, but explaining the basic concept shouldn't be too hard for most programmers. If someone is self-taught, then ok maybe they haven't ever needed to learn this. Even if you're self-taught, if you've been programming for a while you should be able to read up on what linked lists and hash tables are in 15 minutes and virtually all interview preparation guides mention data structures. If you've not had the curiosity to do that then that's a bad sign.
- emodendroket 10y ago
  To be fair, LinkedList is of very limited use. I can't think of a scenario I'd use it in beyond an LRU cache.
  - seanwilson 10y ago
    > To be fair, LinkedList is of very limited use. I can't think of a scenario I'd use it in beyond an LRU cache. It's more the point that not knowing they exist is a very strong indicator you haven't read even introductory text on algorithms and data structures. I barely use them either but when I'm thinking of solutions to problems they're a useful concept to know.
    - emodendroket 10y ago
      Yeah, agreed. They are extremely simple.
  - Annatar 10y ago
    A smartly designed doubly-linked list can be used for extremely fast deletion or insertion, as well as handling dynamic memory allocation for arbitrarily large data sets. Linked lists are the foundation of operating systems, especially UNIX and AmigaOS.
    - emodendroket 10y ago
      Yeah, OK, that is another good example. But nevertheless, there are a lot of programs you could be asked to write where using a linked list doesn't make any sense.
  - falcolas 10y ago
    If you're not familiar with intrusively linked lists, it's worth having a gander at. Learning and implementing a few of those gave me a lot more usecases for linked lists.
  - vonmoltke 10y ago
    I have used a "light" linked list (a linked list that contains just three pointers) to efficiently sort arrays with very large records in C.
- Annatar 10y ago
  I see threads on here all the time about how interviews are broken and you shouldn't be expected to be quizzed on data structures if you're an experienced programmer Anyone who thinks that an experienced programmer shouldn't know data structures just isn't programmer material: someone who truly appreciates this profession will have had formal education in algorithms and data structures, and if they do not, they will make sure they learn it on their own. Otherwise - this is how we get bloated crapware. I just cannot up-vote your comment enough, if I could, I would up-vote it with my both hands and feet! I always think back to The Art of UNIX programming: Rule of Representation: Fold knowledge into data, so program logic can be stupid and robust. http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2878263 http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2878...

usrusr 10y ago

Engineers avoiding hash tables, yes, that's one myth. Still waiting for the other four promised in the headline. In the age of javascript everywhere I'd say that hash tables have pretty much won. I was curious about which corner of software technology the author was coming from where hash tables are routinely questioned (embedded C maybe?), but even the followup post does not quite explain it. ( https://hughewilliams.com/2013/06/03/reflecting-on-my-hash-table-post/ https://hughewilliams.com/2013/06/03/reflecting-on-my-hash-t... , also references a previous hn discussion)

masklinn 10y ago
> In the age of javascript everywhere I'd say that hash tables have pretty much won. All of Lua, PHP, Ruby and Python are hash tables flying around, and pretty much everything web is going to involve tons of hashtables whatever your language as HTTP headers, QS parameters and form-encoded data have arbitrary named fields.
- usrusr 10y ago
  Makes me wonder if today's Lisps are actually "Hasps" in disguise. (unwritten rule of hn: don't post terrible puns like this before the majority of voting is over)

falcolas 10y ago

> Not sure about other people here but I haven't heard any developers I work with avoid hash tables for reasons like this. I've found there's a vast difference with many engineers between their willingness to use a structure called a "Hash Table" as compared to a Python/Swift "Dictionary", JavaScript "Object", or Go "Map". Yes, they're all hash tables underneath, but so few people actually ever make that connection consciously. Hash tables have a lot of baggage from our CS classes, and their O(n) is foremost on people's minds when thinking about them. Objects, on the other hand, are so ubiquitous and programmer friendly that you just use them without thinking that they are a hash table, and what that means.