Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering

The linear-probing hash table is one of the oldest and most widely used data structures in computer science. However, linear probing famously comes with a major draw-back: as soon as the hash table reaches a high memory utilization, elements within the hash table begin to cluster together, causing insertions to become slow. This phenomenon, now known as primary clustering, was first captured by Donald Knuth in 1963; at a load factor of$1 -1/x$, the expected time per insertion is$\Theta(x^{2})$, rather than the more desirable$\Theta(x)$. We show that there is more to the story than the classic analysis would seem to suggest. It turns out that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions. If these design decisions are made correctly, then even a hash table that is continuously at a load factor$1-\Theta(1/x)$can achieve average insertion time$\tilde{O}(x)$. A key insight is that the tombstones left behind by deletions cause a surprisingly strong “anti-clustering” effect, and that when insertions and deletions are one-for-one, the anti-clustering effects of deletions actually overpower the clustering effects of insertions. We also present a new variant of linear probing, which we call graveyard hashing, that completely eliminates primary clustering on any sequence of operations. If, when an operation is performed, the current load factor is$1 -1/x$for some$x$, then the expected cost of the operation is$O(x)$. One corollary is that, in the external-memory model with a data block size of$B$, graveyard hashing offers the following remarkable guarantee: at any load factor$1 -1/x$satisfying$x=o(B)$, graveyard hashing achieves$1 +o(1)$expected block transfers per operation. Past external-memory hash tables have only been able to offer a$1 +o(1)$guarantee when the block size$B$is at least$\Omega(x^{2})$. Our results come with actionable lessons for both theoreticians and practitioners, in particular, that well-designed use of tombstones can completely change the asymptotic landscape of how the linear probing behaves (and if there are no deletions).