Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Space Efficient Hash Tables With Worst Case Constant Access Time

Fotakis, D., Pagh, R., Sanders, P., & Spirakis, P. (2005). Space Efficient Hash Tables With Worst Case Constant Access Time. Theory of Computing Systems, 38, 229-248.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-27B9-3 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-27BA-1
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Fotakis, Dimitris1, Autor           
Pagh, Rasmus, Autor
Sanders, Peter1, Autor           
Spirakis, Paul1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We generalize Cuckoo Hashing to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\e)\,n$ memory cells, for any constant $\e > 0$. Assuming uniform hashing, accessing or deleting table entries takes at most $d=\Oh{\ln\frac{1}{\e}}$ probes and the expected amortized insertion time is constant. This is the first dictionary that has worst case constant access time and expected constant update time, works with $(1+\e)\,n$ space, and supports satellite information. Experiments indicate that $d=4$ probes suffice for $\e\approx 0.03$. We also describe variants of the data structure that allow the use of hash functions that can be evaluated in constant time.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-06-192005
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 279165
Anderer: Local-ID: C1256428004B93B8-58634A459EB13055C125710300326DAE-Sanders2005b
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Theory of Computing Systems
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 38 Artikelnummer: - Start- / Endseite: 229 - 248 Identifikator: -