> 1) The linearly-probed robin hood variant is just a sorted array. That's it. It's just a sorted array. Right. I stumbled on linear probing robin hood hashing

> 1) The linearly-probed robin hood variant is just a sorted array. That's it. It's just a sorted array. Right. I stumbled on linear probing robin hood hashing as a simplification of Bender, Demaine and Farach-Colton's Packed memory array (http://erikdemaine.org/papers/FOCS2000b/paper.pdf http://erikdemaine.org/papers/FOCS2000b/paper.pdf) when inserts are randomised. > 2) The linearly-probed robin hood variant is only faster than regular linear probing for searches that fail. The sortedness means Robin Hood should not only be faster in the worst case (that's what reducing variance is all about), even for successful searches, but can also be faster on average, at high enough loads: make sure empty cells compare as greater than any legitimate value, track the maximum displacement, and use binary search (or just use exponential search).