Abstract-Uppförandet av en dynamisk ordbok mäts främst av dess uppdateringstid, uppslagstid och rymdförbrukning. När det gäller uppdateringstid och uppslagstid finns det kända konstruktioner som garanterar konstant drift i värsta fall med hög sannolikhet, och när det gäller rymdförbrukning finns det kända konstruktioner som använder i huvudsak optimalt utrymme. Men även om den första analysen av en dynamisk ordbok går tillbaka mer än 45 år sedan (när Knuth analyserade linjär undersökning 1963), så är avvägningen mellan dessa aspekter av prestanda fortfarande inte helt klarlagd. I detta papper löser vi två grundläggande öppna problem: • Vi konstruerar den första dynamiska ordbok som har det bästa av båda världar: det lagrar n element med (1 + ε)n minne ord, och garanterar konstant-tid operationer i värsta fall med hög sannolikhet. Specifikt, för alla ε = (log log n/ log n) 1/2 ) och för alla sekvenser av polynomialt många operationer, med hög sannolikhet över slumpmässigheten i initieringsfasen, utförs alla operationer i konstant tid som är oberoende av ε. Konstruktionen är en två-nivå variant av cuckoo hashing, förstärkt med en "backyard" som hanterar en stor del av elementen, tillsammans med en de-amortized perfekt hashing system för att eliminera beroendet av ε. • Vi presenterar en variant av ovanstående konstruktion som använder endast (1 + o(1))B bitar, där B är den informations-teoretiska nedre gränsen för att representera en uppsättning av storlek n tas från ett universum av storlek u, och garanterar konstant-tid operationer i värsta fall med hög sannolikhet, som tidigare. Detta problem var öppet även i den amorterade miljön. En av huvudingredienserna i vår konstruktion är en permutationsbaserad variant av cuckoo hashing, vilket avsevärt förbättrar rymdförbrukningen av cuckoo hashing när man har att göra med ett ganska litet universum.
Denna dynamiska uppsättning kan lagras kortfattat med alla operationer tar O(1) tid med hög sannolikhet REF.
Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}