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.

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