This uses a pretty nice idea to rehash with a different hash whenever
the info byte would cause an overflow, and also improves hash quality
when a bad hash is used.
The murmur finalizer is split up into 2 parts, the final part (one
multiplication and one xor&shift) is always done, regardless of the
hash used. That way the robin_hood hash is murmur's fmix, and all other
hashes have an addition mixer to improve its quality.
The additional mixer uses a member variable for the multiplication
constant. When an overflow is encountered, that constant is changed,
thus the rehash will spread the elements completely differently.
Rehashing is tried multiple times (up to 256 times), so we won't get
an endless loop if this rehashing still does not work.
This uses a pretty nice idea to rehash with a different hash whenever the info byte would cause an overflow, and also improves hash quality when a bad hash is used.
The murmur finalizer is split up into 2 parts, the final part (one multiplication and one xor&shift) is always done, regardless of the hash used. That way the robin_hood hash is murmur's fmix, and all other hashes have an addition mixer to improve its quality.
The additional mixer uses a member variable for the multiplication constant. When an overflow is encountered, that constant is changed, thus the rehash will spread the elements completely differently.
Rehashing is tried multiple times (up to 256 times), so we won't get an endless loop if this rehashing still does not work.