File CuckooHashing.h

↰ Parent directory (ADS/dictionary)

The cuckoo hashing of Pagh and Rodler, beyond the book: each key k is in one of the two places :math:` h_1( k ) ` and :math:` h_2( k ) ` of a table of m places, so that a search and a removal look at two places, O( 1 ) time in the worst case.

Definition (ADS/dictionary/CuckooHashing.h)

Detailed Description

An insertion puts k in the first empty one of its two places, else in :math:` h_1( k ) , evicting the key y there, which moves to its other place, possibly evicting another key, and so on; after MaxLoop evictions the insertion gives up and the table is rebuilt with two new functions (a rehash). In the cuckoo graph, whose vertices are the places and whose edges are the keys, the evictions follow a path from a place of k, and an insertion fails only if the component of k has more than one cycle; for :math: m ge 2 c n ` two places are joined by a shortest path of length L with probability at most :math:` c^{-L} / m ` (Theorem 8.9 of the notes), a key is in the bucket of another with probability O( 1 / m ), and a cycle in the final graph has probability at most :math:` 1 / ( c - 1 ) , at most 1 / 2 for :math: m ge 6 n ( 1 + epsilon ) : an insertion takes O( 1 ) amortized expected time. With one table and both functions on it the graph is a random graph of m vertices and n edges, whose components have at most one cycle with high probability while :math: n / m < 1 / 2 `; the table doubles past the load maxLoad (by default 0.4) and halves below maxLoad / 4, the global rebuilding of the notes.

A stash of s places (Kirsch, Mitzenmacher and Wieder) keeps the keys whose insertion fails, lowering the probability of a rehash from :math:` Theta( 1 / n ) ` to :math:` Theta( 1 / n^{s+1} ) ; a search also looks at the stash. The two functions are simple tabulation [see TabulationHash in :ref:`file_ADS_dictionary_RandomHashing.h] of the hash of the key, which, as Patrascu and Thorup proved, keeps the failure probability of cuckoo hashing at :math:` O( 1 / n^{1/3} ) , while the analysis of Pagh and Rodler asks for :math: O( log n ) -independent functions (Aumueller, Dietzfelbinger and Woelfel give explicit ones that suffice with a stash). Compared with the open addressing [see :ref:`file_ADS_dictionary_OpenHashTable.h], a search has no cluster to walk; the variants of today put several keys in a place (blocked cuckoo hashing, loads above 90 %) or use d > 2 functions (Fotakis et al.).

MaxLoop is :math:` 8 lceil log_2 m rceil + 16 , against the :math: 3 log_{1+epsilon} m ` of the analysis of Pagh and Rodler.

The contracts [see File Contract.h]: m >= 2 and 0 < maxLoad < 1 / 2; insert() ensures that the key is there and remove() that it is not; the invariant is that each key is in one of its two places or in the stash and that the keys are counted right, checked on the key of the operation only past 1024 places, so that a long sequence of operations at the level 3 stays linear. The operations are defined in CuckooHashing.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 8 (section 8.6)

  1. Pagh, F. F. Rodler, Cuckoo hashing, Journal of Algorithms 51(2), 122-144, 2004, doi:10.1016/j.jalgor.2003.12.002

  1. Kirsch, M. Mitzenmacher, U. Wieder, More robust hashing: cuckoo hashing with a stash, SIAM Journal on Computing 39(4), 1543-1561, 2009, doi:10.1137/080728743

  1. Aumueller, M. Dietzfelbinger, P. Woelfel, Explicit and efficient hash families suffice for cuckoo hashing with a stash, Algorithmica 70(3), 428-456, 2014, doi:10.1007/s00453-013-9840-x

  1. Patrascu, M. Thorup, The power of simple tabulation hashing, Journal of the ACM 59(3), article 14, 2012, doi:10.1145/2220357.2220361

  1. Fotakis, R. Pagh, P. Sanders, P. Spirakis, Space efficient hash tables with worst case constant access time, Theory of Computing Systems 38(2), 229-248, 2005, doi:10.1007/s00224-004-1195-x

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes