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.

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