DYNAMIC PERFECT HASHING - UPPER AND LOWER BOUNDS

被引：175

作者：

DIETZFELBINGER, M

KARLIN, A

MEHLHORN, K

AUFDERHEIDE, FM

ROHNERT, H

TARJAN, RE

机构：

[1] DEC SYST RES CTR,PALO ALTO,CA 94301

[2] MAX PLANCK INST INFORMAT,D-66123 SAARBRUCKEN,GERMANY

[3] UNIV GH PADERBORN,FACHBEREICH MATH,D-33095 PADERBORN,GERMANY

[4] SIEMENS AG,D-81370 MUNICH,GERMANY

[5] HEINZ NIXDORF INST,D-33095 PADERBORN,GERMANY

[6] UNIV SAARLAND,W-6600 SAARBRUCKEN,GERMANY

来源：

SIAM JOURNAL ON COMPUTING | 1994年 / 23卷 / 04期

关键词：

DATA STRUCTURES; DICTIONARY PROBLEM; HASHING; UNIVERSAL HASHING; RANDOMIZED ALGORITHM; LOWER BOUND;

D O I：

10.1137/S0097539791194094

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 . n1/k).

引用

页码：738 / 761

页数：24

共 20 条

[1]

AHO HV, 1986, 27TH P IEEE FOCS, P55

[2]

BAST H, 1991, 3RD P ANN ACM S PAR, P50

[3] THE GENERATION OF RANDOM PERMUTATIONS ON THE FLY [J].

BRASSARD, G ;

KANNAN, S .

INFORMATION PROCESSING LETTERS, 1988, 28 (04) :207-212

[4]

CARTER L, 1979, J CSS, V18, P143, DOI DOI 10.1016/0022-0000(79)90044-8

[5]

Dietzfelbinger M., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P524, DOI 10.1109/SFCS.1988.21968

[6]

DIETZFELBINGER M, 1990, 22ND P ANN ACM S THE, P117

[7]

DIETZFELBINGER M, 1993, 513 U DORTM FACHB IN

[8]

DIETZFELBINGER M, 1992, LECTURE NOTES COMP S, V443, P95

[9] STORING A SPARSE TABLE WITH O(1) WORST CASE ACCESS TIME [J].

FREDMAN, ML ;

KOMLOS, J ;

SZEMEREDI, E .

JOURNAL OF THE ACM, 1984, 31 (03) :538-544

[10]

GIL J, 1991, 2ND P ANN ACM SIAM S, P271

← 1 2 →