Hopscotch hashing

lastmod 2026-11-10created 2018-11-253 edits

Hopscotch hashing is a hash table technique based on open addressing that keeps each item within a fixed distance (the neighborhood) of its original bucket. On a collision, it finds an empty slot and then moves items around to make room inside the neighborhood, so lookups finish within a short range and cache efficiency is good. It is used as an alternative to linear probing or cuckoo hashing.

See also

• Hash function

Favorite site

• Github - A C++ implementation of a fast hash map and hash set using hopscotch hashing
• Hopscotch hashing ¹

References