Алгоритмы и структуры данных 4. Хеши и хеш-таблицы - std::unordered_set изнутри

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 24 февраля 2022 года
Лектор: Степанов Илья Даниилович
Оператор: Ирина Жулябина
Монтаж: Жильцов Игорь

0:00 - Вступление
0:40 - Постановка задачи
03:27 - Метод цепочек
08:29 - Алгоритмы обработки запросов
11:57 - Как избежать DoS-атаки, если используешь хеш-таблицы?
15:29 - Универсальное семейство хеш-функций
18:24 - Теорема 1 (б/д). Об асимптотике. Определение load_factor
21:48 - Rehash
26:46 - Пример универсального сеймейства ХФ
32:20 - Совершенное хеширование. Постановка задачи. Мотивация
34:35 - Решение за логарифм, без хешей
35:16 - Решение за чистое О(1) на запрос. "Двухуровневое хеширование"
38:00 - Условие на функцию h_out. Генерация функции h_out
45:15 - Теорема 2 (б/д). О коллизиях. Генерация подходящих функций h_i-ых
50:16 - Ещё одна мотивационная задача
51:35 - Хеш-таблица с открытой адресацией
55:00 - Алгоритмы обработки запросов
57:59 - Замечаение про rehash
58:40 - Анализ эффективности. k-независимые СХФ
01:00:56 - Теорема 3 (б/д). Для линейного пробирования
01:03:28 - Примеры k-независимых СХФ для k=2, 5
01:05:25 - Квадратичное пробирование
01:07:00 - Двойное хеширование
01:08:15 - Теорема 4 (б/д). Для двойного хеширования достаточно 2-независимости
01:09:19 - Фильтр Блума. Постановка задачи
01:12:00 - Алгоритмы обработки запросов
01:17:20 - Теорема 5 (б/д). Оптимальный выбор кол-ва хеш-функций и их области значений
01:19:14 - Время ответа на запрос
01:19:49 - Мотивация фильтра Блума