Comparative analysis of two hash table filling strategies

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

Two strategies for filling hash tables consisting of several subtables are considered, without displacing previously inserted elements, one of which is based on sequential, the other on uniform filling of subtables. An analytical model is proposed for estimating the parameters of filling in the subtables and the combined hash table for the two strategies under consideration. Computer modeling was carried out, which confirmed the high accuracy of the proposed model and the advantage of a strategy based on sequential filling of subtables.

Full Text

Restricted Access

About the authors

A. A. Belyaev

National Research University "MIET"

Author for correspondence.
Email: belandr2015@yandex.ru

Dr. Tech. Sc., Associate Professor

Russian Federation, Moscow

References

  1. Fredkin E. Trie Memory, Communications of the ACM, 1960, no. 3, vol. 9, pp. 490—499.
  2. Knuth D. The Art of Computer Programming, Vol. 3: Sorting and Searching, Reading, Massachusetts, Addison-Wesley, 1998, 780 pp.
  3. Broder A., Karlin А. Multilevel Adaptive Hashing, In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 43—53.
  4. Azar Y., Broder A., Karlin A., Upfal E. Balanced Allocations, SIAM Journal on Computing, 1999, vol. 29, no. 1, pp. 180—200.
  5. Broder A., Mitzenmacher M. Using Multiple Hash Functions to Improve IP Lookups, Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM), 2001, pp. 1454—1463.
  6. Pagh R., Rodler F. Cuckoo Hashing, Journal of Algorithms, 2004, vol. 51, no. 2, pp. 122—144.
  7. Fountoulakis N., Panagiotou K., Steger А. On the insertion time of cuckoo hashing, SIAM Journal on Computing, 2013, vol. 42, no. 6, pp. 2156—2181.
  8. Devroye L., Morin P. Cuckoo hashing: further analysis, Information Processing Letters, 2003, vol. 86, no. 4, pp. 215—219.
  9. Mitzenmacher M. Some open questions related to cuckoo hashing, Proc. ESA, 2009, pp. 1—10.
  10. Fotakis D., Pagh R., Sanders P., Spirakis P. Space efficient hash tables with worst case constant access time, Proc. STACS, 2003, pp. 271—282.
  11. Frieze A., Melsted P., Mitzenmacher M. An analysis of randomwalk cuckoo hashing, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2009, pp. 490—503.
  12. Sun Y., Hua Y., Feng D., Yang L., Zuo P., Cao S. MinCounter: An efficient cuckoo hashing scheme for cloud storage systems, In: Symposium on Mass Storage Systems and Technologies (MSST), May 2015.
  13. Fountoulakis N., Panagiotou K., Steger А. On the insertion time of cuckoo hashing, SIAM Journal on Computing, 2013, vol. 42, no. 6, pp. 2156—2181.
  14. Fountoulakis N., Khosla M., Panagiotou K. The multipleorientability thresholds for random hypergraphs, Proc. ACM-SIAM symposium on Discrete Algorithms, 2011, pp. 1222—1236.
  15. Li Q., Hua Y., He W., Feng D., Nie Z., Sun Y. Necklace: An efficient cuckoo hashing scheme for cloud storage services, Proceedings of IEEE/ACM International Symposium on Quality of Service (IWQoS), 2014, pp. 50—55.
  16. Li D., Du R.,Liu Z., Yang T., Cui В. Multi-copy Cuckoo Hashing, IEEE 35th International Conference on Data Engineering (ICDE), 2019, pp.1226—1237.
  17. Kirsch A., Mitzenmacher M., Wieder U. More robust hashing: Cuckoo hashing with a stash, SIAM Journal on Computing, 2009, vol. 39, no. 4, pp. 1543—1561.
  18. Debnath B., Sengupta S., Li J. Chunkstash: Speeding up inline storage deduplication using flash memory, Proc. USENIX Annual Technical Conference, 2010.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Fig. 1. General combined scheme for organizing work with associative arrays

Download (138KB)
Indexing metadata
3. Fig. 2. Graphs of the dependence of the proportion of occupied cells in the merged hash table for the two considered strategies Fn(2)(v), Fu(2)(v)

Download (211KB)
Indexing metadata
4. Fig. 3. Graphs of the dependence of the proportion of collisions in the merged hash table for the two considered strategies Cn(2)(v), Cu(2)(v)

Download (198KB)
Indexing metadata
5. Fig. 4. Experimental graphs of the dependence of the proportion of collisions on the proportion of inserted elements for strategy 1 and strategy 2 at k = 2 and graphs of the corresponding analytical models

Download (246KB)
Indexing metadata
6. Fig. 5. Experimental graphs of the dependence of the proportion of collisions on the proportion of inserted elements for strategy 1 and strategy 2 at k = 4 and graphs of the corresponding analytical models

Download (233KB)
Indexing metadata

Copyright (c) 2026 Informacionnye Tehnologii


СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ПИ № 77 - 15565 от 02 июня 2003 г.