Хэш-таблицы – одна из самых элегантных структур данных: простая на поверхности и бесконечно глубокая внутри. Андрей Аксенов -- автор поискового движка Sphinx, разбирает их устройство от фундамента до тонкостей реализации.

В выпуске обсуждаем два подхода к разрешению коллизий: Open addressing и Buckets, выбор хэш-функций для разных задач, развенчиваем популярные мифы вроде "load factor больше 0.5 – это смерть". Разбираемся, нужны ли криптографические хэш-функции, когда имеет смысл писать свою хэш-таблицу и почему скорость хэш-функции не всегда благо.

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