On a related note, I have in general concerns about latency spikes due to rehashing. Is there a good, general, incremental rehashing scheme?
If you follow a Shalev/Shavit hash-ordered-lists scheme the rehash doesn't even need to move anything, and can be done with a straight memcpy, or in a separate thread. The link below is an implementation that was intended for Cassandra (so is simplified and append-only, but also a concurrent map - which could be relaxed). It has the nice property that it will "fix" the backing array on-demand, so straight-up copying the existing contents of the backing array into the new region of the backing array, once doubled, will set things up for a gradual transition.
Similarly, it's trivial for the backing array to instead grow incrementally, and for an extra level of indirection to prevent ever having to reallocate older regions (since their contents never changes on rehash).
https://github.com/belliottsmith/cassandra/blob/47d970ead690...
If you rehash based on something like "number of reprobes" then it's probably impossible to absolutely guarantee that a rehash cannot be triggered before a prior one begins, but the linked approach would permit growing the backing array discontiguously (assuming an extra level of indirection to the backing array). But this would obviously incur some extra overheads, and is not entirely dissimilar to hash-tries, which also avoid any costly global rehash.
I think the class-level comment in the code I linked is perhaps the best introduction to split-ordered lists I know of (not hash-ordered; they're sorted by the reverse bitstring of the hash), since they're not widely discussed and not immediately intuitive.
Paper link: http://people.csail.mit.edu/shanir/publications/Split-Ordere...
The idea is not super clever so I'm sure many people found & implemented it in papers and other languages, but I didn't find them. Will be grateful if someone points me to prior work.
Trees.
But the amortized O(1) lookup of hash tables is hard to beat.
edit: s/bass/beat/
On the other hand: the performance characteristics of trees are much easier to predict.
And in many cases a HT lookup isn't distinguishable from a tree lookup, at least if it's a dedicated application data structure, like some index or so.
I feel like HTs are very good for smaller structures (excellent example: dictionary/hashtable-based interpreters), but for larger data structures (e.g.: indices) ... not so much.
One option is to move a few elements over from the old hash table on each operation[0].
A second option is to use linear hashing[1] (different from linear probing). Linear hashing let's you increase the size of your hash table by one bucket at a time. The general idea is once your hash table is full, you allocate a new bucket (generally from a preallocated array) and move half of the elements from an old bucket to the new bucket. I know Postgres used to use linear hashing, but I'm not sure about the current state. I heard they started using Robin Hood hashing, but I haven't looked at whether that is unrelated to the code that uses linear hashing.