Vi anser att ordböcker av storlek n över det finita universum u = (0, l}w och införa en ny teknik för deras genomförande: felkorrigerande koder. Användningen av sådana koder gör det möjligt att ersätta användningen av starka former av hashing, såsom universell hashing, med mycket svagare former, såsom klustering. Vi använder vår strategi för att konstruera, för alla E > 0, en deterministisk lösning på det dynamiska ordlistan problem med linjärt utrymme, med värsta fall tid 0 n') för tillägg och raderingar, och värsta fall tid O(1) I eller uppslag. Detta är den första deterministiska lösningen på det dynamiska ordboksproblemet med linjärt utrymme, konstant frågetid och icke-trivial uppdateringstid. I synnerhet får vi en lösning på problemet med den statiska ordboken med O(n) utrymme, värsta fall frågetid
Miltersen REF introducerade användningen av felkorrigeringskoder i ett nytt tillvägagångssätt för konstruktion av perfekta hashfunktioner.
Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries
{'venue': "SODA '98", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}