Moreover, this kind of optimization only makes sense if (1) latency, not throughput, is your bottleneck or (2) if you're really concerned about parallel accesses.
A reasonable default in general is to use a hash table + mutex until that is your bottleneck. (I've yet to encounter a scenario where switching from a hash map would provide significant gains in performance-relevant code)
Disclosure: I work at Google and use the fancy hash map discussed by Matt. I didn't work on it, though.
Note that there exist hash table implementations which support incremental resizing.
I do agree, though, that it's a leap to go from "hash tables with this property are inappropriate under these constraints" to "hash tables with this property should not be considered further", precisely because there is such a broad spectrum of data structure requirements across the industry.
Rather, there exist hash table algorithms that support incremental resizing.
http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/cours...
This is important in environments where you have or do not want to use malloc/free. E.g. in embedded systems, exactly where some properties like worst case time behaviour is important and, therefore, radix trees seem like an option: they still might not be.
Well, but hash tables are not an option either in these situations, so good old binary search trees win (red-black, avl, 2-4, whatever).
That said, I can see two counter-arguments:
1. Rehashing can be avoided if the table size is known in advance. 2. Rehashing is immaterial if the data structure is write-once, read-many.
In those cases, we might reasonably expect a hash table to perform better.
With an open addressing implementation (Google's dense_hash_map, for example) this is only true if you rarely or never need to remove items from the map.
Examples from my own small library (http://25thandclement.com/~william/projects/phf.html), using 1 million random integers:
80% load -> 0.47s
85% load -> 0.56s
90% load -> 0.74s
95% load -> 1.10s
98% load -> 1.35s
99% load -> 1.68s
That said, 90% of the time I just use a simple red-black tree--a so-called intrusive implementation. It makes memory management much easier in C, and rare is the situation where a hash table (let alone a perfect hash table) can make a real difference relative to focusing on all the other inefficiencies.
https://en.wikipedia.org/wiki/Radix_tree looks like a funky structure for _very_ specific work loads.
In the worst case, the cache behaviour of a radix tree could be awful, if each node lives in a different cache-line, no?
I imagine this problem can be ameliorated with a custom allocator, though.
Been a while since I've studied hash-maps in depth, but with a good hash function, that wouldn't be a big worry, would it?
In some scenarios, radix trees can overcome that with better space efficiency (i.e. implicit key storage), but I think it's fair to say that there are many scenarios (if not most!) where hash tables outperform radix trees.
Of course, that all hinges on how you measure performance. As Salvatore pointed out, if you're looking to minimize variance, hash tables might not be suitable due to their growth characteristics. Radix trees also give you efficient sorting and range scans out of the box, and are a viable immutable persistent data structure as well. If none of those are meaningful to your use cases, then hash tables could certainly be a better fit.
How could we support deletion of nodes?
Conventionally, a free list would be used, though admittedly that sacrifices locality which was one of the original motivating factors. To the extent that deletion is a significant component of the workload, then yeah, this doesn't help.
Radix trees never rotate, right? Can that be leveraged to help with locality?
The downside of radix trees is the space of algorithm designs is pretty exotic, especially high-performance implementations. It is much easier to write a good hash table implementation than a good radix tree implementation.
{ i * "a" : i = 1 to n }