Full comment
In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible) Oh, I see, right. If determining the home bucket is trivial, then the back-shifting method is great. The issue is just that it’s not as much of a general-purpose solution as it may initially seem. In the bad cases, it's really bad. With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate. I’ve seen the 90% claim made several times in literature on Robin Hood hash tables. In my experience, the claim is a bit exaggerated, although I suppose it depends on what our idea of “good performance” is. See these benchmarks, which again go up to a maximum load factor of 0.95 (although boost and Absl forcibly grow/rehash at 0.85-0.9): link Tsl, Martinus, and CC are all Robin Hood tables ( link , link , and link , respectively). Absl (from Google) and Boost are well-known C++ SIMD-based hash tables. Khash ( link ) is, I think, an ordinary open-addressing table using quadratic probing. Fastmap is a new, yet-to-be-published design that is fundamentally similar to bytell ( this video ) but also incorporates some aspects of the aforementioned SIMD maps (in particular, it stores a 4-bit fragment of the hash code to avoid most false key comparisons). As you can see, all the Robin Hood maps spike upwards dramatically as the load factor gets high,
