10.14489/vkit.2026.04.pp.045-052

DOI: 10.14489/vkit.2026.04.pp.045-052

Беляев А. А.
ВЫБОР СТРАТЕГИИ ЗАПОЛНЕНИЯ ДВУХСЕКЦИОННЫХ ХЕШ-ТАБЛИЦ БЕЗ ВЫТЕСНЕНИЯ РАНЕЕ ВСТАВЛЕННЫХ ЭЛЕМЕНТОВ
(c. 45-52)

Аннотация. Известно, что применение многосекционных хеш-таблиц, состоящих из нескольких подтаблиц (секций) с соответствующими хеш-функциями, позволяет повысить по сравнению с односекционными таблицами их общую заполняемость. Рассмотрены две стратегии заполнения аппаратных двухсекционных хеш-таблиц без последующего вытеснения ранее вставленных элементов: одна основана на последовательном неравномерном, другая – на поочередном равномерном заполнении подтаблиц. Предложены теоретические модели для оценки характеристик заполнения хеш-таблиц для обеих стратегий. Проведено компьютерное моделирование, подтвердившее высокую точность предложенных моделей и преимущество стратегии, основанной на последовательном заполнении подтаблиц.

Ключевые слова: ассоциативный массив; хеширование; хеш-функция; хеш-таблица.

Belyaev A. A.
CHOOSING A STRATEGY FOR FILLING TWO-SECTION HASH TABLES WITHOUT REPLACING PREVIOUSLY INSERTED ELEMENTS
(pp. 45-52)

Abstract. It is known that the use of multi-section hash tables consisting of several subtables (sections) each having its own hash function results in their overall occupancy percentage growing as compared to single-section tables. To achieve greater occupancy, the technique of redistributing elements between sections of the table, known as Cuckoo hashing, is usually used, which consists in iteratively replacing previously inserted elements by the new ones and finding alternative places in the table for these evicted elements. However, such a redistribution is associated with additional energy and time costs, that may be unacceptable for modern high-speed telecommunication and data processing systems. For this reason, the importance of properly organizing the process of initial filling of hash tables, without replacing previously inserted items, is increasing. The article discusses two strategies for filling hardware two-section hash tables without replacing previously inserted elements. One strategy is based on sequential uneven filling of the subtables while the other applies uniform filling. Based on the theoretical analysis in which the hash tables filling is considered as a pseudorandom process, the analytical formulas for the hash tables filling characteristics for the two strategies under consideration are obtained. Computer modeling was performed, and its results confirmed the high accuracy of the obtained models as well as the advantage of a strategy based on sequential filling of subtables.

Keywords: Associative array; Hashing; Hash function; Hash table.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

А. А. Беляев (Национальный исследовательский университет «Московский институт электронной техники», Москва, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

A. A. Belyaev (National Research University of Electronic Technology – MIET, Moscow, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Knuth D. The Art of Computer Programming. V. 3: Sorting and Searching. 2d ed. Massachusetts: Addison-Wesley, 1998, 780 p.
2. Broder A., Karlin A. Multilevel Adaptive Hashing // Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms. 22–24 January 1990. San Francisco, California, USA. P. 43–53.
3. Azar Y., Broder A., Karlin A., Upfal E. Balanced Allocations // SIAM Journal on Computing. 1999. V. 29(1). P. 180–200.
4. Broder A., Mitzenmacher M. Using Multiple Hash Functions to Improve IP Lookups // Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM). 22–26 April 2001. Anchorage, Alaska, USA. P. 1454–1463.
5. Pagh R., Rodler F. Cuckoo Hashing // Journal of Algorithms. 2004. V. 51(2). P. 122–144.
6. Fountoulakis N., Panagiotou K., Steger A. On the insertion time of cuckoo hashing // SIAM Journal on Computing. 2013. V. 42, No. 6. P. 2156–2181.
7. Devroye L., Morin P. Cuckoo hashing: further analysis // Information Processing Letters. 2003. V. 86, No. 4. P. 215–219.
8. Mitzenmacher M. Some open questions related to cuckoo hashing // Proc. ESA 2009, 17th Annual European Symposium. Copenhagen, Denmark, 7–9 September 2009. P. 1–10.
9. Fotakis D., Pagh R., Sanders P., Spirakis P. Space efficient hash tables with worst case constant access time // Proc. STACS, Symposium on Theoretical Aspects of Computer Science. 27 February – 1 March 2003. Berlin, Germany. P. 271–282.
10. Frieze A., Melsted P., Mitzenmacher M. An analysis of randomwalk cuckoo hashing // Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 2009. Springer, Berlin, Heidelberg. V.5687. P. 490–503. (APPOX 2009, RANDOM 2009). DOI:10.1007/978-3-642-03685-9_37
11. MinCounter: An efficient cuckoo hashing scheme for cloud storage systems / Sun Y., Hua Y., Feng D. et al. Proceedings of the 31st International Conference on Massive Storage Systems and Technology, 30 May 2015 – 05 June 2015, Santa Clara, CA, USA, P. 1–7.

Eng

1. Knuth, D. E. (1998). The art of computer programming (Vol. 3: Sorting and searching, 2nd ed.). Addison Wesley.
2. Broder, A., & Karlin, A. (1990). Multilevel adaptive hashing. In Proceedings of the 1st ACM SIAM Symposium on Discrete Algorithms (pp. 43–53). ACM/SIAM.
3. Azar, Y., Broder, A., Karlin, A., & Upfal, E. (1999). Balanced allocations. SIAM Journal on Computing, 29(1), 180–200.
4. Broder, A., & Mitzenmacher, M. (2001). Using multiple hash functions to improve IP lookups. In Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM) (pp. 1454–1463). IEEE.
5. Pagh, R., & Rodler, F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122–144.
6. Fountoulakis, N., Panagiotou, K., & Steger, A. (2013). On the insertion time of cuckoo hashing. SIAM Journal on Computing, 42(6), 2156–2181.
7. Devroye, L., & Morin, P. (2003). Cuckoo hashing: Further analysis. Information Processing Letters, 86(4), 215–219.
8. Mitzenmacher, M. (2009). Some open questions related to cuckoo hashing. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009) (pp. 1–10). Springer.
9. Fotakis, D., Pagh, R., Sanders, P., & Spirakis, P. (2003). Space efficient hash tables with worst case constant access time. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003) (pp. 271–282). Springer.
10. Frieze, A., Melsted, P., & Mitzenmacher, M. (2009). An analysis of randomwalk cuckoo hashing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Vol. 5687, pp. 490–503). Springer. https://doi.org/10.1007/978-3-642-03685-9_37
11. Sun, Y., Hua, Y., Feng, D., et al. (2015). MinCounter: An efficient cuckoo hashing scheme for cloud storage systems. In Proceedings of the 31st International Conference on Massive Storage Systems and Technology (MSST 2015) (pp. 1–7). IEEE.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

DOI: 10.14489/vkit.2026.04.pp.045-052

Скопируйте DOI статьи и перейдите по ссылке https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

В комментарии к заказу обязательно укажите DOI статьи.

Eng

This article is available in electronic format (PDF).

DOI: 10.14489/vkit.2026.04.pp.045-052

Copy the article DOI and follow the link https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

Please specify the article DOI in the order comments.