Potentially critical bug in Robin Hood invariant checking about robin-hood-hashing HOT 4 CLOSED

Hi! I'm not 100% sure where you think there is a bug. In my robin_hood map implementation the entries with equal PSL are sorted according to the hoisted hash bits, so it is ok to stop the loop before actually reaching the next PSL.

That's one of the tricks of robin_hood that I think are quite nice, because when PSL are used as the higher bits and the hoised hash bits used for the lower bits it is enough use info <= mInfo[idx] as a stopping criteria

from robin-hood-hashing.

By the way I'm using exactly the same trick in my unordered_dense map: https://github.com/martinus/unordered_dense
I think that code might be easier to read. There I am always using 24bit as PSL and 8 bit for the hoisted hash, both stored in dist_and_fingerprint: https://github.com/martinus/unordered_dense/blob/main/include/ankerl/unordered_dense.h#L317-L323

from robin-hood-hashing.

Thanks for the explanation. I will close the issue.
Is there a place in the source code where you state this property, of augmenting the Robin Hood invariant with the fingerprint of the key?
I will study your unordered_dense

from robin-hood-hashing.

Hm I don't think I have written down anywhere. Some years ago I wrote a blog post, but this is outdated: https://martin.ankerl.com/2016/09/21/very-fast-hashmap-in-c-part-2/

One more note, the encoded PSL value has an offset of 1, so 0 means the bucket is empty, 1 means this bucket is taken and actually is at the correct location, 2 means its one bucket away from its intended location.

from robin-hood-hashing.