Автор: Андрей Аксенов · Podlodka Podcast
Андрей Аксенов — автор поискового движка Sphinx и человек, который писал собственные хэш-таблицы тогда, когда это ещё было нормальной практикой. Выпуск Podlodka #464 — не обзор структур данных, а разговор с человеком, который знает, где у хэш-таблиц болевые точки.
Хэш-таблицы — та структура данных, которую все используют и почти никто не понимает глубоко. Большинство разработчиков знают про O(1) в среднем и помнят что-то про load factor «меньше 0.75». Аксенов разбирает, откуда берутся эти числа, почему они не универсальны, и что реально происходит с производительностью, когда таблица растёт. Центральный тезис: поведение хэш-таблицы определяется не только алгоритмом, но и характером данных и паттерном доступа — и одна реализация не может быть одинаково хороша везде.
Разговор про open addressing особенно ценен: это техника, которая лежит в основе многих стандартных библиотек, но редко объясняется на уровне «почему именно так, а не иначе».
Кому смотреть: разработчикам, которые хотят понимать, что происходит внутри HashMap в их стандартной библиотеке, и тем, кто сталкивается с перформанс-проблемами в коде, который «должен работать быстро».
Из этого можно взять в работу: в следующий раз, когда выбираете или конфигурируете хэш-таблицу, спросите себя: какой у нас паттерн доступа — много reads или много writes, известен ли размер заранее, однородны ли ключи. Ответы на эти вопросы определяют выбор лучше, чем любой дефолтный load factor.
Аксенов начинает с фундамента: хэш-таблица — это массив плюс хэш-функция плюс политика разрешения коллизий. Все три компонента влияют на производительность, и оптимизировать один без понимания двух других бессмысленно.
Два классических подхода к коллизиям: chaining (каждый слот — список) и open addressing (ищем следующий свободный слот в самом массиве). Chaining проще реализовать и более предсказуем при высоком load factor. Open addressing быстрее при низком load factor из-за cache locality — все данные в одном массиве, меньше cache miss. Именно поэтому современные high-performance реализации (Google’s absl, Rust HashMap) используют open addressing с различными схемами зондирования.
Про load factor: порог 0.75 — не закон физики, а компромисс по умолчанию. При 0.5 таблица быстрее, но вдвое расточительнее по памяти. При 0.9 экономит память, но деградирует по скорости нелинейно — особенно при open addressing, где кластеризация коллизий резко возрастает. Аксенов показывает, что в специфических задачах осознанный выбор load factor может дать 2-3x прироста производительности.
Хэш-функции — отдельная тема. Криптографические хэши (SHA, MD5) для хэш-таблиц почти всегда избыточны и медленны. Хорошая нехэш-функция (MurmurHash, xxHash, wyhash) обеспечивает достаточное распределение при несравнимо меньшей стоимости. Аксенов также затрагивает HashDoS — атаку через коллизии, которая превращает O(1) в O(n) и ронает веб-сервисы — и объясняет, когда и как от неё защищаться.
Когда писать свою хэш-таблицу: практически никогда, но бывают случаи. Если у вас очень специфические ключи (короткие строки фиксированной длины, int64 из узкого диапазона) или очень предсказуемый паттерн доступа, специализированная реализация может выиграть у универсальной в разы.