Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Dynamic Perfect Hashing: Upper and Lower Bounds

Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer Auf Der Heide, F., Rohnert, H., & Tarjan, R. E. (1991). Dynamic Perfect Hashing: Upper and Lower Bounds.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Dietzfelbinger, Martin1, Autor           
Karlin, Anna2, Autor
Mehlhorn, Kurt1, Autor           
Meyer Auf Der Heide, Friedhelm, Autor
Rohnert, Hans2, Autor
Tarjan, Robert E.2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Max Planck Society, ou_persistent13              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lookup. A dynamic perfect hashing strategy is given: a randomized algorithm for the dynamic dictionary problem that takes O(1) worst-case time for lookups and O(1) amortized expected time for insertions and deletions; it uses space proportional to the size of the set stored. Furthermore, lower bounds for the time complexity of a class of deterministic algorithms for the dictionary problem are proved. This class encompasses realistic hashing-based schemes that use linear space. Such algorithms have amortized worst-case time complexity OMEGA(log n) for a sequence of n insertions and lookups; if the worst-case lookup time is restricted to k then the lower bound becomes $OMEGA (k^cdot^n sup 1/k$).

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-09-181991
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 344711
Anderer: Local-ID: C1256428004B93B8-5A593B783ED1767CC12571ED0031268B-mehlhorn91d
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: