Linear Probing Made Faster

Very interesting paper.

The paper is very long and mostly math so I only skimmed it. It seems to me (as a practitioner) the key insight to alleviate primary clustering effects is the following:

At high loads, when you rebuild the hash table, you put k/2 "fake tombstones" evenly across the table, where k is the # of free slots in the table. This way, when one performs an insertion, the iteration length is going to be short (thanks to the evenly spreaded tombstone), thus alleviating the primary clustering effects.

I'm very interested in seeing some empirical numbers for graveyard hashing in both RAM and external storage use case.