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

532

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

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