13 ms·

Myths about Hash Tables

86 points by ptr 10y ago

josefx 10y ago
The worst case was once used to attack Java based servers, using colliding post parameters I think. Since then the Java HashMap sorts colliding entries if the entries implement Comparable.
- masklinn 10y ago
  > The worst case was once used to attack Java based servers The worst case was revealed able to efficiently DOS pretty much any hashtable-based stack back in 2011[0] (practical attacks on real-world implementations, not theoretical work), following which most stacks added hash randomisation during 2012. [0] https://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf https://events.ccc.de/congress/2011/Fahrplan/attachments/200...
- bhaak 10y ago
  Needs a (2012) in the title. The hash collisions you mentioned probably got fixed after or because of these CCC congress talks: https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.... https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.html https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.... The article talks about peculiar myths that I haven't heard before. And the first one "the worst case is terrible" is not even a myth if you're hashing function isn't well designed and you have a malicious data provider.
- danbruc 10y ago
  But that is of course true for all algorithms without uniform performance, another famous example being sorting with quicksort which on average takes O(n x log(n)) time but can become O(n²) in the worst case. Or zip bombs making you decompress a few kilobytes of data into gigabytes. If a user can control a relevant fraction or important piece of the data you are processing, then you always have to be careful not to expose yourselves to algorithmic complexity attacks.
- jkot 10y ago
  Also String.hashCode is broken, it generates too many collisions. It can not be fixed for historic reasons.
  - arethuza 10y ago
    Wasn't an early version really broken - where it only looked at the first N characters of a string when hashing it? Where N was actually pretty low.
    - jkot 10y ago
      Perhaps, but it made sense with 16MB RAM and 486 CPU. Current implementation uses 31 multiplier which is useless over 1M entries. This problem is also in Arrays.hash*() and many other places.
- espadrine 10y ago
  The answer to that has always been universal hash functions. You have a family of hash functions, one of which is picked randomly. In the family, each hash function is such that Pr(collision) ≤ Pr(randomly picking that hash function). That way, for a sufficiently large family, it is virtually impossible to hit its worst case.
  - rurban 10y ago
    No, it's not. With enough data leaking, like ordering and timings attacks are computable. Only a proper collision resolution method can prevent from DoS attacks. The blog post doesn't even know about modern hash tables, not chasing ptrs in a linked list, which is not recommended where ptrs chasing is 50x slower than adjacent entries (cpu's of the last 15 years). But for newbies it's at least a beginning.
seanwilson 10y ago
> 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.
hueving 10y ago
He mentioned his own home grown hash with the bit shifts. How does it compare to common ones that use an AES instruction if the crypto chip is available?
- rurban 10y ago
  Poor. See https://github.com/rurban/smhasher https://github.com/rurban/smhasher
acidbaseextract 10y ago
A whole post about hash tables and he doesn't mention the real reason trees are better than hash tables: lower variance! > Hash tables become full, and bad things happen The bad thing is not a crazy long probe or even rehashing to enlarge the table—it's that some random individual insert is stuck eating the entire cost of rebuilding the table. For many applications, I'm happy with a slightly higher cost per operation in return for predictable performance. > Hash functions are slow Great, another unmentioned footgun - hash functions are hard. For example, the hash function he provides doesn't use a prime number of buckets. Oops, non-uniform input data in combination with unlucky bucket counts can generate high numbers of collisions. Writing a comparison function to put your data in a tree is pretty stupidproof!
- mojuba 10y ago
  For similar reasons I prefer reference counting over (tracing) garbage collection, especially in near-realtime applications, such as audio.
- whack 10y ago
  There are resizing algorithms out there which specifically avoid the single-insertion-spike that you're worried about. http://stackoverflow.com/a/2200345 http://stackoverflow.com/a/2200345 If you're working with small data sizes, the difference between O(1) and O(lgN) isn't that big a deal, so you can use whatever you want. But once you start working with larger datasets containing millions of elements, and the only thing you care about is insertions and exact-match-lookups, it's hard to justify using a tree over a hash map.
personjerry 10y ago
This seems like Data Structures 101
saw-lau 10y ago
Interesting that the author offers the chained hash table as an alternative implementation - that was always how I was taught they worked back in school. (1986?)
- douche 10y ago
  Same here, graduated in the 2000s. The way hash tables are described in the opening section sounds really naive, and I would hope that real implementations aren't using that method.
  - emodendroket 10y ago
    AFAIK most real-world dictionary classes use linear probing.
    - gpderetta 10y ago
      std::unordered_map and friends use chaining (and they suffer from it).
  - mason55 10y ago
    Go find the post on the history of dict in Python from the other day to see how they move away from chaining.
- emodendroket 10y ago
  That's because that implementation is more obvious but has worse real-world performance than linear probing.
Udo 10y ago
While the article is a bit polemic, I really wish more people knew how hash tables work under the hood. When I was looking for a job, I flunked out of one interview where I got into an argument with an interviewer about the runtime properties of hash tables - more specifically: the interviewer was adamant their access time was always O(1), wanted me to admit my "mistake" and move on, but I just couldn't ;) It was one of those rare cases where they give you feedback on why you're not being hired, too. The lady on the phone said my "technical knowledge" was not up to par with what they needed for the position. Yeah, I'm still salty about that.
- arethuza 10y ago
  Sounds to me more like the interviewer/company flunked you're test rather than you flunking - you might have dodged a bullet there.
  - Udo 10y ago
    I wouldn't have worked for the interviewer, it's often just a gatekeeper you need to overcome. Also, when you don't know how to make rent next month and the company seems pretty cool (apart from that person), it's hard to see at the time how you dodged any bullets...
    - arethuza 10y ago
      If someone reacts badly when you know more than they do then that's not a great bit of behaviour, if a company chooses such a person as an interviewer then that's a bit of a red flag to me - an interview should be as much about trying to present a positive image of the company as much as testing the interviewer. Sorry to hear about the rent situation - I take that worked out OK eventually?
      - Udo 10y ago
        > if a company chooses such a person as an interviewer then that's a bit of a red flag to me I think the basic corporate rules of signalling competence apply here. Assuming that person was both technologically and socially incompetent (which might be too harsh of a judgement), some people still have a way of getting promoted into valuable positions by appearing to do a great job. > Sorry to hear about the rent situation - I take that worked out OK eventually? Thankfully that was some years back, I'm doing okay today :)
krylon 10y ago
One interesting alternative to hash tables that appears to get too little love is the Judy tree: https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array They are not quite as versatile, I think, but for simple cases where your keys are strings or ints, they work just as well and are quite fast, too. The API is very simple, too. I don't do much programming in C these days (pretty much none at all), but I used Judy in one toy project and have fond memories of it.
- stuxnet79 10y ago
  Gotta love HN. I'm always learning new stuff. Thanks for posting this. The "Judy Shop Manual" (http://judy.sourceforge.net/application/shop_interm.pdf http://judy.sourceforge.net/application/shop_interm.pdf) looks very complicated so I don't know if I should take the time to fully understand how they work, especially if they are not as versatile as hash tables.
  - krylon 10y ago
    Judy's author appears to have poured bathtubs full of cleverness into his brainchild to make it fast at the cost of implementation complexity. As long as you don't look behind the curtain, it's genius - an API so simple a child could use it, and it's so fast... But try to understand how it works, and your brain melts. Well, mine, at least. Then again, I suspect the same can be said of what used to be called the STL, or Boost. In a library that is meant to be used by lots of other projects, the trade-off is legitimate.
- matheweis 10y ago
  Neat! I developed something similar back in college in JAVA - it was a ternary radix tree, and wow was that thing fast... something like only about 10% slower than HashMap for storing the entire English dictionary and looking up an arbitrary string a million times. There were all sorts of other interesting advantages relative to hash tables since I kept it sorted... you could retrieve an element and then find five adjacent elements. Handy for something like a dictionary app etc.
Annatar 10y ago
Hash arrays are great; I use them all the time in AWK. All searches using hash indexed arrays in AWK are O(1). I believe that the biggest problem around using hashes as indices entails people wrapping their head around the concept that the array index is a string (for all intents and purposes), rather than a number of a field in an array (or an address of a region in memory, which it eventually is anyway, once it runs). For example, I used entire lines of text as the hash for an array. My colleague who I was showing this technique to was completely dumbfounded as to how that worked. Why was I only storing the value "1" into Array["ORA-1234: blablabla"]? if(Array[$0] != 1) { # # This record is different, so print the entire record. # print; } "How is that used to filter out lines which are identical the ones we have in the canonical file?" He seemed completely flabbergasted. He just couldn't wrap his head around this concept, and ended up re-implementing the entire thing using several lines of grep -v, sed, and if [ ...] then. I think there were even several temporary files in the game, whereas the hash array technique in AWK loaded both the canonical file and the input from stdin into memory, rather than using intermediate files.
emodendroket 10y ago
I'm all for learning for hash tables work, but is avoiding them really widespread? Especially in dynamic languages I feel like dynamic arrays and hash tables are like 90% of the data structures used.
- falcolas 10y ago
  No, dynamic languages use Maps and Dictionaries and Objects and Containers and... Sure, they're all hash tables under the hood, but if you go up to an average JavaScript programmer and ask them the difference between a Hash Table and an Object, I'm sure you'd get a surprising (to you) answer.
  - emodendroket 10y ago
    I mean, not even under the hood. Those are just different names for the same thing.
    - masklinn 10y ago
      Due to the way JS objects are used, modern runtime will generally try to use structures for them (e.g. "hidden classes" in V8/Chrome) rather than "general-purpose" hashmaps. Likewise JS arrays incidentally. They will often need to deoptimise back to general-purpose hashmaps, but they'll try pretty hard not to.
      - emodendroket 10y ago
        Oh. That's neat.
        masklinn 10y ago
        Yep. V8's JIT will also try to specialise functions based on that so if you always pass the same type (where type = hidden class), a limited number of types or "anything goes". Or at least it did a few years back.
      - 10y ago
stefs 10y ago
potential offtopic question here: i always wondered about multi-layered hashtables, i.e. instead of a linked list for resolving collisions use a second hashtable with a different hash function (and then maybe a linked list on the 3rd level). i guess this might bring some potential improvements in case of a hashtable with too many collisions but a prohibitively expensive overhead in all other cases. i.e. it might alleviate a hashtable that was already broken.
- rurban 10y ago
  This is a bad idea, since double hashing with open addressing has the same benefits but is much faster. The indices are already in the cache and there's need for an additional hash table setup overhead. Usually you go for a variant of robin-hood, cuckoo or even quadratic hashing, with the same benefits but vastly better performance. (all open addressing schemes). And if the collision rate ("load factor"/"fill rate") is too high for your use case, you go for lower load factors, down from 90% to 50%. It's still much faster than using a complete separate 2nd data structure. And if you need something better than a hash table, (pointers, fixed size keys, ordered, ...) you usually go for patricia/crit-bit trees. One popular database tried a RB-tree as second data structure once (forgot the name and link. starts with R but not redis). Also see http://programmers.stackexchange.com/a/281785/27031 http://programmers.stackexchange.com/a/281785/27031, DMDScript used that also.
stefs 10y ago
i think the article omits one interesting point - cache coherence. afaik this is the one reason otherwise inefficient data structures might result in better real world performance for small data sets.
- marcosdumay 10y ago
  Well, asymptotic analysis is not very useful for small data sets.
greg7mdp 10y ago
If you are interested in hash tables, check out my improved version of Google's already excellent sparsehash at https://github.com/greg7mdp/sparsepp https://github.com/greg7mdp/sparsepp. Excellent performance, very low memory usage, grows as needed of course.

86 points by ptr 10y ago

The worst case was once used to attack Java based servers, using colliding post parameters I think. Since then the Java HashMap sorts colliding entries if the entries implement Comparable.

masklinn 10y ago
> The worst case was once used to attack Java based servers The worst case was revealed able to efficiently DOS pretty much any hashtable-based stack back in 2011[0] (practical attacks on real-world implementations, not theoretical work), following which most stacks added hash randomisation during 2012. [0] https://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf https://events.ccc.de/congress/2011/Fahrplan/attachments/200...
bhaak 10y ago
Needs a (2012) in the title. The hash collisions you mentioned probably got fixed after or because of these CCC congress talks: https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.... https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.html https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.... The article talks about peculiar myths that I haven't heard before. And the first one "the worst case is terrible" is not even a myth if you're hashing function isn't well designed and you have a malicious data provider.
danbruc 10y ago
But that is of course true for all algorithms without uniform performance, another famous example being sorting with quicksort which on average takes O(n x log(n)) time but can become O(n²) in the worst case. Or zip bombs making you decompress a few kilobytes of data into gigabytes. If a user can control a relevant fraction or important piece of the data you are processing, then you always have to be careful not to expose yourselves to algorithmic complexity attacks.
jkot 10y ago
Also String.hashCode is broken, it generates too many collisions. It can not be fixed for historic reasons.
- arethuza 10y ago
  Wasn't an early version really broken - where it only looked at the first N characters of a string when hashing it? Where N was actually pretty low.
  - jkot 10y ago
    Perhaps, but it made sense with 16MB RAM and 486 CPU. Current implementation uses 31 multiplier which is useless over 1M entries. This problem is also in Arrays.hash*() and many other places.
espadrine 10y ago
The answer to that has always been universal hash functions. You have a family of hash functions, one of which is picked randomly. In the family, each hash function is such that Pr(collision) ≤ Pr(randomly picking that hash function). That way, for a sufficiently large family, it is virtually impossible to hit its worst case.
- rurban 10y ago
  No, it's not. With enough data leaking, like ordering and timings attacks are computable. Only a proper collision resolution method can prevent from DoS attacks. The blog post doesn't even know about modern hash tables, not chasing ptrs in a linked list, which is not recommended where ptrs chasing is 50x slower than adjacent entries (cpu's of the last 15 years). But for newbies it's at least a beginning.

seanwilson 10y ago

> 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.

hueving 10y ago

He mentioned his own home grown hash with the bit shifts. How does it compare to common ones that use an AES instruction if the crypto chip is available?

rurban 10y ago
Poor. See https://github.com/rurban/smhasher https://github.com/rurban/smhasher

acidbaseextract 10y ago

A whole post about hash tables and he doesn't mention the real reason trees are better than hash tables: lower variance! > Hash tables become full, and bad things happen The bad thing is not a crazy long probe or even rehashing to enlarge the table—it's that some random individual insert is stuck eating the entire cost of rebuilding the table. For many applications, I'm happy with a slightly higher cost per operation in return for predictable performance. > Hash functions are slow Great, another unmentioned footgun - hash functions are hard. For example, the hash function he provides doesn't use a prime number of buckets. Oops, non-uniform input data in combination with unlucky bucket counts can generate high numbers of collisions. Writing a comparison function to put your data in a tree is pretty stupidproof!

mojuba 10y ago
For similar reasons I prefer reference counting over (tracing) garbage collection, especially in near-realtime applications, such as audio.
whack 10y ago
There are resizing algorithms out there which specifically avoid the single-insertion-spike that you're worried about. http://stackoverflow.com/a/2200345 http://stackoverflow.com/a/2200345 If you're working with small data sizes, the difference between O(1) and O(lgN) isn't that big a deal, so you can use whatever you want. But once you start working with larger datasets containing millions of elements, and the only thing you care about is insertions and exact-match-lookups, it's hard to justify using a tree over a hash map.

personjerry 10y ago

This seems like Data Structures 101

saw-lau 10y ago

Interesting that the author offers the chained hash table as an alternative implementation - that was always how I was taught they worked back in school. (1986?)

douche 10y ago
Same here, graduated in the 2000s. The way hash tables are described in the opening section sounds really naive, and I would hope that real implementations aren't using that method.
- emodendroket 10y ago
  AFAIK most real-world dictionary classes use linear probing.
  - gpderetta 10y ago
    std::unordered_map and friends use chaining (and they suffer from it).
- mason55 10y ago
  Go find the post on the history of dict in Python from the other day to see how they move away from chaining.
emodendroket 10y ago
That's because that implementation is more obvious but has worse real-world performance than linear probing.

Udo 10y ago

While the article is a bit polemic, I really wish more people knew how hash tables work under the hood. When I was looking for a job, I flunked out of one interview where I got into an argument with an interviewer about the runtime properties of hash tables - more specifically: the interviewer was adamant their access time was always O(1), wanted me to admit my "mistake" and move on, but I just couldn't ;) It was one of those rare cases where they give you feedback on why you're not being hired, too. The lady on the phone said my "technical knowledge" was not up to par with what they needed for the position. Yeah, I'm still salty about that.

arethuza 10y ago
Sounds to me more like the interviewer/company flunked you're test rather than you flunking - you might have dodged a bullet there.
- Udo 10y ago
  I wouldn't have worked for the interviewer, it's often just a gatekeeper you need to overcome. Also, when you don't know how to make rent next month and the company seems pretty cool (apart from that person), it's hard to see at the time how you dodged any bullets...
  - arethuza 10y ago
    If someone reacts badly when you know more than they do then that's not a great bit of behaviour, if a company chooses such a person as an interviewer then that's a bit of a red flag to me - an interview should be as much about trying to present a positive image of the company as much as testing the interviewer. Sorry to hear about the rent situation - I take that worked out OK eventually?
    - Udo 10y ago
      > if a company chooses such a person as an interviewer then that's a bit of a red flag to me I think the basic corporate rules of signalling competence apply here. Assuming that person was both technologically and socially incompetent (which might be too harsh of a judgement), some people still have a way of getting promoted into valuable positions by appearing to do a great job. > Sorry to hear about the rent situation - I take that worked out OK eventually? Thankfully that was some years back, I'm doing okay today :)

krylon 10y ago

One interesting alternative to hash tables that appears to get too little love is the Judy tree: https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array They are not quite as versatile, I think, but for simple cases where your keys are strings or ints, they work just as well and are quite fast, too. The API is very simple, too. I don't do much programming in C these days (pretty much none at all), but I used Judy in one toy project and have fond memories of it.

stuxnet79 10y ago
Gotta love HN. I'm always learning new stuff. Thanks for posting this. The "Judy Shop Manual" (http://judy.sourceforge.net/application/shop_interm.pdf http://judy.sourceforge.net/application/shop_interm.pdf) looks very complicated so I don't know if I should take the time to fully understand how they work, especially if they are not as versatile as hash tables.
- krylon 10y ago
  Judy's author appears to have poured bathtubs full of cleverness into his brainchild to make it fast at the cost of implementation complexity. As long as you don't look behind the curtain, it's genius - an API so simple a child could use it, and it's so fast... But try to understand how it works, and your brain melts. Well, mine, at least. Then again, I suspect the same can be said of what used to be called the STL, or Boost. In a library that is meant to be used by lots of other projects, the trade-off is legitimate.
matheweis 10y ago
Neat! I developed something similar back in college in JAVA - it was a ternary radix tree, and wow was that thing fast... something like only about 10% slower than HashMap for storing the entire English dictionary and looking up an arbitrary string a million times. There were all sorts of other interesting advantages relative to hash tables since I kept it sorted... you could retrieve an element and then find five adjacent elements. Handy for something like a dictionary app etc.

Annatar 10y ago

Hash arrays are great; I use them all the time in AWK. All searches using hash indexed arrays in AWK are O(1). I believe that the biggest problem around using hashes as indices entails people wrapping their head around the concept that the array index is a string (for all intents and purposes), rather than a number of a field in an array (or an address of a region in memory, which it eventually is anyway, once it runs). For example, I used entire lines of text as the hash for an array. My colleague who I was showing this technique to was completely dumbfounded as to how that worked. Why was I only storing the value "1" into Array["ORA-1234: blablabla"]? if(Array[$0] != 1) { # # This record is different, so print the entire record. # print; } "How is that used to filter out lines which are identical the ones we have in the canonical file?" He seemed completely flabbergasted. He just couldn't wrap his head around this concept, and ended up re-implementing the entire thing using several lines of grep -v, sed, and if [ ...] then. I think there were even several temporary files in the game, whereas the hash array technique in AWK loaded both the canonical file and the input from stdin into memory, rather than using intermediate files.

emodendroket 10y ago

I'm all for learning for hash tables work, but is avoiding them really widespread? Especially in dynamic languages I feel like dynamic arrays and hash tables are like 90% of the data structures used.

falcolas 10y ago
No, dynamic languages use Maps and Dictionaries and Objects and Containers and... Sure, they're all hash tables under the hood, but if you go up to an average JavaScript programmer and ask them the difference between a Hash Table and an Object, I'm sure you'd get a surprising (to you) answer.
- emodendroket 10y ago
  I mean, not even under the hood. Those are just different names for the same thing.
  - masklinn 10y ago
    Due to the way JS objects are used, modern runtime will generally try to use structures for them (e.g. "hidden classes" in V8/Chrome) rather than "general-purpose" hashmaps. Likewise JS arrays incidentally. They will often need to deoptimise back to general-purpose hashmaps, but they'll try pretty hard not to.
    - emodendroket 10y ago
      Oh. That's neat.
      - masklinn 10y ago
        Yep. V8's JIT will also try to specialise functions based on that so if you always pass the same type (where type = hidden class), a limited number of types or "anything goes". Or at least it did a few years back.
    - 10y ago

stefs 10y ago

potential offtopic question here: i always wondered about multi-layered hashtables, i.e. instead of a linked list for resolving collisions use a second hashtable with a different hash function (and then maybe a linked list on the 3rd level). i guess this might bring some potential improvements in case of a hashtable with too many collisions but a prohibitively expensive overhead in all other cases. i.e. it might alleviate a hashtable that was already broken.

rurban 10y ago
This is a bad idea, since double hashing with open addressing has the same benefits but is much faster. The indices are already in the cache and there's need for an additional hash table setup overhead. Usually you go for a variant of robin-hood, cuckoo or even quadratic hashing, with the same benefits but vastly better performance. (all open addressing schemes). And if the collision rate ("load factor"/"fill rate") is too high for your use case, you go for lower load factors, down from 90% to 50%. It's still much faster than using a complete separate 2nd data structure. And if you need something better than a hash table, (pointers, fixed size keys, ordered, ...) you usually go for patricia/crit-bit trees. One popular database tried a RB-tree as second data structure once (forgot the name and link. starts with R but not redis). Also see http://programmers.stackexchange.com/a/281785/27031 http://programmers.stackexchange.com/a/281785/27031, DMDScript used that also.

stefs 10y ago

i think the article omits one interesting point - cache coherence. afaik this is the one reason otherwise inefficient data structures might result in better real world performance for small data sets.

marcosdumay 10y ago
Well, asymptotic analysis is not very useful for small data sets.

greg7mdp 10y ago

If you are interested in hash tables, check out my improved version of Google's already excellent sparsehash at https://github.com/greg7mdp/sparsepp https://github.com/greg7mdp/sparsepp. Excellent performance, very low memory usage, grows as needed of course.