Структуры данных

Хеш-таблицы: O(1) доступ

Цели урока

  • Понять идею хеширования: ключ → число → индекс
  • Узнать почему хеш-таблицы дают O(1)
  • Разобраться с коллизиями и Load Factor

Предварительные знания

  • Массивы и индексация
  • Массивы

Представьте библиотеку с миллионом книг. Как найти нужную за секунду? Не перебором же! Хеш-таблица - это гениальный трюк: превращаем название книги в номер полки.

  • Базы данных - индексы для быстрого поиска
  • Кеширование - Redis, Memcached хранят данные в хеш-таблицах
  • Компиляторы - таблица символов (переменные, функции)
  • Браузеры - DNS кеш (домен → IP адрес)

Ханс Петер Лун и рождение хеширования в IBM

Идею хеширования сформулировал Ханс Петер Лун, инженер IBM, во внутренней записке в январе 1953 года. Он искал способ быстро находить записи в большой картотеке и предложил вычислять по ключу число, которое сразу указывает на ячейку хранения. В той же записке Лун описал и разрешение коллизий через цепочки. Параллельно над похожими идеями работал Арнольд Думи, который в 1956 году опубликовал метод деления с остатком: индекс получается как остаток от деления ключа на простое число, близкое к размеру таблицы. Именно метод деления дал название всему подходу: английское hash означает мелко нарубить и перемешать, ведь хеш-функция как бы перемалывает ключ в небольшое число. К началу 1960-х хеш-таблицы уже широко применялись в компиляторах для таблиц символов, и с тех пор остаются одной из самых используемых структур данных в программировании.

Проблема поиска

**Задача:** у вас миллион пользователей. Нужно по email найти данные пользователя. Как?

  • Массив: O(n) - перебираем всё
  • Отсортированный массив: O(log n) - бинарный поиск
  • Хеш-таблица: **O(1)** - мгновенно!

Google обрабатывает миллиарды запросов в секунду. При O(n) на каждый запрос интернет бы умер. Хеш-таблицы - основа современных баз данных, кешей и словарей.

У вас 1 миллион записей. Сколько операций нужно для поиска в хеш-таблице?

Хеш-функция: Ключ -> Число

**Хеш-функция** преобразует любой ключ в число - индекс в массиве.

**Проблема:** "cat" и "act" дают одинаковый хеш! Это называется **коллизия**.

Хорошая хеш-функция должна:

  1. **Детерминированность** - одинаковый вход = одинаковый выход
  2. **Равномерность** - равномерно распределять значения
  3. **Быстрота** - вычисляться за O(1)

Что такое коллизия в хеш-таблице?

Структура хеш-таблицы

Хеш-таблица = **массив** + **хеш-функция**. Ключ хешируется в индекс, по индексу храним значение.

В Python `dict`, в JavaScript `Object`/`Map`, в Java `HashMap` - все это хеш-таблицы!

Из каких компонентов состоит хеш-таблица?

Операции: O(1) в среднем

Три главные операции хеш-таблицы:

ОперацияСреднееХудшее*
**put(key, value)**O(1)O(n)
**get(key)**O(1)O(n)
**delete(key)**O(1)O(n)

*Худший случай - когда все ключи хешируются в один индекс (все коллизии).

Когда операции хеш-таблицы деградируют до O(n)?

Load Factor: Когда расширять

**Load Factor** = количество элементов / размер таблицы

**Правило:** при Load Factor > 0.7 - удваиваем размер таблицы и перехешируем все элементы.

Перехеширование (rehashing) - дорогая операция O(n), но происходит редко. Амортизированная сложность остается O(1).

В таблице размером 20 находится 14 элементов. Чему равен Load Factor?

Ключевые идеи

  • Хеш-таблица = массив + хеш-функция
  • Хеш-функция превращает ключ в индекс: O(1) доступ
  • Коллизия - когда разные ключи дают одинаковый хеш
  • Load Factor > 0.7 → расширяем таблицу

Следующие шаги

А что делать с коллизиями? В следующем уроке разберём два главных метода: цепочки и открытую адресацию.

  • Разрешение коллизий — Как справляться с коллизиями
  • Применения хеш-таблиц — Two Sum и другие задачи

Связанные уроки

  • ds-05-deque — Basic linear structures before jumping to hash tables
  • ds-07-hash-collisions — Collision resolution is the main complexity of hash tables
  • ds-08-hash-applications — Applications build on understanding of hash table internals
  • ds-11-bst — BST is an ordered alternative achieving O(log n) vs O(1) amortised
  • comp-17-symbol-table
  • plt-04-type-inference
Хеш-таблицы: O(1) доступ

0

1

Войти