Хэш-таблицы – одна из самых элегантных структур данных: простая на поверхности и бесконечно глубокая внутри. Андрей Аксенов — автор поискового движка 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 Заключение
