Hash Tables are Slow

When accessing neiboring keys, hash tables are very slow, unless they fit into cache. Cache miss has like 300 cycles, which is a huge multiplier on top of O(1). I.e. if you iterate over a sorted list of string keys, then a binary tree will beat hashtable any day. And a tree also allows retrieving entire neighborhood, which is useful for say error correction or auto-completion.

No; hash tables are fast.

A red-black tree costs a cache miss for each level queried, which is proportional to log2 of its number of elements. Worse, if a red-black tree's nodes are already in the cache, the control-to-data dependency which its "compare key, pick side" loop introduces puts it in the far red. The only time when trees are faster than hashes is if the querying algorithms benefit from visiting each key in order, or in reverse order.

However, rebuilding hash tables is very very slow. Red-black trees work better for low-latency applications where there's cycles left spare in each frame.

>>2

hash tables are fast.

Only if your access entries randomly. But if you use hash table for something like variables in a scripting language, the access pattern is not random, since variables are clustered by scope. I.e. you have ht.get("scope0_var0") + ht.get("scope0_var1") Good hash function will likely place these vars in different buckets, while bad hash function will make hash table useless.

Hash browns, grits, bacon, pancakes, and toast!!!!!

>>3
Look at this clown who only knows chaining as a method for resolving hash clash.

what the fuck is this thread about

pls eli5

>>5
Perfect hashing doesn't exist.

>>7
Hashing doesn't have to be perfect, just good enough.

>>8
but is good enough good enough?

>>1-2
Why aren't you using B+Trees instead? They are g-d's chosen data structure.

>>7
Wrong https://en.wikipedia.org/wiki/Perfect_hash_function