Cuckoo hashing är en mycket praktisk dynamisk ordbok: det ger amortized konstant insättningstid, värsta fall konstant raderingstid och uppslagningstid, och bra minnesanvändning. Men med en märkbar sannolikhet under införandet av n element vissa insättning kräver  på (log n) tid. Medan en sådan amorterad garanti kan vara lämplig för vissa tillämpningar, i andra tillämpningar (såsom högpresterande routing) är detta mycket oönskade. Nyligen, Kirsch och Mitzenmacher (Allerton '07) föreslog en de-amortization av cuckoo hashing med hjälp av olika kö tekniker som bevarar sina attraktiva egenskaper. Kirsch och Mitzenmacher visade en betydande förbättring till det värsta fallet prestanda göko hashing via experimentella resultat, men de lämnade öppna problemet med att bygga ett system med bevisbara egenskaper. I detta arbete följer vi Kirsch och Mitzenmacher och presenterar en de-amortisering av cuckoo hashing som bevisligen garanterar konstant värsta fall operationer. Specifikt, för varje sekvens av polynomiskt många operationer, med överväldigande sannolikhet över slumpmässigheten i initieringsfasen, utförs varje operation i konstant tid. Vår teoretiska analys och experimentella resultat indikerar att programmet är mycket effektivt, och ger ett praktiskt alternativ till den enda kända dynamiska ordbok med sådana värsta fall garantier, på grund av Dietzfelbinger och Meyer auf der Heide (ICAP '90). - Vad är det för fel på dig?
Nyligen, Arbitman et al. REF presenterade en de-amortisering av cuckoo hashing som garanterar konstant drift i värsta fall med hög sannolikhet, och uppnår minnesanvändning på cirka 50%.
De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}