Cuckoo hashing

被引：694
作者：
Pagh, R
Rodler, FF
机构：
[1] IT Univ Copenhagen, DK-2300 Copenhagen S, Denmark
[2] ON AIR AS, DK-9200 Aalborg SV, Denmark
来源：
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2004年 / 51卷 / 02期
关键词：
data structures; dictionaries; information retrieval; searching; hashing; experiments;
D O I：
10.1016/j.jalgor.2003.12.002
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738-761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time. (C) 2003 Elsevier Inc. All rights reserved.
引用
收藏
页码：122 / 144
页数：23
相关论文
共 29 条
  • [1] [Anonymous], COMPUT AUTOM
  • [2] Balanced allocations
    Azar, Y
    Broder, AZ
    Karlin, AR
    Upfal, E
    [J]. SIAM JOURNAL ON COMPUTING, 1999, 29 (01) : 180 - 200
  • [3] Berenbrink P., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P745, DOI 10.1145/335305.335411
  • [4] REDUCING RETRIEVAL TIME OF SCATTER STORAGE TECHNIQUES
    BRENT, RP
    [J]. COMMUNICATIONS OF THE ACM, 1973, 16 (02) : 105 - 109
  • [5] BRODER AZ, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P43
  • [6] CARTER L, 1979, J CSS, V18, P143, DOI DOI 10.1016/0022-0000(79)90044-8
  • [7] DIETZFELBINGER M, 1992, LECT NOTES COMPUT SC, V623, P235
  • [8] A reliable randomized algorithm for the closest-pair problem
    Dietzfelbinger, M
    Hagerup, T
    Katajainen, J
    Penttonen, M
    [J]. JOURNAL OF ALGORITHMS, 1997, 25 (01) : 19 - 51
  • [9] DYNAMIC PERFECT HASHING - UPPER AND LOWER BOUNDS
    DIETZFELBINGER, M
    KARLIN, A
    MEHLHORN, K
    AUFDERHEIDE, FM
    ROHNERT, H
    TARJAN, RE
    [J]. SIAM JOURNAL ON COMPUTING, 1994, 23 (04) : 738 - 761
  • [10] DIETZFELBINGER M, 1990, LECT NOTES COMPUT SC, V443, P6, DOI 10.1007/BFb0032018
123