Cuckoo hashing, som infördes av Pagh och Rodler [10], är en dynamisk ordbok datastruktur för att lagra en uppsättning S av n nycklar från ett universum U, med konstant uppslagningstid och amortized förväntad konstant insättningstid. För analysen räcker det med utrymme (2+ε)n och (log n)-vis oberoende av hashfunktionerna. I experiment som nämns i [10], flera svagare hash klasser fungerade bra, men en viss enkel multiplikativ hash familj fungerade dåligt. I detta papper bevisar vi att sannolikheten för fel är hög när gökhashering körs med multiplikativ klass eller med den mycket vanliga klassen av linjär hash funktioner över ett huvudfält, även om utrymme 4n tillhandahålls. Nyckeln uppsättningen S är helt slumpmässig, men det måste vara relativt tät i universum U av alla nycklar (t.ex. Det dåliga beteendet och det faktum att denna effekt beror på densiteten av S i U kan också observeras i experiment. Resultatet överförs till större universer om tangenterna väljs från en lämplig mindre domän. Ur ett annat perspektiv illustrerar vårt resultat att man måste vara försiktig när man tillämpar ett resultat av Mitzenmacher och Vadhan ([12], SODA 2008) som visar ett gott beteende hos universella haschklasser i kombination med nyckeluppsättningar som har entropi. Deras resultat är tillämpligt på gökhashing. En teknisk hypotes i [12], nämligen antagandet att antingen "kollisionssannolikhet" eller "maximal sannolikhet" är liten, översätts till villkoret att  tills är relativt liten i jämförelse med  på U. Vårt resultat visar att resultatet från [12] på 2-universal klasser upphör att hålla om  och/eller U inte är tillräckligt litet, även för mycket vanliga 2-universal hash klasser och helt slumpmässiga nyckeluppsättningar.
Mycket nyligen, Dietzfelbinger och Schellbach REF visade att två naturliga klasser av hash funktioner, den multiplikativa klass och klass av linjära funktioner över ett huvudfält, leder till stor fel sannolikhet om tillämpas i cuckoo hashing.
On risks of using cuckoo hashing with simple universal hash classes
{'venue': 'In Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}