The principle of "hopscotch hasing" is described, for example, here: https://en.wikipedia.org/wiki/Hopscotch_hashing https://en.wikipedia.org/wiki/Hopscotch_has

The principle of "hopscotch hasing" is described, for example, here: https://en.wikipedia.org/wiki/Hopscotch_hashing https://en.wikipedia.org/wiki/Hopscotch_hashing ---- An point often missed by people who need to/want to do hashing: In practice, with your real workloads, you can often make do with actually "giving up" on the hasing of some fraction of the elements, whose buckets, neighborhoods and such are already occupied - and instead put those aside for separate out-of-band handling. hash table implementations such as this one (or std::unordered_map and all the rest), absolutely _must_ succeed in inserting your values - and so must always allow for more collisions, resizing etc.