Автор: Андрей Аксенов · Podlodka Podcast

Андрей Аксенов — автор поискового движка Sphinx и человек, который писал собственные хэш-таблицы тогда, когда это ещё было нормальной практикой. Выпуск Podlodka #464 — не обзор структур данных, а разговор с человеком, который знает, где у хэш-таблиц болевые точки.

Хэш-таблицы — та структура данных, которую все используют и почти никто не понимает глубоко. Большинство разработчиков знают про O(1) в среднем и помнят что-то про load factor «меньше 0.75». Аксенов разбирает, откуда берутся эти числа, почему они не универсальны, и что реально происходит с производительностью, когда таблица растёт. Центральный тезис: поведение хэш-таблицы определяется не только алгоритмом, но и характером данных и паттерном доступа — и одна реализация не может быть одинаково хороша везде.

Разговор про open addressing особенно ценен: это техника, которая лежит в основе многих стандартных библиотек, но редко объясняется на уровне «почему именно так, а не иначе».

Кому смотреть: разработчикам,…