О новых алгоритмах хеш-таблиц
Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: «Optimal Bounds for Open Addressing Without Reordering» (Farach-Colton, Krapivin, and Kuszmaul, 2025) и последующую «The Bathroom Model: A Realistic Approach to Hash Table Algorithm Optimization» (Wang, 2025). И особенно кликбейтное: «в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете.»Я около 7 лет очень плотно занимался темой хеш-таблиц и написал много их вариантов: Koloboke, SmoothieMap, memory-mapped вариации.Я потерял к теме интерес с выходом гугловской SwissTable (2018), и ее фейсбучного варианта F14, которые основаны на SIMD. Они проверяют загруженность ячеек и совпадения «тега» элемента сразу блоками по 8 соседних слотов. Поэтому на любых разумных загрузках таблиц (до 90%) - «цепочка проверки» очень редко превышает 1 (то есть, одну проверку 8-элементного блока).В этих SIMD-based алгоритмах, ухищрения и теоретические по поводу «алгоритма шагания» просто не играют никакой роли -- алгоритм шагания можно сказать отсутствует, потому что если можно вставить элемент внутри 8-элементного блока, то это и стоит сделать.Именно эти разработки, а не Крут и не статья Yao, которую «опровергли» новые работы, стали «практическим концом теории» хеш-таблиц, на мой взгляд.SwissTable стали стандартным алгоритмом хеш-таблиц в Расте, и, буквально в этом месяце, в Golang 1.24.В заключение, отвечая Илье Кабанову: к «ускорению интернета» эти теоретические алгоритмы не приведут :) Читать далее