De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results

Yuriy Arbitman, Moni Naor, Gil Segev

Cuckoo hashing is a highly practical dynamic dictionary: it provides amortized constant insertion time, worst case constant deletion time and lookup time, and good memory utilizati…