table table figure inserting into the table in figure displaces dwhich displaces bwhich displaces awhich displaces ewhich displaces fwhich displaces cwhich displaces it is not yet hopeless since when is displacedwe would now try the other hash tableat position howeverwhile that could be successful in generalin this case there is cycle and the insertion will not terminate detected more preciselythe probability that single insertion would require new set of hash functions can be made to be ( / )the new hash functions themselves generate more insertions to rebuild the tablebut even sothis means the rebuilding cost is minimal howeverif the table' load factor is at or higherthen the probability of cycle becomes drastically higherand this scheme is unlikely to work well at all after the publication of cuckoo hashingnumerous extensions were proposed for instanceinstead of two tableswe can use higher number of tablessuch as or while this increases the cost of lookupit also drastically increases the theoretical space utilization in some applications the lookups through separate hash functions can be done in parallel and thus cost little to no additional time another extension is to allow each table to store multiple keysagainthis can increase space utilization and make it easier to do insertions and can be more cache-friendly various combinations are possibleas shown in figure and finallyoften cuckoo hash tables are implemented as one giant table with two (or morehash functions that probe the entire tableand some variations attempt to place an item in the second hash table immediately if there is an available spotrather than starting sequence of displacements cuckoo hash table implementation implementing cuckoo hashing requires collection of hash functionssimply using hashcode to generate the collection of hash functions makes no sensesince any hashcode collisions will result in collisions in all the hash functions figure shows simple interface that can be used to send families of hash functions to the cuckoo hash table hash functions hash functions hash functions item per cell items per cell items per cell figure maximum load factors for cuckoo hashing variations