10.14489/vkit.2026.08.pp.043-050

DOI: 10.14489/vkit.2026.08.pp.043-050

Беляев А. А.
ВЛИЯНИЕ СТРУКТУРЫ АППАРАТНЫХ ХЕШ-ТАБЛИЦ НА ИХ ЗАПОЛНЯЕМОСТЬ
(c. 43-50)

Аннотация. Структура хеш-таблицы определяется количеством используемых хеш-функций (подтаблиц) и числом ячеек хранения, соответствующих каждому индексу хеш-функции (т.е. числом сегментов в подтаблице). Структура хеш-таблицы, как и алгоритм заполнения, напрямую влияет на достигаемый уровень заполнения хеш-таблицы. В отличие от большинства публикаций, посвященных организации хеш-таблиц, в которых основное внимание уделяется повышению заполняемости хеш-таблиц путем итеративного перераспределения элементов в таблице «по принципу кукушки» (Cuckoo Hashing), в данной работе рассматривается проблема заполняемости хеш-таблиц с первой попытки и без вытеснения ранее размещенных элементов. Такой подход дает важное преимущество в скорости обработки данных. Получены аналитические зависимости характеристик заполнения хеш-таблиц от количества вставляемых элементов при различных структурных параметрах. Показано, что количество используемых хеш-функций оказывает большее влияние на заполняемость, чем количество сегментов. Проведено компьютерное моделирование, подтвердившее высокую точность предложенных теоретических моделей.

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

Belyaev A. A.
THE INFLUENCE OF HARDWARE HASH TABLES STRUCTURE ON THEIR LEVEL OF FILLING
(pp. 43-50)

Abstract. The hash table structure is determined by the number of hash functions used (i.e., the number of sub-tables) and the number of storage cells corresponding to each hash function index (i.e., the number of segments in each sub-table). The structure of the hash table, as well as the filling algorithm, has a direct impact on the achieved level of the hash table filling. Unlike most publications on the hash tables optimizations, which focus on increasing the hash tables filling level by iteratively redistributing elements in the table according to the Cuckoo Hashing method, this paper examines the problem of hash tables filling "on the first attempt", without displacing previously inserted elements. Such approach provides an advantage in data processing speed in many practically important cases. 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 dependences on the number of inserted elements for various structural parameters under consideration are obtained. It is shown that the number of hash functions used has a greater impact on hash table filling level than that of the number of sub-tables segments. For example, the hash table configuration (k = 4, b = 1) provide greater filling level compared to configuration parameters (k = 1, b = 4) by about % of the total volume of the hash table. Computer modeling was performed and its results confirmed the high accuracy of the obtained theoretical models. The discrepancy between the analytical models and the experimental results for the considered cases does not exceed about 0.2 %. The proposed analytical models for the hash table filling characteristics can be effectively used in practical design.

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 Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

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

Рус

1. Knuth D. The Art of Computer Programming. Vol. 3: Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1998. 780 pp.
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. Vol. 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. Vol. 51(2). P. 122–144.
6. Fountoulakis N., Panagiotou K., Steger A. On the insertion time of cuckoo hashing // SIAM Journal on Computing. 2013. Vol. 42, no. 6. P. 2156–2181.
7. Devroye L., Morin P. Cuckoo hashing: further analysis // Information Processing Letters. 2003. Vol. 86, no. 4. P. 215–219.
8. Mitzenmacher M. Some open questions related to cuckoo hashing // Proc. ESA. 2009. 17th Annual European Symposium. 7–9 September 2009. Copengagen, Denmark. P. 1–10.
9. Fotakis D., Pagh R., Sanders P., Spirakis P. Space efficient hash tables with worst case constant access time // Proc. 2003. Symposium on Theoretical Aspects of Computer science (STACS 2003). 27 Feb–1 March. 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. P. 490–503.
11. Erlingsson V., Manasse M., Mcsherry F. A Cool and Practical Alternative to Traditional Hash Tables // In Seventh Whorkshop on Distributed Data and Structures (WDAS’2006). 4–6 January 2006. Santa Clara, California, USA. P. 1–6.

Eng

1. Knuth, D. E. (1998). The art of computer programming (Vol. 3: Sorting and searching). 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). San Francisco, CA, USA.
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). Anchorage, AK, USA.
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). Copenhagen, Denmark.
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 Symposium on Theoretical Aspects of Computer Science (STACS 2003) (pp. 271–282). Berlin, Germany.
10. Frieze, A., Melsted, P., & Mitzenmacher, M. (2009). An analysis of randomwalk cuckoo hashing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (pp. 490–503). Springer.
11. Erlingsson, V., Manasse, M., & Mcsherry, F. (2006). A cool and practical alternative to traditional hash tables. In Seventh Workshop on Distributed Data and Structures (WDAS’2006) (pp. 1–6). Santa Clara, CA, USA.

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

Рус

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

Стоимость статьи 700 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2026.08.pp.043-050

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 700 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2026.08.pp.043-050

and fill out the form