Hopscotch Hashing


Hopscotch Hashing
 
Brown University
Tel-Aviv University,    Sun Microsystems
Tel-Aviv University 
 
 Abstract
We present a new resizable sequential and concurrent hash map algorithm directed at both uniprocessor and multicore machines. The algorithm is based on a novel hopscotch multi-phased probing and displacement technique that has the flavors of chaining, cuckoo hashing, and linear probing, all put together, yet avoids the limitations and over heads of these former approaches. The resulting algorithm provides a table with very low synchronization over heads and high cache hit ratios. In a series of benchmarks on a state-of-the-art 64-way Niagara II multicore machine, a concurrent version of the new algorithm proves to be highly scalable, delivering in some cases 2 or even 3 times the throughput of today’s most efficient concurrent hash algorithm, Lea’s ConcurrentHashMap from java.concurr.util. Moreover, in tests on both Intel and Sun uni-processor machines, a sequential version of the algorithm consistently out performs the most effective sequential hash table algorithms including cuckoo-hashing and bounded linear probing. The most interesting feature of the new hopscotch algorithm is that it continues to deliver good performance when the table is more than 90%full, increasing its advantage over other algorithms as the table density grows.
Subpages (1): Download
Comments