Cuckoo hashing är en effektiv och praktisk dynamisk ordbok. Det ger förväntad amortized konstant uppdateringstid, värsta fall konstant uppslagningstid, och bra minnesanvändning. Olika experiment visade att cuckoo hashing är mycket lämplig för moderna datorarkitekturer och distribuerade inställningar, och erbjuder betydande förbättringar jämfört med andra system. I detta arbete konstruerar vi ett praktiskt historieoberoende dynamiskt lexikon baserat på gökhashing. I en historikoberoende datastruktur ger minnesrepresentationen vid någon tidpunkt ingen information om den specifika sekvensen av tillägg och raderingar som ledde till dess nuvarande innehåll, annat än själva innehållet. En sådan egenskap är viktig när det gäller att förhindra oavsiktligt läckage av information, och befanns också användbar i flera algoritmiska inställningar. Vår konstruktion har de flesta av de attraktiva egenskaper gökoo hashing. I synnerhet krävs ingen dynamisk minnesallokering, uppdateringar utförs i förväntad amorterad konstant tid, och medlemskap frågor utförs i värsta fall konstant tid. Dessutom, med hög sannolikhet, uppslagningsproceduren frågor endast två minnesposter som är oberoende och kan frågas parallellt. Den metod som ligger till grund för vår konstruktion är att driva igenom en kanonisk minnesrepresentation på gökhashering. Det vill säga, fram till den inledande slumpmässigheten, varje uppsättning element har en unik minnesrepresentation. En preliminär version av detta verk publicerades i
Denna förstärkning var en viktig ingrediens i arbetet av Naor, Segev, och Wieder REF, som konstruerade en historia oberoende variant av guckoo hashing.
History-Independent Cuckoo Hashing
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Computer Science']}