Перейти к содержанию

Хеш-таблица меняет память на поиск за почти константное время

Главная мысль: хеш-функция превращает ключ в индекс массива, поэтому поиск, вставка и удаление стоят O(1) в среднем — пока коллизии остаются редкими.

Intro 15 мин чтения algorithms

Что вы сможете делать

  • Объяснить, почему хеш-таблица даёт поиск O(1) в среднем, а список — O(n).
  • Описать, как возникают коллизии, и сравнить цепочки и открытую адресацию.
  • Предсказать, когда хеширование вырождается в O(n) и какие ключи опасно хешировать.
  • Применить хеш-множество/словарь, чтобы заменить вложенный цикл одним проходом.

Требуется знать: массивы, нотация big-O, базовые функции.

Хеш-таблица — это массив, по которому вы индексируете по содержимому, а не по позиции

Чтобы найти значение в неотсортированном массиве, вы просматриваете все элементы: O(n). Хеш-таблица убирает просмотр. Под капотом — массив корзин (buckets) и хеш-функция h(key) -> int. Чтобы сохранить ключ, вы вычисляете i = h(key) % capacity и кладёте его в корзину i; чтобы найти — вычисляете тот же i и идёте прямо туда. Никакого просмотра — вы вычисляете позицию из самого ключа.

В этом весь приём: потратить лишнюю память (пустые корзины), чтобы купить прямой доступ.

Хорошая хеш-функция распределяет ключи равномерно и даёт O(1) в среднем

В массиве capacity корзин и n элементов. Отношение α = n / capacity — коэффициент заполнения (load factor). Если хеш-функция рассеивает ключи равномерно, в каждой корзине примерно α элементов, и поиск затрагивает ~1 + α записей — константа, пока α мал (реальные реализации увеличивают массив, когда α превышает ~0.7).

flowchart LR
    K1["ключ: alice"] -->|h % 5 = 1| B1
    K2["ключ: bob"]   -->|h % 5 = 3| B3
    K3["ключ: carol"] -->|h % 5 = 1| B1
    subgraph Корзины
        B0[0: ·]
        B1[1: alice → carol]
        B2[2: ·]
        B3[3: bob]
        B4[4: ·]
    end

Здесь alice и carol попали в одну корзину — это коллизия. Таблица по-прежнему корректна; в корзине 1 просто небольшой список. Поиск остаётся быстрым именно потому, что при хорошем хеше и низком заполнении коллизии редки.

Коллизии разрешают цепочками или открытой адресацией

Рано или поздно два ключа попадут в одну корзину (принцип Дирихле). Два стандартных решения:

  • Цепочки (separate chaining) — каждая корзина это небольшой список (или дерево). При коллизии — добавляем в конец. Просто, деградирует плавно. Используется в Java HashMap и в концептуальной модели dict в Python.
  • Открытая адресация (open addressing) — один элемент на корзину; при коллизии пробируем следующий свободный слот (линейное/квадратичное пробирование, двойное хеширование). Дружелюбна к кешу, без указателей на запись. Используется в map в Go и в «плоских» хеш-картах C++.

Вот повседневная выгода — свернуть вложенный поиск O(n²) в один проход, запоминая то, что уже видели:

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:      # O(1) average lookup
            return [seen[target - x], i]
        seen[x] = i
    return []

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int, len(nums)) // value -> index
    for i, x := range nums {
        if j, ok := seen[target-x]; ok {  // O(1) average lookup
            return []int{j, i}
        }
        seen[x] = i
    }
    return nil
}

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;        // value -> index
    for (int i = 0; i < (int)nums.size(); ++i) {
        auto it = seen.find(target - nums[i]); // O(1) average lookup
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

Хеширование подводит при плохих хешах, изменяемых ключах и нужде в порядке

O(1) — это среднее, а не гарантия. Три способа всё сломать:

  1. Состязательные / плохие хеши — если много ключей сталкиваются в одну корзину, поиск идёт по длинной цепочке: худший случай O(n). Атаки hash-flooding эксплуатируют ровно это.
  2. Изменяемые ключи — если хеш ключа меняется после вставки (вы изменили ключ), вы уже никогда его не найдёте. Ключи должны быть неизменяемыми и хешируемыми (кортежи в Python — да, списки — нет; в C++/Go тип ключа должен иметь стабильный хеш/равенство).
  3. Нет порядка — у хеш-таблицы нет осмысленного порядка ключей. Нужна отсортированная итерация или запросы по диапазону? Берите сбалансированное дерево (O(log n)), а не хеш-таблицу.

Равенство и хеш обязаны быть согласованы

Если два ключа равны, они обязаны хешироваться одинаково — иначе таблица хранит дубликаты, которые никогда не сведёт воедино. Определяя свой тип ключа, переопределяйте хеш и равенство вместе (__hash__/__eq__, std::hash + operator==, в Go — сравнимая структура).

Проверь себя

Вопрос 1 — Поиск в хеш-таблице всегда O(1)?

Один лучший ответ:

  • A. Да — хеширование константно по определению.
  • B. Да, но только для целочисленных ключей.
  • C. Нет — это O(1) в среднем; плохой хеш или высокое заполнение дают O(n). ← верно
  • D. Нет — это всегда O(log n).

Почему: ✅ C — средний O(1) предполагает равномерное хеширование и ограниченный коэффициент заполнения; свалите всё в одну корзину — и вы идёте по цепочке → O(n). ✗ A путает среднее с гарантией. ✗ B — тип ключа не меняет асимптотику. ✗ D смешивает хеш-таблицы со сбалансированными деревьями.

Вопрос 2 — Что напечатает этот код? 
seen = {}
for x in [3, 3, 3]:
    seen[x] = seen.get(x, 0) + 1
print(len(seen), seen[3])
  • A. 3 1
  • B. 1 3 ← верно
  • C. 3 3
  • D. 1 1

Почему: ✅ B — все три 3 это один и тот же ключ, поэтому запись одна (len == 1), а её счётчик увеличили три раза (seen[3] == 3). ✗ A и ✗ C предполагают, что дубликаты ключей создают отдельные слоты — нет; словарь индексирует по значению/равенству. ✗ D забывает про накопление.

Практика

  • Two Sum — канонический проход «запомни, что видел».
  • Contains Duplicate — хеш-множество как тест на принадлежность.
  • Group Anagrams — хеширование производного ключа (отсортированные буквы / счётчики).
  • Top K Frequent Elements — словарь частот + выборка.

Итог

  • Хеш-таблица индексирует по содержимому: i = h(key) % capacity → прямой доступ.
  • Средний O(1) держится, пока коэффициент заполнения низкий, а хеш равномерный; реализации увеличивают массив, чтобы так и было.
  • Коллизии неизбежны; разрешаем их цепочками или открытой адресацией.
  • Вырождается в O(n) при плохих хешах, ломается с изменяемыми ключами и не хранит порядок — нужен порядок, берите дерево.
  • Главная мысль: меняем память на поиск за почти константное время, пока коллизии редки.

Что почитать дальше

  • Кормен, Лейзерсон, Ривест, Штайн — Алгоритмы: построение и анализ (CLRS), гл. 11 «Хеш-таблицы».
  • Заметки о дизайне dict в CPython — Objects/dictobject.c и «компактный» словарь.
  • Внутренности map в Go: "Macro View of Map Internals" и map на основе Swiss-table.
  • cppreference: std::unordered_map.