Работа рассматривает способ увеличения скорости поиска в хеш-таблицах с хранением ссылки, если задача предполагает ограничение производительности пропускной способностью одного из интерфейсов между уровнями хранения (кэши L1, L2, L3, память). Для уменьшения влияния этого ограничения предлагается алгоритм оптимального использования размера кэш-линии – минимальной порции информации, передающейся между уровнями хранения. В работе показано, что существует наилучший для конкретных задачи и архитектуры размер информации о ключе в хеш-таблице (образ ключа), приведены формулы для его численного и приблизительного аналитического вычисления для случаев имеющегося и отсутствующего в таблице ключа. Рассмотрен отдельный случай использования части ключа в качестве его образа в таблице. Предложен алгоритм работы с неудобными размерами образа ключа, не являющимися степенью двойки. Приведенные результаты вычислений подтверждают увеличение производительности поиска при использовании вычисляемого размера образа ключа по сравнению с другими вариантами. Приведенный результат эксперимента подтверждает предположение, что связанное с этим усложнение кода практически не влияет на производительность из-за частичного простоя процессора. В работе подразумевается разрешение коллизий через цепочки, но схожие вычисления должны быть применимы и к другим способам с учетом их особенностей.
1. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск. Москва: И.Д. Вильямс; 2018. 832 с.
2. Farach-Colton M., Krapivin A., Kuszmaul W. Optimal Bounds for Open Addressing Without Reordering. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 27–30 October 2024, Chicago, IL, USA. IEEE; 2024. P. 594–605. https://doi.org/10.1109/FOCS61266.2024.00045
3. Zukowski M., Héman S., Boncz P. Architecture-Conscious Hashing. In: DaMoN '06: Proceedings of the 2nd International Workshop on Data Management on New Hardware, 25 June 2006, Chicago, IL, USA. New York: Association for Computing Machinery; 2006. https://doi.org/10.1145/1140402.114041
4. De Cristo F., De Almeida E., Alves M. ViViD Cuckoo Hash: Fast Cuckoo Table Building in SIMD. In: Proceedings of the 20th Symposium on High Performance Computing Systems, SSCAD 2019, 16–18 October 2019, Campo Grande, MS, Brasil. Porto Alegre: Sociedade Brasileira de Computação; 2019. P. 288–299. https://doi.org/10.5753/wscad.2019.8676
5. Thorup M. String Hashing for Linear Probing. In: SODA '09: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 04–06 January 2009, New York, USA. Philadelphia: Society for Industrial and Applied Mathematics; 2009. P. 655–664. https://doi.org/10.1137/1.9781611973068.72
6. Barredo A., Cebrian J.M., Valero M., Casas M., Moreto M. Efficiency Analysis of Modern Vector Architectures: Vector ALU Sizes, Core Counts and Clock Frequencies. The Journal of Supercomputing. 2020;76(3):1960–1979. https://doi.org/10.1007/s11227-019-02841-6
7. Chen S., Ailamaki A., Gibbons P.B., Mowry T.C. Improving Hash Join Performance Through Prefetching. ACM Transactions on Database Systems. 2007;32(3). https://doi.org/10.1145/1272743.1272747
8. Ross K.A. Efficient Hash Probes on Modern Processors. In: 2007 IEEE 23rd International Conference on Data Engineering, 15 April 2006 – 20 April 2007, Istanbul, Turkey. IEEE; 2007. P. 1297–1301. https://doi.org/10.1109/ICDE.2007.368997
9. Herlihy M., Shavit N., Tzafrir M. Hopscotch Hashing. In: Distributed Computing: 22nd International Symposium, DISC 2008: Proceedings, 22–24 September 2008, Arcachon, France. Berlin, Heidelberg: Springer; 2008. P. 350–364. https://doi.org/10.1007/978-3-540-87779-0_24
10. Tripathi R.R.K., Singh P.K., Singh S. Templing and Temple Search-Same Height Hashing. [Preprint]. ResearchSquare. URL: https://doi.org/10.21203/rs.3.rs-1947527/v1 [Accessed 21st May 2025].
Буевич Евгений Андреевич
Московский государственный технологический университет “СТАНКИН”
Москва, Российская Федерация
