English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AE33-0 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AE34-E
Genre: Other

Files

show Files

Locators

show

Creators

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

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2006-09-181991
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 344711
Other: Local-ID: C1256428004B93B8-5A593B783ED1767CC12571ED0031268B-mehlhorn91d
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show