Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70233610.17587/it.32.3-11Modeling and optimizationМоделирование и оптимизацияResearch ArticleComparative analysis of two hash table filling strategiesСравнительный анализ двух стратегий заполнения хеш-таблицBelyaevA. A.БеляевА. А.
Russian Federation

Dr. Tech. Sc., Associate Professor

д-р техн. наук, доц.

belandr2015@yandex.ruNational Research University "MIET"Национальный исследовательский университет "МИЭТ"150120263213110802202608022026Copyright ©; 2026, Informacionnye TehnologiiCopyright ©; 2026, Информационные технологии2026Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702336

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.

Рассматриваются две стратегии заполнения хеш-таблиц, состоящих из нескольких подтаблиц, без вытеснения ранее вставленных элементов, одна из которых основана на последовательном, другая — на равномерном заполнении подтаблиц. Предложена аналитическая модель для оценки параметров заполнения подтаблиц и объединенной хеш-таблицы для двух рассматриваемых стратегий. Проведено компьютерное моделирование, подтвердившее высокую точность предложенной модели и преимущество стратегии, основанной на последовательном заполнении подтаблиц.

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