LHlf: lock-free linear hashing (poster paper)

Abstract

LHlf is a new hash table designed to allow very high levels of concurrency. The table is lock free and grows and shrinks auto-matically according to the number of items in the table. Insertions, lookups and deletions are never blocked. LHlf is based on linear hashing but adopts recursive split-ordering of the items within a bucket to be able to split and merge lists in a lock free manner. LHlf is as fast as the best previous lock-free design and in addition it offers stable performance, uses less space, and supports both expansions and contractions.