3 ms·
The hash table is still doing a string compare per bucket. The best technique I have seen is to have an open addressing hash table whose keys are 64 bit hashes
by liontwist 2y ago
The hash table is still doing a string compare per bucket.
The best technique I have seen is to have an open addressing hash table whose keys are 64 bit hashes and values are pointers.
Then you layer on top of that to make a string dictionary. The value of the hash table is a linked list chain of key value pairs where the key is a string.
In the vast majority of cases you never touch the chain. Only when two keys have identical 64 bit hashes (not bucket indices) do you need to disambiguate with string equality.
This design is much faster and can be easily reconfigured for key types which are not strings, with no changes to the underlying hash table.
- acuozzo 2y agoAFAICT, what you write here is more-or-less the standard approach to open addressed hash tables since they were invented. I'm not sure why Chris overlooked this in writing his article. The string comparison is supposed to only happen when the hash values are equal.
- liontwist 2y agoIn school (and Wikipedia?) they told me chaining is just moving elements with the same bucket index into a linked list. Sometimes textbooks focus too much on the abstract idea, and throw out what they think are unnecessary details, when they are actually important contributions by practitioners.
- twic 2y agoWhy chain rather than reprobing on full key collisions?
- liontwist 2y agoThat’s a good question. Since we want the key table to be packed 64 bits, then that means the reprobing would scan the values array. In this implementation the values type is a pointer, so you still have to deref those and you get no perf benefits. In addition you can compose the functionality of the more complex tables on the simple ones. You need custom get/set hash table probing for the key type.