Коэффициент заполнения: почему словарь всё-таки не константа

Если ты знаешь, что α = n/m, что среднее время поиска растёт с α, и почему таблицу держат недозаполненной с рехешированием, листай до «Теперь сам».

Как думаешь, от чего зависит скорость хеш-таблицы

Мы знаем: доступ по ключу - O(1) в среднем, но коллизии неизбежны и их надо разрешать. Возникает вопрос: а СКОЛЬКО именно работы добавляют коллизии? Ясно, что это зависит от тесноты: в почти пустой таблице ключи редко сталкиваются, поиск короткий; в набитой под завязку - каждая ячейка забита, поиск бредёт по длинной цепочке столкнувшихся ключей. Значит у скорости есть один главный «регулятор» - насколько плотно набита таблица. Назовём его и поймём, как он управляет временем: тогда станет ясно, почему словарь надо держать полупустым и почему иногда он вдруг «тормозит» на одной операции.

На что это похоже

Парковка у торгового центра. Пока занято 30% мест, ты въезжаешь и сразу видишь свободное - почти не ищешь. Когда занято 95%, ты кружишь по этажам, проверяя ряд за рядом, - поиск места растягивается. Заполненность парковки - это и есть α, а время поиска места растёт вместе с ней. Разумный ТЦ не ждёт, пока забьётся под завязку: при 80% открывает новый этаж (увеличивает m). Хеш-таблица делает ровно это - следит за α и, когда становится тесно, расширяется, чтобы поиск снова стал коротким.

Механизм: α = n/m и его влияние на время

Коэффициент заполнения - простое отношение:

α = n / m       # n - сколько ключей уже в таблице, m - сколько всего ячеек

α = 0.5 - таблица заполнена наполовину; α = 1 - ключей столько же, сколько ячеек; α > 1 возможно только при цепочках (в открытой адресации α < 1 обязательно - следующая глава). При РАВНОМЕРНОЙ хеш-функции ключи размазаны по ячейкам ровно, и в среднем на ячейку приходится α ключей. Отсюда среднее число проверок на поиск - порядка 1 + α: одна на саму ячейку плюс проход по столкнувшимся в ней. Пока α - небольшая константа (скажем, 0.75), это O(1). Но если дать α расти (ключей всё больше, m не меняется), время поиска растёт линейно по α, и O(1) теряется.

Поэтому реальные таблицы держат порог. При превышении (например, α > 0.75) делают рехеширование:

1. завести новый массив вдвое больше (m → 2m, снова простое рядом)
2. пересчитать h(ключ) для КАЖДОГО ключа под новое m и переложить
3. старый массив выбросить

Правило

Коэффициент заполнения α = n/m управляет скоростью хеш-таблицы: при равномерной функции среднее число проверок на поиск - порядка 1 + α. Пока α держат небольшой константой (0.5–0.75), поиск - O(1) в среднем; если дать α расти, время растёт линейно. Поэтому таблицу держат НЕДОЗАПОЛНЕННОЙ, а при превышении порога РЕХЕШИРУЮТ - заводят массив вдвое больше и перекладывают все ключи. Отсюда честная формулировка: словарь - O(1) в среднем при условии «равномерная функция И α под контролем».

Разбор: почему рехеширование - это амортизированно O(1)

Рехеширование пугает: переложить ВСЕ n ключей - это O(n), дорогая операция посреди быстрых. Не рушит ли она O(1)? Нет - и здесь работает та же амортизация, что у растущего массива из раздела про списки. Удваиваем m при заполнении, значит между двумя рехешированиями успеваем добавить ≈ m новых ключей (пока α дойдёт от 0.375 снова до 0.75). Дорогая переборка O(m) «размазывается» по этим m дешёвым вставкам - по константе на каждую. Итог: одна вставка иногда стоит O(n), но СРЕДНЯЯ (амортизированная) по длинной серии - O(1). Ключевое условие - удвоение (умножение на константу), а не добавление фиксированного числа ячеек: прибавляй мы по +1000, рехеширования шли бы всё чаще и амортизация сломалась бы (O(n) на вставку). Это ровно тот же расчёт, что и у динамического массива, - хеш-таблица наследует его целиком.

Разбор: почему из-за рехеширования словарь иногда «дёргается»

Практическое следствие амортизации: отдельная вставка в словарь МОЖЕТ занять O(n), когда на ней сработало рехеширование. В среднем всё быстро, но конкретная операция «не повезло» затягивается - таблица в этот миг перекладывает миллионы ключей. Для большинства программ это незаметно, но там, где важна ПРЕДСКАЗУЕМАЯ задержка каждой операции (системы реального времени, игровые кадры, торговые системы), внезапный O(n)-скачок - проблема. Поэтому в таких местах либо заранее задают размер таблицы с запасом (чтобы рехеширования не случилось), либо берут структуры с гарантированным худшим случаем (сбалансированные деревья, O(log n) ВСЕГДА - следующий раздел). Понимать это - значит не удивляться, почему «константный» словарь иногда даёт всплеск времени, и знать, когда его нельзя ставить в критичный по задержке путь.

Что ломается без этого

Первая ошибка - не следить за α и дать таблице переполниться: цепочки растут, поиск из O(1) становится O(n), словарь тормозит непонятно почему. Второе - расширять таблицу добавлением ФИКСИРОВАННОГО числа ячеек (m += 1000), а не удвоением: амортизация ломается, вставки в среднем становятся O(n). Третье - рехешируя, забыть ПЕРЕСЧИТАТЬ h(ключ) под новое m: h(k) = k mod m при другом m даёт другой номер, старые индексы недействительны, и просто скопировать ячейки нельзя - надо переразложить каждый ключ. Четвёртое - обещать O(1) на КАЖДУЮ операцию там, где важен худший случай: из-за рехеширования отдельная вставка бывает O(n).

Зачем это в работе

Коэффициент заполнения - то, чем настраивают хеш-таблицу под задачу. Реальные словари (dict в Python, HashMap в Java) сами держат α ниже порога и рехешируют, но знание этого механизма даёт рычаги: если знаешь заранее, сколько будет ключей, - задай начальный размер (dict через нужную ёмкость, HashMap(capacity)), и рехешировок вообще не будет, код станет заметно быстрее на больших вставках. Понимание амортизации объясняет, почему dict в среднем константа, но иногда «дёргается», и подсказывает, где словарь не годится (жёсткие требования к задержке каждой операции). А формула 1 + α объясняет практический совет «не набивай хеш-таблицу под завязку»: разница между α = 0.5 и α = 0.95 - это разница между быстрым и медленным словарём при том же числе ключей. Настройка α - дешёвый способ ускорить код, о котором многие не знают.

Теперь сам

Хеш-таблица с цепочками, m = 1000 ячеек, в неё положили n = 3000 ключей, α = 3. Сколько в среднем проверок займёт поиск, и что делать, чтобы вернуть поиск к O(1)?