Алгоритмы и структуры данных поиска: Хэширование. Бабенко Максим

Бабенко Максим рассказывает о хеширование.

1. Хеш-функции.
2. Коллизии.
3. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования.
4. Гипотеза простого равномерного хеширования, оценка средней длины цепочки.
5. Универсальные семейства хеш-функций, оценка средней длины цепочки.
6. Построение универсального семейства для целочисленных ключей.
7. Совершенные хеш-функции.
8. Построение совершенной хеш-функции с помощью универсального семейства.
9. Интерфейс множества с ошибками.
10. Фильтр Блюма (Bloom filter).
11. Оценка вероятности ложноположительного срабатывания.
12. Интерфейс словаря с ошибками.
13. Модификация фильтра Блюма (bloomier filter).