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.