Алгоритмы с нуля
Хеширование: тест с выбором ответа
Суть Синтез по всему юниту в формате выбора: hash function, collision, chaining, load factor, amortized resize и паттерны поверх hash map и hash set.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов, которые проходят через весь юнит. Каждый — это решение, которое вы принимаете, когда тянетесь к hash map на собеседовании или в реальном коде: не определение для пересказа, а tradeoff, который нужно защитить.
Цель
Убедитесь, что вы связываете hash function, обработку collision, load factor и amortized resize с повседневными паттернами — seen, частотный подсчёт, группировка, — к которым вели отдельные уроки.
Викторина
Completed
Hash set даёт O(1) поиск в среднем. На каком единственном факте на самом деле держится это «в среднем»?
Heads-up Hash set ничего не хранит в отсортированном виде, а обход неупорядочен. O(1) берётся из прямого вычисления индекса, а не из поиска по отсортированным данным.
Heads-up O(1) — это СРЕДНЕЕ при равномерном распределении и ограниченном load factor. При плохой hash function или враждебных ключах оно деградирует до O(n): среднее — это утверждение о типичных входах, а не гарантия.
Heads-up Движок помогает с константами, но асимптотическая гарантия всё равно держится на равномерном хешировании и управляемом load factor. Патологическое распределение ключей деградирует любую реализацию.
Викторина
Completed
Два разных ключа хешируются в один и тот же индекс бакета. При separate chaining что происходит и сколько это стоит?
Heads-up Это молча потеряло бы данные. Chaining хранит оба — бакет это список, а поиск сравнивает полный ключ, а не только индекс, поэтому коллидирующие ключи сосуществуют.
Heads-up Одна collision не вызывает resize. Resize управляется тем, что общий load factor пересекает порог, а не одной коллизией; collision ожидаемы и обрабатываются на месте цепочкой.
Heads-up Индекс общий, но сохранённый ключ — нет. Поиск сканирует цепочку и сопоставляет по реальному ключу, поэтому возвращает правильное значение несмотря на collision.
Викторина
Completed
В таблице 10 элементов на 5 бакетов, и она никогда не делает resize. Если продолжать вставлять без resize, что произойдёт со стоимостью поиска и почему?
Heads-up O(1) держится лишь пока alpha ограничен. При фиксированных бакетах и растущем числе элементов alpha растёт без предела, цепочки удлиняются — поиск деградирует к O(n).
Heads-up Больше элементов в фиксированных бакетах означает более длинные цепочки и больше сравнений на поиск, а не меньше. Драйвер — load factor, и он растёт.
Heads-up Collision становятся ЧАЩЕ по мере роста alpha — меньше свободных бакетов на элемент. Более полная таблица означает большую тесноту, а не меньшую.
Викторина
Completed
Вставку в hash table называют O(1) amortized, но одна вставка может стоить O(n). Как оба утверждения верны одновременно?
Heads-up Amortized — это не лучший случай, а среднее по последовательности, и оно явно ВКЛЮЧАЕТ O(n)-resize. Они учитываются, а затем размазываются по дешёвым вставкам через геометрию удвоения.
Heads-up Копирование и перехеширование n элементов действительно O(n) — каждый элемент переразмещается. Amortization не делает этот шаг дешёвым; она делает его достаточно редким, чтобы среднее оставалось O(1).
Heads-up Удаление не ломает amortized-оценку вставки. Аргумент про удвоение-при-росте самодостаточен; amortized-граница про геометрическое расписание resize, а не про удаления.
Викторина
Completed
Нужно определить, повторяется ли хоть одно значение в потоке, и отдельно — найти два числа, дающих в сумме target. Какой паттерн хеширования подходит каждому?
Heads-up Частотная map работает, но избыточна. Принадлежности нужна только presence (set), а two-sum нужна map из значения в индекс уже увиденного — ни тому, ни другому не нужны полные счётчики.
Heads-up Сортировка — O(n log n) и разрушает информацию об индексах, нужную для two-sum. Хеш-подходы — это один проход O(n) и сохраняют исходные индексы.
Heads-up Это обратная пара: обнаружению по присутствию нужен set, а поиску дополнения нужна map (значение в индекс), чтобы вернуть пару. Голый set не вернёт совпавший индекс для two-sum.
Викторина
Completed
Сервис хеширует строки от пользователя в таблицу, а атакующий заливает входами, специально подобранными так, чтобы все коллидировали в один бакет. В чём отказ и в чём настоящий фикс?
Heads-up Chaining обрабатывает collision корректно, но не дёшево, когда все попадают в один бакет — цепочка становится длиной n, а поиски — O(n). Корректность выживает; производительность рушится.
Heads-up Resize перераспределяет той же детерминированной hash function, поэтому враждебные ключи снова коллидируют после resize. Меньший порог не помогает, когда атакующий контролирует входы хеша; нужен непредсказуемый seed.
Heads-up Open addressing меняет то, как хранятся collision, а не то, коллидируют ли ключи атакующего. При предсказуемом хеше они всё равно скучиваются; защита — рандомизированный хеш, независимо от схемы разрешения.
Итог
Сквозная линия юнита — одна цепочка рассуждений: hash function превращает ключ в индекс для доступа O(1) в среднем; collision неизбежны, и chaining хранит их в списках на бакет; load factor задаёт среднюю длину цепочки, поэтому таблица делает resize — удвоение и перехеширование, — чтобы держать её ограниченной: O(n) на resize, но O(1) amortized; а сверху лежат повседневные паттерны — seen, дополнение, частотный подсчёт, группировка. Та же механика деградирует к O(n) при плохой или враждебной hash function, поэтому рандомизированный хеш важен для недоверенного входа.