Hopscotch hashing

Hopscotch hashing was introduced by Maurice Herlihy, Nir Shavit and Moran Tzafrir in 2008.

[1] The name is derived from the sequence of hops that characterize the table's insertion algorithm (see Hopscotch for the children's game).

In this way, an item can be found quickly by looking at the word to see which entries belong to the bucket, and then scanning through the constant number of entries (most modern processors support special bit manipulation operations that make the lookup in the "hop-information" bitmap very fast).

One advantage of hopscotch hashing is that it provides good performance at very high table load factors, even ones exceeding 0.9.

A lock-free variant was introduced by Robert Kelly, Barak A. Pearlmutter and Phil Maguire in 2020.

Hopscotch hashing. Here, H is 4. Gray entries are occupied. In part (a), the item x is added with a hash value of 6. A linear probe finds that entry 13 is empty. Because 13 is more than 4 entries away from 6, the algorithm looks for an earlier entry to swap with 13. The first place to look in is H −1 = 3 entries before, at entry 10. That entry's hop information bit-map indicates that d , the item at entry 11, can be displaced to 13. After displacing d , Entry 11 is still too far from entry 6, so the algorithm examines entry 8. The hop information bit-map indicates that item c at entry 9 can be moved to entry 11. Finally, a is moved to entry 9. Part (b) shows the table state just before adding x .