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 ﬂavors 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.util.concurrent. Moreover, in tests on both Intel and Sun uni-processor machines, a sequential version of the algorithm consistently out performs the most eﬀective 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.
. Maurice Herlihy, Nir Shavit, and Moran Tzafrir. DISC 2008. (Talk slides.)
The source code is available here.