🔴 Сложный ⏱️ 50 минут

Хеш-таблицы

📋 Содержание урока

Хеш-таблицы 🔑

Когда ты пишешь user_data["email"] в Python, ответ прилетает мгновенно — независимо от того, три пары ключ-значение хранится в словаре или три миллиона. Это не магия языка и не особенность конкретной реализации CPython, которую можно было бы устроить как-то иначе, — это прямое следствие того, что словарь (dict) внутри устроен как хеш-таблица: структура данных, которая превращает ключ поиска не в «объект, который нужно найти среди прочих», а в адрес, который можно вычислить напрямую. Вместо вопроса «где среди всех этих элементов лежит нужный?» хеш-таблица отвечает на вопрос «по какой формуле вычислить, где он лежит?» — и это отличие превращает поиск из операции, зависящей от размера данных, в операцию, которая в среднем занимает одно и то же время независимо от того, десять там элементов или десять миллионов.

Эта идея — «ключ напрямую в адрес» — не осталась абстрактной темой курса алгоритмов, она прямо встроена в инструментарий, которым ты будешь пользоваться в машинном обучении каждый день. Когда у категориального признака миллионы уникальных значений — идентификаторы пользователей, URL, комбинации редких категорий — держать в памяти полный словарь «значение → индекс» становится дорого или вовсе невозможно, особенно если модель обучается в потоковом режиме и новые значения появляются на лету. Решение называется хешированием признаков (feature hashing, hashing trick): значение признака хешируется напрямую в один из заранее выбранных $m$ индексов, без построения и хранения словаря вообще. А когда ты работаешь с NLP-моделями, таблица эмбеддингов токенов — тот самый слой, который превращает номер токена в его векторное представление, — по сути своей тоже хеш-таблица: «токен → вектор», где поиск нужного вектора обязан выполняться за O(1), потому что он происходит миллиарды раз при обучении и инференсе. Понимание того, как устроена хеш-таблица изнутри, — это понимание того, почему обе эти техники работают и в чём их реальная цена.

В предыдущем уроке ты разобрался со связными списками — структурой, где элементы соединены указателями, а не лежат подряд в памяти. Хеш-таблица использует связные списки не как альтернативу, а как строительный блок: один из двух классических способов разрешения коллизий (метод цепочек) — это в буквальном смысле массив связных списков. Так что этот урок не начинает новую тему с нуля, а показывает, как две уже знакомые тебе структуры — массив (урок 252) и связный список (урок 254) — вместе с одной новой идеей (хеш-функцией) складываются в структуру, которая лежит в основе едва ли не каждой программы, которую ты когда-либо напишешь.

🎯 Ты узнаешь:

  • Как хеш-функция превращает произвольный ключ в индекс массива и почему это даёт поиск, вставку и удаление за O(1) в среднем
  • Что такое коллизия хеш-функции и как её разрешают метод цепочек (chaining) и открытая адресация
  • По каким критериям хеш-функция считается «хорошей»: равномерность распределения, детерминированность, скорость вычисления
  • Как устроены словарь (dict) и множество (set) в Python и почему они быстрее списка при поиске, подсчёте частот и дедупликации
  • Что такое хеширование признаков (feature hashing, hashing trick) и как таблицы эмбеддингов в NLP-моделях используют ту же идею хеш-таблицы «ключ → индекс»

История: откуда это взялось?

В 1953 году инженер компании IBM Ханс Петер Лун (Hans Peter Luhn) — тот самый человек, который несколькими годами позже изобретёт алгоритм контрольной суммы для проверки номеров банковских карт, — столкнулся с практической задачей: как быстро искать записи в огромных бумажных и перфокартных картотеках. Обычный подход — сортировка и последующий бинарный поиск — требовал держать данные упорядоченными, что было дорого при постоянных изменениях. Лун предложил принципиально другую идею, которую он описал во внутренней записке IBM: вместо того чтобы искать запись, перебирая или сравнивая её с другими, можно вычислить адрес, по которому запись должна лежать, прямо из её содержимого. Так родилось хеширование — превращение произвольных данных в число, которое служит адресом.

Практически одновременно, в том же 1953 году, другая группа инженеров IBM — независимо от Луна — предложила решение проблемы, которая неизбежно возникает при таком подходе: что делать, если два разных ключа вычисляют один и тот же адрес? Их ответ — искать следующую свободную ячейку по определённому правилу — стал первой формализацией того, что сегодня называют открытой адресацией. Дональд Кнут, систематизировавший эту область в третьем томе «Искусства программирования», отмечал, что подобная скорость независимого открытия одной и той же идеи в одном и том же году и в одной и той же компании — редкость даже по меркам истории вычислительной техники, и она говорит о том, насколько остро в начале 1950-х стояла задача быстрого поиска в памяти, которая тогда измерялась килобайтами, а не гигабайтами.

С тех пор хеш-таблицы прошли путь от специализированного инженерного трюка до, пожалуй, самой часто используемой структуры данных в программировании. Языки программирования один за другим встраивали хеш-таблицы прямо в ядро: Perl и Python сделали словарь (dict) базовым типом данных, доступным без импорта библиотек; Java, JavaScript, Go, Ruby пошли тем же путём. В самом Python словарь был и остаётся структурой, на которой держится реализация пространств имён, атрибутов объектов и модулей интерпретатора, — когда ты пишешь import numpy, под капотом происходит поиск в хеш-таблице модулей. То, что начиналось как способ ускорить работу с перфокартами, стало фундаментом, на котором построен едва ли не весь современный софт.

Хеш-функция и идея прямого адреса

Интуиция: номерок в гардеробе вместо очереди

Представь два способа организовать гардероб в театре. Первый: все куртки висят подряд на длинной вешалке без всякого порядка, и, чтобы найти свою, гардеробщик должен по очереди осмотреть каждую — в среднем ему придётся проверить половину всех курток. Второй способ: у тебя на руках номерок, скажем 47, и куртка гардеробщика хранится ровно на крючке номер 47 — гардеробщику не нужно ничего искать, он идёт прямо к нужному крючку. Разница между этими двумя способами — ровно та же самая, что разница между линейным поиском по списку и поиском в хеш-таблице: в первом случае ты ищешь, во втором — вычисляешь адрес и идёшь прямо к нему.

Хитрость в том, что у пользователя нет «номерка» заранее — есть только ключ поиска: имя, идентификатор, строка. Хеш-функция — это правило, которое превращает такой ключ в номерок, то есть в индекс ячейки массива, где нужно искать значение. Если у тебя есть массив-хранилище размера $m$ и функция $h$, переводящая любой ключ в число от $0$ до $m-1$, то, чтобы найти значение по ключу, достаточно вычислить $h(\text{ключ})$ и заглянуть в ячейку с этим номером — никакого перебора.

Формальное определение

Определение: Хеш-функция — это функция $h: U \to \{0, 1, \dots, m-1\}$, которая отображает произвольный ключ из универсума возможных ключей $U$ (строки, числа, кортежи и т. п.) в индекс массива размера $m$. Хеш-таблица — структура данных, состоящая из массива-хранилища (бакетов) размера $m$ и хеш-функции $h$; операции вставки, поиска и удаления по ключу выполняются через вычисление $h(\text{ключ})$ и обращение к соответствующей ячейке, что в среднем занимает время $O(1)$ — константное, не зависящее от числа хранимых элементов $n$.

Хорошая хеш-функция должна одновременно удовлетворять трём требованиям. Она обязана быть детерминированной: один и тот же ключ должен всегда давать один и тот же индекс, иначе структуру нельзя будет использовать для поиска — ты не найдёшь то, что сам же туда положил. Она должна быть быстрой: если вычисление $h(\text{ключ})$ занимает столько же времени, сколько занял бы перебор всех элементов, вся идея теряет смысл. И она должна равномерно распределять ключи по всем $m$ ячейкам, а не скапливать их в нескольких, — именно от этого свойства зависит, действительно ли поиск займёт $O(1)$, или же выродится в перебор внутри одной перегруженной ячейки.

Примеры с разбором

Пример 1 (простая модульная хеш-функция). В компании ведётся таблица возрастов сотрудников по числовому идентификатору. Таблица — массив из $m=11$ ячеек, хеш-функция — остаток от деления: $h(k) = k \bmod 11$. Нужно разместить сотрудников с идентификаторами $3$, $15$, $26$ и $40$.

def h(key, m=11):
    return key % m

table = [None] * 11

for employee_id, age in [(3, 28), (15, 34), (26, 41), (40, 25)]:
    index = h(employee_id)
    print(f"id={employee_id} -> индекс {index}")

Вычисляем: $h(3) = 3$, $h(15) = 15 \bmod 11 = 4$, $h(26) = 26 \bmod 11 = 4$, $h(40) = 40 \bmod 11 = 7$. Обрати внимание: идентификаторы $15$ и $26$ дают один и тот же индекс $4$ — это коллизия, ситуация, к которой мы вернёмся в следующем разделе. Уже на этом крошечном примере видно, что вычисление индекса — мгновенная арифметическая операция, не зависящая от того, сколько всего сотрудников в таблице.

Пример 2 (почему сумма кодов символов — плохая хеш-функция для строк). Допустим, для хеширования строк выбрали наивное правило: сложить коды всех символов и взять остаток от деления на размер таблицы.

def naive_hash(s, m=100):
    return sum(ord(c) for c in s) % m

print(naive_hash("кот"))  # сумма кодов букв к, о, т
print(naive_hash("ток"))  # те же буквы, другой порядок

Обе строки состоят из одних и тех же трёх букв, просто переставленных местами, поэтому сумма их кодов совпадает всегда, для любых анаграмм — naive_hash("кот") и naive_hash("ток") дадут одинаковое число, а значит, гарантированную коллизию. Проблема не в конкретных числах, а в самой конструкции: сумма не учитывает порядок символов, а хорошая хеш-функция для строк обязана его учитывать. Реальные хеш-функции (например, полиномиальный хеш $h(s) = \sum_i \mathrm{ord}(s_i) \cdot p^i \bmod m$ с каким-нибудь простым основанием $p$, вроде $31$ или $131$) домножают код каждого символа на разную степень основания в зависимости от его позиции — тогда перестановка символов меняет результат, и анаграммы перестают массово сталкиваться.

Пример 3 (встроенный hash() в Python). В реальности не нужно изобретать хеш-функцию для строк самому — в Python для этого есть встроенная функция hash(), использующая внутри алгоритм SipHash, специально спроектированный так, чтобы результат было трудно предсказать и подобрать коллизию намеренно.

m = 8
for key in ["Москва", "Питер", "Казань"]:
    print(key, "->", hash(key) % m)

Каждый запуск этого кода в новом процессе Python, скорее всего, даст разные числа для одних и тех же строк — потому что начиная с Python 3.3 интерпретатор случайным образом «подсаливает» хеш-функцию строк при каждом запуске (об этом подробнее — в разделе про интересные факты). Зато внутри одного запущенного процесса hash("Москва") всегда возвращает одно и то же число — детерминированность сохраняется там, где она действительно нужна: пока программа работает, один и тот же ключ всегда попадёт в одну и ту же ячейку.

Почему это важно. Всё, что делает хеш-таблицу быстрой, держится на качестве хеш-функции. Если функция вычисляется быстро и равномерно распределяет ключи, вставка, поиск и удаление в среднем занимают $O(1)$ — константное время, не растущее с размером данных, и именно поэтому dict в Python работает одинаково быстро что на сотне записей, что на десяти миллионах. Но если функция плохая — например, все ключи схлопываются в одну ячейку, как в примере с суммой кодов символов, — хеш-таблица вырождается в обычный список с лишними накладными расходами, и та же операция превращается в $O(n)$. Ниже мы разберём, что делать, когда несколько разных ключей всё-таки претендуют на одну ячейку, — это неизбежно даже для хорошей хеш-функции.

Коллизии и метод цепочек

Интуиция: два письма в один почтовый ящик

Даже самая аккуратная почтовая система рано или поздно столкнётся с ситуацией, когда два разных письма нужно доставить в один и тот же почтовый ящик — просто потому, что ящиков меньше, чем потенциальных адресатов. Ровно то же самое неизбежно для хеш-таблицы: если ключей потенциально бесконечно много (все возможные строки, все возможные числа), а ячеек в таблице — конечное число $m$, то по принципу Дирихле (если голубей больше, чем клеток, хотя бы в одной клетке окажется больше одного голубя) рано или поздно два разных ключа получат один и тот же индекс. Это называется коллизией, и хорошая хеш-функция не устраняет коллизии полностью — она лишь делает их редкими и равномерно распределёнными, а не концентрирующимися в нескольких ячейках.

Первое и самое простое решение — не пытаться втиснуть оба значения в одну ячейку, а превратить каждую ячейку из одного слота в маленький контейнер, способный хранить несколько элементов. Этот контейнер — обычный связный список: если два ключа коллизируют, оба узла просто добавляются в список, растущий из этой ячейки.

Формальное определение

Определение: Коллизия — ситуация, при которой два разных ключа $k_1 \neq k_2$ дают одинаковое значение хеш-функции: $h(k_1) = h(k_2)$. Метод цепочек (chaining) — способ разрешения коллизий, при котором каждая ячейка массива хеш-таблицы хранит не одно значение, а связный список (или иную коллекцию) всех пар «ключ-значение», чей хеш указывает на эту ячейку; при коллизии новый элемент просто добавляется в список соответствующей ячейки.

Примеры с разбором

Пример 1 (продолжение примера про сотрудников). В примере из предыдущего раздела идентификаторы $15$ и $26$ дали одинаковый индекс $4$ в таблице размера $m=11$. С методом цепочек ячейка $4$ превращается в список из двух пар:

table = [[] for _ in range(11)]

def h(key, m=11):
    return key % m

def insert(table, key, value):
    index = h(key, len(table))
    table[index].append((key, value))

for employee_id, age in [(3, 28), (15, 34), (26, 41), (40, 25)]:
    insert(table, employee_id, age)

print(table[4])  # [(15, 34), (26, 41)] — оба элемента в одной ячейке

Поиск сотрудника с идентификатором $26$ теперь работает так: вычислить $h(26)=4$, попасть в ячейку $4$, а дальше пройти по короткому списку [(15, 34), (26, 41)], сравнивая ключи, пока не найдётся нужный. Если бы вся таблица целиком превратилась в один длинный связный список (например, при совсем плохой хеш-функции), поиск деградировал бы до $O(n)$ — но пока цепочки короткие, лишний шаг сравнения внутри списка почти не сказывается на скорости.

Пример 2 (load factor и средняя длина цепочки). Пусть таблица имеет $m=8$ ячеек, и в неё вставили $n=20$ ключей. Величина $\alpha = n / m$ называется коэффициентом загрузки (load factor) и показывает, сколько элементов в среднем приходится на одну ячейку:

$$\alpha = \frac{20}{8} = 2{,}5.$$

При равномерном распределении ключей это означает, что типичная цепочка содержит около $2$–$3$ элементов, а не $20$: поиск по-прежнему требует сравнить лишь пару элементов внутри своей ячейки, а не перебрать всю таблицу. Средняя сложность поиска при методе цепочек оценивается как $O(1 + \alpha)$ — единица за вычисление хеша плюс $\alpha$ за проход по цепочке. Именно поэтому реальные реализации хеш-таблиц (включая dict в Python) следят за коэффициентом загрузки и автоматически увеличивают размер внутреннего массива (пересчитывая все хеши заново — эта операция называется rehashing), когда $\alpha$ превышает определённый порог, чтобы цепочки не разрастались.

Пример 3 (полноценная реализация хеш-таблицы с цепочками). Соберём класс, поддерживающий вставку, поиск и удаление, — обрати внимание, что бакеты используют структуру, буквально идентичную связному списку из прошлого урока, только упрощённую до списка Python:

class HashTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)  # обновление
                return
        self.buckets[index].append((key, value))

    def search(self, key):
        index = self._hash(key)
        for k, v in self.buckets[index]:
            if k == key:
                return v
        raise KeyError(key)

    def delete(self, key):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                del self.buckets[index][i]
                return
        raise KeyError(key)

table = HashTable()
table.insert("Аня", 19)
table.insert("Петя", 20)
print(table.search("Аня"))   # 19
table.delete("Аня")

Этот код — упрощённая, но полностью рабочая модель того, как устроен dict в большинстве языков программирования до появления более тонких оптимизаций: вставка и поиск проверяют равенство ключей внутри списка ровно потому, что одинаковый хеш ещё не гарантирует одинаковый ключ — сравнение через == остаётся обязательным последним шагом.

Почему это важно. Метод цепочек — прямое практическое применение связных списков из предыдущего урока: без понимания того, как узел ссылается на следующий, невозможно понять, что происходит внутри «перегруженной» ячейки хеш-таблицы. Плюс метода цепочек в том, что он никогда не «переполняется» — таблица просто позволяет цепочкам расти, деградируя постепенно, а не ломаясь резко. Минус — дополнительная память на хранение указателей и более плохая работа с процессорным кешем, потому что элементы одной цепочки разбросаны по памяти, а не лежат подряд, — об этом подробнее в следующем разделе.

Открытая адресация: коротко о втором способе

Интуиция: свободные места в зрительном зале

Представь, что у каждого зрителя есть предпочитаемое место в зале, но если оно занято, он не строит очередь возле этого кресла, а сам идёт искать следующее свободное — сначала соседнее, потом следующее, и так далее, пока не найдёт свободное место и не сядет прямо в него. Это и есть суть открытой адресации: в отличие от метода цепочек, где несколько элементов уживаются в одной ячейке за счёт дополнительной структуры (списка), при открытой адресации в каждой ячейке массива хранится не более одного элемента — при коллизии ищется следующая свободная ячейка по заранее определённому правилу (правилу пробирования).

Определение: Открытая адресация — способ разрешения коллизий, при котором все элементы хранятся непосредственно в массиве хеш-таблицы, по одному на ячейку; при коллизии выполняется последовательность проб (probing sequence) $h_0(k), h_1(k), h_2(k), \dots$ до тех пор, пока не будет найдена свободная ячейка. Простейший вариант — линейное пробирование: $h_i(k) = (h(k) + i) \bmod m$, то есть при занятости ячейки проверяется следующая по порядку.

Примеры с разбором

Пример 1 (линейное пробирование и эффект кластеризации). Таблица размера $m=7$, хеш-функция $h(k) = k \bmod 7$. Вставляем по очереди ключи $9$, $16$, $23$.

$h(9) = 9 \bmod 7 = 2$ — ячейка $2$ свободна, кладём туда. $h(16) = 16 \bmod 7 = 2$ — занята, пробуем $h_1(16) = (2+1) \bmod 7 = 3$ — свободна, кладём туда. $h(23) = 23 \bmod 7 = 2$ — занята, пробуем $3$ — тоже занята, пробуем $h_2(23) = (2+2)\bmod 7 = 4$ — свободна, кладём туда. Все три ключа, несмотря на разные значения, скопились подряд в ячейках $2$, $3$, $4$ — это называется первичной кластеризацией: как только образуется занятый «остров», он притягивает к себе всё новые коллизии, потому что любой ключ, чей хеш попадает в этот диапазон, вынужден пробираться сквозь весь остров целиком.

Пример 2 (проблема удаления и «надгробия»). Если из таблицы выше просто удалить ключ $16$ из ячейки $3$, обычным способом обнулив её, поиск ключа $23$ сломается: алгоритм поиска вычислит $h(23)=2$, увидит, что она занята не тем ключом, перейдёт к ячейке $3$ — а она теперь пуста — и ошибочно решит, что ключа $23$ в таблице нет, хотя он всё ещё лежит в ячейке $4$. Решение — не очищать ячейку по-настоящему, а помечать её специальным маркером-«надгробием» (tombstone), который говорит поиску «здесь было занято, продолжай пробирование», но говорит вставке «сюда можно класть новый элемент»:

DELETED = object()  # специальный маркер-надгробие

def search(table, key, h):
    m = len(table)
    i = h(key) % m
    start = i
    while table[i] is not None:
        if table[i] is not DELETED and table[i][0] == key:
            return table[i][1]
        i = (i + 1) % m
        if i == start:
            break
    return None

Пример 3 (альтернативы линейному пробированию). Чтобы уменьшить кластеризацию, придуманы более хитрые последовательности проб: квадратичное пробирование ($h_i(k) = (h(k) + i^2) \bmod m$ — шаг растёт квадратично, что разбивает длинные «острова») и двойное хеширование ($h_i(k) = (h_1(k) + i \cdot h_2(k)) \bmod m$ — используются сразу две независимые хеш-функции, что делает последовательность проб для разных ключей практически непохожей). Любопытный технический факт: сам dict в CPython внутри использует именно открытую адресацию, а не метод цепочек — с дополнительной хитрой псевдослучайной последовательностью проб (не строго линейной и не строго квадратичной), которая специально спроектирована так, чтобы избегать длинных кластеров даже в неудачных случаях.

Почему это важно. Открытая адресация экономит память (не нужны указатели на узлы списков) и лучше работает с процессорным кешем: все элементы лежат подряд в одном массиве, а не разбросаны по памяти, как при методе цепочек, — а последовательный доступ к памяти на современных процессорах на порядок быстрее случайного. Именно поэтому открытую адресацию выбирают там, где важна сырая скорость и предсказуемое использование памяти, — например, во внутренней реализации dict и set в Python и в таблицах хешей многих баз данных и кешей в оперативной памяти, включая сценарии из мира машинного обучения, где приходится хешировать миллионы категориальных значений признаков за доли секунды.

Словарь Python как хеш-таблица: практические применения

Интуиция: умный органайзер вместо ящика с бумагами

Список (list) в Python — это ящик, куда вещи складываются подряд: чтобы найти нужную, приходится доставать одну за другой. Словарь (dict) — это органайзер с подписанными отделениями: у каждой вещи есть бирка (ключ), и, чтобы найти вещь, достаточно посмотреть в отделение с нужной биркой, не трогая остальные. Внутри dict устроен ровно так, как описано в этом уроке: массив ячеек плюс хеш-функция (плюс открытая адресация для разрешения коллизий) — и всё это скрыто за удобным синтаксисом словарь[ключ].

Определение: dict в Python — встроенная реализация хеш-таблицы: операции получения, установки и удаления значения по ключу (d[key], d[key] = value, del d[key]) выполняются в среднем за $O(1)$. Ключом может быть только неизменяемый (hashable) объект — число, строка, кортеж из неизменяемых элементов, — потому что хеш ключа не должен меняться, пока объект лежит в таблице. Тип set устроен так же, как dict, только без хранения значений — это хеш-таблица одних ключей, используемая для проверки принадлежности и удаления дубликатов.

Примеры с разбором

Пример 1 (поиск в списке против поиска в словаре). Пусть нужно быстро проверять, зарегистрирован ли пользователь по его идентификатору, среди миллиона записей.

user_ids_list = list(range(1_000_000))       # O(n) на каждую проверку "in"
user_ids_set = set(range(1_000_000))          # O(1) на каждую проверку "in"

print(999_999 in user_ids_list)  # в худшем случае — миллион сравнений
print(999_999 in user_ids_set)   # один вызов хеш-функции и переход к ячейке

Для list оператор in в худшем случае перебирает все элементы по очереди — сложность $O(n)$. Для set (той же хеш-таблицы, что и dict, только без значений) оператор in вычисляет хеш искомого числа и сразу заглядывает в нужную ячейку — сложность $O(1)$ в среднем. При миллионе элементов и тысячах таких проверок в цикле разница между секундами и долями секунды становится вполне ощутимой на практике, а не только в теоретической оценке.

Пример 2 (подсчёт частот). Классическая задача — посчитать, сколько раз каждое слово встречается в тексте.

text = "кот сидит на окне кот смотрит на птицу кот доволен"
words = text.split()

frequency = {}
for word in words:
    frequency[word] = frequency.get(word, 0) + 1

print(frequency)  # {'кот': 3, 'сидит': 1, 'на': 2, 'окне': 1, ...}

from collections import Counter
frequency_fast = Counter(words)
print(frequency_fast.most_common(2))  # [('кот', 3), ('на', 2)]

Метод .get(word, 0) за одно обращение к хеш-таблице либо возвращает уже накопленный счётчик, либо ноль, если слово встретилось впервые, — и то и другое занимает $O(1)$. collections.Counter — это подкласс dict, написанный специально под задачу подсчёта, с удобным методом .most_common(), но по сути выполняющий ту же самую операцию инкремента значения по ключу за $O(1)$.

Пример 3 (дедупликация). Нужно убрать повторяющиеся идентификаторы пользователей из списка логов.

user_log = [42, 17, 42, 8, 17, 99, 42]

unique_unordered = set(user_log)               # {8, 99, 17, 42} — порядок не гарантирован
unique_ordered = list(dict.fromkeys(user_log))  # [42, 17, 8, 99] — порядок вставки сохранён

print(unique_unordered)
print(unique_ordered)

set(user_log) строит хеш-таблицу из элементов списка, автоматически отбрасывая повторы, — потому что в множестве по определению не может быть двух одинаковых ключей: при попытке вставить уже существующий ключ ничего не происходит. dict.fromkeys(user_log) использует то же свойство, но, поскольку современный dict (начиная с Python 3.7) сохраняет порядок вставки, результат оказывается ещё и упорядоченным ровно так же, как исходный список, только без повторов, — трюк, который на практике удобнее прямого использования set, когда порядок важен.

Почему это важно. Быстрая проверка принадлежности, подсчёт частот и дедупликация — это, пожалуй, три самые частые операции в подготовке данных для машинного обучения: проверка, встречался ли уже такой объект (кеш вычислений, дедупликация обучающей выборки), построение словаря частот категорий или слов (первый шаг почти любого текстового пайплайна), устранение дубликатов записей перед обучением модели. Понимание, что всё это работает быстро именно потому, что dict и set — хеш-таблицы, а не потому что «Python оптимизированный», помогает вовремя заметить момент, когда код случайно откатывается к $O(n)$-поиску по списку там, где должен использоваться словарь или множество.

Хеш-таблицы в машинном обучении: хеширование признаков и эмбеддинги

Интуиция: адрес вместо картотеки

Обычный подход к превращению категориального признака в число — завести словарь «значение → индекс»: первое встреченное значение получает индекс $0$, второе — $1$, и так далее, а словарь растёт вместе с данными. Это прекрасно работает, пока уникальных значений тысячи. Но если признак — идентификатор пользователя интернет-магазина, URL посещённой страницы или комбинация нескольких категориальных полей сразу, число уникальных значений может исчисляться сотнями миллионов, и держать полный словарь в памяти становится дорого, а иногда и вовсе невозможно — особенно если модель обучается на потоке данных и заранее неизвестно, какие значения ещё появятся. Хеширование признаков решает эту проблему тем же способом, каким хеш-таблица решает задачу поиска: вместо хранения соответствия «значение → индекс» индекс просто вычисляется напрямую хеш-функцией.

Определение: Хеширование признаков (feature hashing, hashing trick) — техника кодирования категориальных признаков, при которой каждое значение признака хешируется напрямую в один из $m$ заранее фиксированных индексов вектора ($h(\text{значение}) \bmod m$), без явного построения и хранения словаря «значение → индекс»; размер $m$ не растёт с числом уникальных значений признака и задаётся заранее.

Примеры с разбором

Пример 1 (хеширование категорий вручную). Есть категориальный признак «город» с потенциально огромным числом уникальных значений. Вместо словаря используем фиксированный вектор из $m=4$ ячеек.

def feature_hash(value, m=4):
    return hash(value) % m

cities = ["Москва", "Питер", "Казань", "Москва", "Новосибирск"]
vector = [0] * 4

for city in cities:
    index = feature_hash(city)
    vector[index] += 1

print(vector)  # например, [2, 0, 1, 2] — счётчики по хеш-бакетам

Ни один из городов не хранится в памяти явно — вектор просто накапливает счётчики попаданий в каждый из четырёх бакетов, а сам список возможных городов нигде не сохраняется. Если два разных города случайно попадут в один и тот же бакет (то есть произойдёт коллизия — как в разделе про коллизии выше, только теперь она называется hash collision в feature hashing), модель просто не сможет их различить по этому признаку — это осознанная плата за постоянный, заранее известный размер вектора.

Пример 2 (библиотечная реализация). В scikit-learn та же идея доступна из коробки:

from sklearn.feature_extraction import FeatureHasher

hasher = FeatureHasher(n_features=8, input_type="string")
rows = [["Москва", "категория_A"], ["Питер", "категория_B"]]
matrix = hasher.transform(rows)

print(matrix.toarray())  # разреженная матрица 2x8, без единого словаря внутри

FeatureHasher не строит и не хранит внутри себя список встреченных строк — при каждом вызове transform он заново хеширует переданные значения в те же самые $8$ индексов, поэтому одно и то же значение всегда попадёт в одну и ту же позицию вектора, а память, занимаемая преобразователем, не растёт независимо от того, обработал он тысячу строк или миллиард.

Пример 3 (таблица эмбеддингов — тоже хеш-таблица). В NLP-модели слой эмбеддингов хранит для каждого токена вектор фиксированной длины — обычно это просто матрица размера (размер словаря) × (размерность вектора), а номер токена служит индексом строки:

import torch

vocab_size, embedding_dim = 50_000, 300
embedding_table = torch.nn.Embedding(vocab_size, embedding_dim)

token_id = 1234
vector = embedding_table(torch.tensor([token_id]))  # мгновенный доступ к строке 1234

Это прямое обращение по индексу — то есть в точности та же операция $O(1)$, вокруг которой построен весь урок, только «хеш-функцией» здесь служит словарь токенов (токен → его номер), построенный заранее на этапе токенизации. Когда словарь токенов сам оказывается неприемлемо большим — например, в рекомендательных системах, где «токенами» служат идентификаторы товаров или пользователей, которых сотни миллионов, — инженеры применяют хешированные эмбеддинги: вместо словаря «id → номер строки» индекс строки вычисляется напрямую, hash(user_id) % table_size, ровно как в feature hashing выше. Так объём таблицы эмбеддингов перестаёт зависеть от числа уникальных пользователей и определяется только выбранным размером таблицы — за счёт допущения, что часть пользователей поделит одну строку (и, соответственно, один и тот же вектор) с кем-то ещё.

Почему это важно. Хеширование признаков (feature hashing) и хешированные эмбеддинги — это не отдельный трюк, а прямое применение всего, что разобрано в этом уроке, доведённое до предела: если обычная хеш-таблица хранит ключи явно и просто ускоряет доступ к ним, то feature hashing идёт на шаг дальше и вовсе отказывается хранить ключи, оставляя только вычисляемый адрес. Плата за это — управляемый риск коллизий, точно такой же, как в обычной хеш-таблице с методом цепочек или открытой адресацией, только вместо связного списка или пробирования цена коллизии здесь — потеря различимости между двумя разными категориями. Понимание этого компромисса — прямая причина, почему в реальных ML-системах размер хеш-таблицы признаков или эмбеддингов выбирают осознанно, а не наугад.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Вычисли индекс для ключа $k=23$ в хеш-таблице размера $m=7$ по формуле $h(k) = k \bmod m$.

Задание 2. Хеш-функция для строк — сумма кодов символов по модулю $5$. Вычисли хеш строки "AB", если $\mathrm{ord}(\text{'A'})=65$, $\mathrm{ord}(\text{'B'})=66$.

Задание 3. В хеш-таблице размера $m=10$ хешируются четыре ключа, и получены индексы $3$, $6$, $3$, $9$. Сколько коллизий произошло и в какой ячейке?

Задание 4. В хеш-таблице методом цепочек размещено $12$ элементов в массиве из $8$ ячеек. Найди коэффициент загрузки (load factor).

Задание 5. Дан массив бакетов метода цепочек buckets = [[], [], []]. Хеш ключа "x" равен $1$. Опиши, как изменится массив после вставки пары ("x", 100).

Задание 6. Два ключа "a" и "b" дают одинаковый хеш $2$ в таблице методом цепочек размера $m=5$. После вставки обоих в пустую таблицу, что будет храниться в buckets[2]?

Задание 7. Сравни среднюю и худшую временную сложность поиска элемента в хеш-таблице.

Задание 8. Верно ли утверждение: «хеш-функция для хеш-таблицы обязана быть недетерминированной, чтобы данные распределялись более случайно»? Обоснуй ответ.

Задание 9. Можно ли использовать список (list) Python как ключ словаря? Объясни, почему да или почему нет.

Задание 10. Какая структура данных используется внутри одной ячейки (бакета) при методе цепочек и как это связано с материалом предыдущего урока?

Средние (задания 11–20)

Задание 11. Напиши функцию insert, добавляющую пару «ключ-значение» в хеш-таблицу с методом цепочек, представленную как список списков buckets, с обновлением значения, если ключ уже существует.

Задание 12. В таблице методом цепочек $m=6$ ячеек, всего вставлено $n=15$ ключей равномерно. Оцени среднюю длину одной цепочки и среднюю сложность поиска.

Задание 13. Таблица открытой адресации размера $m=5$, линейное пробирование, $h(k)=k \bmod 5$. Вставь по очереди ключи $12$, $17$, $7$ и укажи итоговые индексы.

Задание 14. Дан список идентификаторов с повторами [5, 2, 5, 8, 2, 9]. Напиши код, который удаляет дубликаты, сохраняя исходный порядок первого появления.

Задание 15. Посчитай частоту слов в строке "дождь идёт дождь льёт дождь стучит" с помощью словаря.

Задание 16. Категориальный признак «страна» хешируется в $m=4$ бакета функцией $h(v) = \mathrm{len}(v) \bmod 4$ (длина строки по модулю $4$, для простоты примера). Распредели значения "Россия", "США", "Китай", "Индия" по бакетам и укажи, где произошли коллизии.

Задание 17. Список из $10^6$ элементов используется для проверки принадлежности x in lst в цикле из $10^3$ повторений. Оцени порядок числа операций сравнения для list и для set, при условии, что искомый элемент отсутствует.

Задание 18. Объясни техническую причину, по которой ключ хеш-таблицы должен быть неизменяемым объектом, если рассуждать не про Python конкретно, а про принцип устройства хеш-таблицы вообще.

Задание 19. Таблица открытой адресации содержит $16$ ячеек, из них занято $12$. Порог для расширения (rehashing) — коэффициент загрузки $0{,}7$. Нужно ли расширять таблицу сейчас? Если да, до какого размера при удвоении?

Задание 20. Полный словарь эмбеддингов на $V=50\,000$ токенов с размерностью вектора $d=300$ хранится как числа типа float32 (4 байта). Хешированная альтернатива использует таблицу на $m=8192$ бакета той же размерности. Сравни объём памяти обоих вариантов.

Продвинутые (задания 21–30)

Задание 21. Реализуй метод delete для класса HashTable с методом цепочек, корректно удаляющий нужную пару из соответствующего бакета.

Задание 22. Реализуй функции insert и search для хеш-таблицы с линейным пробированием на массиве фиксированного размера.

Задание 23. По приближённой формуле среднего числа проб при линейном пробировании для успешного поиска $\approx \dfrac{1}{2}\left(1 + \dfrac{1}{1-\alpha}\right)$ сравни ожидаемое число проб при $\alpha = 0{,}5$ и при $\alpha = 0{,}9$.

Задание 24. В рекомендательной системе $n=10\,000\,000$ идентификаторов пользователей хешируются в таблицу эмбеддингов размера $m = 2^{20} = 1\,048\,576$ строк. Найди среднее число пользователей, приходящихся на одну строку таблицы.

Задание 25. Опиши, что такое алгоритмическая атака на хеш-таблицу (algorithmic complexity attack), и как Python защищается от неё по умолчанию.

Задание 26. Используя collections.Counter, найди самое частое слово в строке "тест тест данные тест данные модель" и объясни, какая операция хеш-таблицы стоит за подсчётом.

Задание 27. Сравни поиск дубликатов в массиве из миллиона строк наивным способом (двойной цикл со сравнением каждой пары) и через set. Оцени порядок числа операций для обоих подходов.

Задание 28. В NLP-модели с хешированными эмбеддингами два редких, но семантически разных токена коллизируют в одну строку таблицы. Опиши, как это повлияет на качество модели, и почему это иная цена, чем полный отказ от учёта редких токенов вовсе.

Задание 29. Напиши функцию hash_encode, которая превращает столбец категориальных значений (список строк) в список индексов фиксированного диапазона $[0, m)$ с помощью хеширования признаков.

Задание 30. Опиши по шагам весь путь одного обращения словарь[ключ] в Python — от вызова до возврата значения — и объясни, почему тот же самый механизм критичен для производительности ML-пайплайна, в котором такое обращение выполняется миллиарды раз.

Частые ошибки

❌ Ошибка: «Хеш-таблица всегда работает за $O(1)$, это гарантия, а не оценка» ✅ Правильно: $O(1)$ — это средняя (амортизированная) сложность при хорошей хеш-функции и разумном коэффициенте загрузки; в худшем случае — при плохой хеш-функции или намеренной атаке — сложность деградирует до $O(n)$ 💡 Почему: как показано в задании 25, специально подобранные ключи могут схлопнуть все операции в одну цепочку, превратив $n$ вставок из $O(n)$ в $O(n^2)$ суммарно — именно поэтому Python рандомизирует хеш строк между запусками.

❌ Ошибка: «Одинаковый хеш двух ключей означает, что это один и тот же ключ» ✅ Правильно: совпадение хешей — это лишь необходимое, но не достаточное условие; реализация хеш-таблицы обязательно сравнивает сами ключи через == внутри бакета или на этапе пробирования 💡 Почему: без финальной проверки равенства ключей две коллизирующие, но разные записи (как "кот" и "ток" в примере из первого раздела) перепутались бы местами.

❌ Ошибка: «Можно использовать список или другой изменяемый объект как ключ словаря, если он пока не менялся» ✅ Правильно: ключом может быть только неизменяемый (hashable) тип — число, строка, кортеж из неизменяемых элементов; список, словарь и множество ключами быть не могут 💡 Почему: как разобрано в задании 18, хеш ключа вычисляется один раз при вставке и определяет место хранения — изменение ключа после вставки сделало бы элемент недостижимым для поиска.

❌ Ошибка: «Хеш-таблица — это структура без всякого порядка, dict в Python принципиально не может сохранять порядок вставки» ✅ Правильно: начиная с Python 3.7 сохранение порядка вставки в dict — гарантированная особенность языка, реализованная через дополнительный компактный массив поверх обычной хеш-таблицы 💡 Почему: это не свойство хеш-таблиц вообще (хеш-таблица как абстрактная структура порядок не хранит), а конкретная инженерная надстройка CPython — полезно понимать разницу между общим принципом и деталями одной реализации.

❌ Ошибка: «Чем сложнее и «крипто-надёжнее» хеш-функция, тем лучше подходит для хеш-таблицы» ✅ Правильно: для хеш-таблиц важны скорость вычисления и равномерность распределения, а не криптографическая стойкость к подбору обратного значения — использование SHA-256 вместо SipHash или простого модульного хеша сделало бы каждую операцию dict[key] заметно медленнее без выигрыша в качестве поиска 💡 Почему: криптографические хеш-функции спроектированы под другую задачу (невозможность подделки или обращения хеша), а для таблицы важны только скорость и равномерность — это разные, хотя и смежные, инженерные требования.

❌ Ошибка: «При хешировании признаков (feature hashing) коллизии — это баг, который нужно полностью устранить» ✅ Правильно: коллизии при хешировании признаков — осознанный и управляемый компромисс между размером таблицы (памятью) и точностью различения категорий, а не ошибка реализации 💡 Почему: как показано в задании 24, при фиксированном размере таблицы эмбеддингов и растущем числе уникальных значений признака коллизии неизбежны математически — вопрос не «есть коллизии или нет», а «достаточно ли редки коллизии при выбранном размере таблицы $m$».

Главное запомнить

✅ Хеш-таблица — массив ячеек плюс хеш-функция: ключ превращается в индекс, по индексу выполняется прямой доступ к значению за $O(1)$ в среднем

✅ Хорошая хеш-функция должна быть детерминированной, быстрой и равномерно распределять ключи по ячейкам — от последнего свойства напрямую зависит, останется ли поиск константным или деградирует

✅ Коллизия ($h(k_1)=h(k_2)$ при $k_1 \neq k_2$) неизбежна при достаточном числе ключей (принцип Дирихле) — вопрос не в том, произойдёт ли она, а в том, как часто и как её разрешать

✅ Метод цепочек хранит в каждой ячейке связный список всех коллизирующих пар — прямое практическое применение связных списков из урока 254; сложность поиска растёт как $O(1+\alpha)$, где $\alpha=n/m$ — коэффициент загрузки

✅ Открытая адресация хранит все элементы прямо в массиве, при коллизии пробируя следующие ячейки по правилу (линейно, квадратично или через двойное хеширование); экономит память и дружелюбнее к процессорному кешу, но требует «надгробий» при удалении

✅ При росте коэффициента загрузки выше порога хеш-таблица выполняет rehashing — расширение массива и пересчёт всех хешей заново

✅ dict и set в Python — встроенные хеш-таблицы; ключи обязаны быть неизменяемыми (hashable); с версии 3.7 dict гарантированно сохраняет порядок вставки

✅ Хеширование признаков (feature hashing, hashing trick) отображает категориальный признак напрямую в фиксированный индекс без хранения словаря «значение → индекс» — критично для признаков с огромной или заранее неизвестной кардинальностью

✅ Таблица эмбеддингов в NLP-моделях — это хеш-таблица «токен → вектор»; при сверхбольших словарях (пользователи, товары) применяют хешированные эмбеддинги, платя управляемым риском коллизий за постоянный объём памяти

✅ Худший случай сложности хеш-таблицы — $O(n)$, а не $O(1)$: это происходит при плохой хеш-функции или при намеренной алгоритмической атаке, от которой Python защищается рандомизацией хеша строк

Связь с темами курса

🔙 Откуда пришли: массивы (урок 252) — хеш-таблица хранит данные именно в массиве, обеспечивая доступ по индексу за $O(1)$; связные списки (урок 254) — прямая реализация бакетов при методе цепочек; сложность алгоритмов (урок 251) — язык $O(1)$/$O(n)$, на котором формулируется вся выгода и все риски хеш-таблиц.

🔜 Куда идём:

  • Деревья (уроки 256–258) — альтернативная структура для случаев, когда важен порядок ключей (диапазонные запросы, «найти все значения между X и Y»), с которым хеш-таблица, в отличие от дерева, в принципе не работает
  • Графы (урок 259 и далее) — списки смежности графа на практике почти всегда реализуются как словари (хеш-таблицы) «вершина → список соседей»
  • Деревья поиска и сбалансированные деревья — сравнение $O(\log n)$ гарантированного худшего случая против $O(1)$ среднего, но $O(n)$ худшего случая хеш-таблицы — выбор между ними зависит от того, что важнее: скорость в среднем или предсказуемость в худшем случае

🎯 В машинном обучении: кодирование категориальных признаков (label encoding, ordinal encoding строятся на словарях «значение → индекс»), хеширование признаков (feature hashing, hashing trick) для признаков высокой кардинальности, таблицы эмбеддингов токенов, пользователей и товаров в NLP- и рекомендательных моделях, мемоизация (кеширование результатов дорогих вычислений по ключу входных данных), дедупликация обучающих выборок через set, построение индексов в базах данных, из которых читаются обучающие данные.

Интересные факты

📌 Ханс Петер Лун, придумавший идею хеширования в 1953 году, известен ещё и как изобретатель контрольной суммы номеров банковских карт (алгоритм Луна) и одного из первых алгоритмов автоматического реферирования текста — то есть один и тот же человек стоял у истоков и структур данных, и текстовой аналитики, которыми сегодня активно пользуется машинное обучение.

📌 Открытая адресация была предложена независимо от Луна и в том же 1953 году другой группой инженеров IBM — Дональд Кнут в третьем томе «Искусства программирования» называет это совпадение одним из самых быстрых случаев параллельного изобретения одной и той же идеи в истории вычислительной техники.

📌 Начиная с Python 3.3 хеш строк и байтов рандомизируется при каждом запуске интерпретатора (управляется переменной окружения PYTHONHASHSEED) — это защита от алгоритмических атак типа «отказ в обслуживании» (задание 25), при которых злоумышленник специально подбирает данные, вызывающие массовые коллизии в хеш-таблицах веб-сервиса.

📌 С версии Python 3.6 (и как гарантия языка — с 3.7) словарь стал «компактным»: вместо одного большого разреженного массива хеш-таблица хранит компактный плотный массив записей и отдельно — компактную таблицу индексов в этот массив, что одновременно экономит память и даёт сохранение порядка вставки в качестве побочного эффекта нового внутреннего устройства.

Лайфхаки

💡 Если тебе нужно быстро проверять принадлежность элемента коллекции — используй set, а не list. Переход с $O(n)$ на $O(1)$ окупается уже на тысячах элементов, а на миллионах разница измеряется не процентами, а порядками, как в задании 17.

💡 Для подсчёта частот сразу используй collections.Counter вместо ручной связки dict и if/else — он короче, читаемее и предоставляет готовый метод .most_common(), который иначе пришлось бы писать самому.

💡 Не изобретай собственную хеш-функцию для реальных задач — используй встроенный hash() Python или проверенные библиотечные алгоритмы (SipHash, MurmurHash, xxHash). Они уже проверены сообществом на равномерность распределения и устойчивость к атакам, чего сложно добиться самодельной формулой вроде «суммы кодов символов» из примера 2.

💡 При работе с категориальным признаком, у которого потенциально миллионы уникальных значений (ID пользователя, URL, IP-адрес), сразу задумывайся о sklearn.feature_extraction.FeatureHasher или аналоге вместо построения полного словаря «значение → индекс» — это спасает и память, и работает даже в потоковом обучении, когда полный список значений заранее неизвестен.

💡 Если тебе нужен упорядоченный по вставке словарь — не усложняй код через OrderedDict: обычный dict в современном Python (3.7+) уже гарантированно сохраняет порядок вставки; OrderedDict стоит доставать только ради его специфичных методов вроде move_to_end.

💡 При отладке неожиданно медленного кода на больших данных в первую очередь проверь: не превратился ли где-то по пути твой быстрый set или dict обратно в list — например, после .keys() и последующего приведения к списку, потому что операция in над списком снова становится $O(n)$, сводя на нет весь выигрыш от хеш-таблицы.

Каждый раз, когда код обращается к словарю квадратными скобками, происходит ровно то, что разобрано в этом уроке: ключ превращается в адрес, и это превращение — не деталь реализации, а фундаментальная идея, которая перекочевала из бумажных картотек IBM пятидесятых годов прямо в ядро языков программирования и в архитектуру современных моделей машинного обучения. Как только эта идея закреплена — хеш-функция, коллизии, метод цепочек, открытая адресация, компромисс между памятью и точностью в feature hashing и хешированных эмбеддингах, — становится понятно, что и связные списки, и массивы из предыдущих уроков не были отдельными, разрозненными темами: они сошлись в одной структуре, которая обеспечивает едва ли не самую частую операцию в программировании — быстрый доступ по ключу. В следующем уроке ты перейдёшь к деревьям — структуре, которая жертвует частью этой скорости ради того, чего хеш-таблица дать принципиально не может: порядка.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!