Хэш-таблицы — Open addressing, коллизии, hash

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

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

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

Содержание:

• 00:00 О чём выпуск?
• 06:11 Что такое хэш?
• 09:32 Хэш-функции
• 31:50 Хэш-таблица
• 45:57 Open addressing
• 01:01:14 Open addressing vs Buckets
• 01:04:51 Параметризованные хэш-функции
• 01:11:50 Для чего нужны хэш-таблицы?
• 01:20:28 Параметры хэш-таблиц
• 01:29:41 Тестирование производительности хэш-таблиц
• 01:36:16 Использование AI в хэшах
• 01:42:41 Новые подходы в хэш-таблицах
• 01:47:32 Заключение