Хеш-таблицы
Обзор
Хеш-таблица (также известная как словарь) - это структура данных, которая ключам ставит в соответствие значения.
В основе хеш-таблицы лежит хеш-функция - специальный алгоритм, превращающий ключ в число, которое далее используется как индекс массива. По этому индексу таблица обращается напрямую к нужной ячейке для получения значения. Это делает операции поиска, добавления и удаления очень быстрыми.
Иллюстрация работы
Простая иллюстрация - это пример списка товаров и их цен:
| Товар | Цена |
|---|---|
| Картофель | 80 |
| Молоко | 90 |
| Яблоки | 150 |
Наличие такой таблицы цен в памяти, где название товара является ключом, а его цена - значением, дает возможность мгновенного доступа к ценам. Когда мы ищем цену, используя название товара в качестве ключа, хеш-таблица немедленно вернет эту цену.
Хеш-таблицы невероятно эффективны для поиска, вставки и удаления данных,
поскольку обычно выполняют эти операции за константное время: O(1). Они
являются одной из самых универсальных и широко используемых структур данных в
информатике. Их применяют для таких задач, как подсчет частоты элементов,
кэширование данных и многое другое.
Хеш-таблицы используются повсюду в реальных системах. Классический пример применения - кэширование в веб-браузерах. Когда вы посещаете веб-сайт, ваш браузер сохраняет данные, такие как изображения, HTML и CSS файлы, в кэше, чтобы они загружались гораздо быстрее при последующих посещениях.
Свойства хеш-таблиц
- Данные хранятся в виде пар ключ-значение.
- Не хранятся дубликаты. Каждый ключ уникален, что гарантирует возможность однозначной идентификации и доступа к каждому значению.
- Неупорядоченность. Ключи не хранятся в каком-либо определенном порядке.
- Коллизии. Иногда хеш-функция выдает один и тот же индекс для разных ключей. Это называется коллизией. С этим борются либо создавая списки внутри ячеек (метод цепочек), либо ища ближайшую свободную ячейку (открытая адресация).
Временная сложность
| Операция | Средняя | Худшая | Описание |
|---|---|---|---|
| Вставка | O(1) | O(n) | Добавление пары ключ-значение в хеш-таблицу. |
| Удаление | O(1) | O(n) | Удаление пары ключ-значение. |
| Чтение | O(1) | O(n) | Найти или получить элемент. |
n - обозначает количество элементов в хеш-таблице.
На практике мы обычно считаем, что операции с хеш-таблицами имеют временную
сложность O(1) в среднем и не учитываем худший случай. Это основано на
предположении, что эффективная хеш-функция минимизирует коллизии. Однако в
худшем случае, когда плохо оптимизированная хеш-функция приводит к частым
коллизиям, временная сложность может ухудшиться до O(n), что требует линейного
поиска по всем элементам таблицы.
Коллизии
В хеш-таблицах коллизии возможны из-за того, что, во-первых, размер таблицы намного меньше множества значений ключа, и, во-вторых, сама хеш-функция может отображать разные ключи в одинаковые значения.
Коллизии в хеш-таблицах возникают из-за математического принципа, который
называется "Принцип Дирихле" (или принцип голубей и ящиков). Если у нас n
ящиков и мы размещаем в них n + 1 голубей, то будет существовать ящик, в
котором находятся хотя бы два голубя.
Хеш-функция преобразует ключ из множества большого размера (символ, строку, структуру данных) в индекс фиксированной длины. Неизбежно наступит момент, когда двум разным ключам захочется занять одну и ту же "ячейку" в таблице.
Кроме того, хеш-функция может быть не идеальной и может распределять данные не равномерно, а так, что разные ключи будут группироваться в одном месте, создавая "кластеры" коллизий.
Даже если хеш-функция генерирует уникальные числа (например, 64-битные), размер
реальной хеш-таблицы в памяти компьютера ограничен. Таблица использует операцию
взятия остатка от деления (hash % array_size), чтобы преобразовать полученный
хеш-код в индекс. Это сужает диапазон и размещает разные ключи в одной позиции.
Когда два разных ключа претендуют на одну и ту же ячейку, хеш-таблицы используют одну из двух основных стратегий "размещения":
- Метод цепочек (Chaining). Это самый популярный способ. Вместо того чтобы хранить в ячейке один элемент, мы храним там ссылку на связный список (цепочку). Например если ячейка уже занята, новый элемент просто дописывается в голову списка, привязанного к этой ячейке.
- Открытая адресация (Open Addressing). Здесь действует правило: "одна
ячейка - один элемент". Если место занято, мы ищем другое по определенному
алгоритму:
- Линейное пробирование: Просто проверяем следующую ячейку (+1, +2...). Если она занята - идем дальше, пока не найдем пустую.
- Квадратичное пробирование: Шаг поиска увеличивается квадратично (1, 4, 9...), чтобы избежать скопления данных в одном месте.
- Двойное хеширование: Если возникла коллизия, применяется вторая хеш-функция, которая определяет "шаг" для поиска свободной ячейки.
Именно по причине коллизий в худшем случае операции с хеш-таблицей могут
работать за O(n). Если бы хеш-функция всегда выдавала уникальный индекс для
уникального ключа и таблица была бы огромного размера, мы бы просто прыгали в
нужную ячейку и забирали значение для ключа. В реальности же поиск проходит в
два этапа: сначала по индексу, а затем таблица дополнительно сравнивает значения
ключей:
- в случае цепочек: коллизии сохраняются в отдельном списке, и нужно пройти по этому списку и сравнить эти ключи с искомым.
- в случае открытой адресации: коллизии занимают соседние свободные ячейки, поэтому в случае несовпадения ключа, нужно двигаться по соседним ячейкам (в соответствии с алгоритмом пробирования) пока не найдем совпадающий ключ или пустую ячейку.
На интервью часто спрашивают, может ли хеш-таблица содержать разные объекты с одинаковым хеш кодом?
Тут важно прояснить, про какие объекты идет речь: про ключи или про значения, соответствующие этим ключам.
Когда мы вставляем элемент в хеш-таблицу мы указываем ключ и значение:
table[key] = value
При этом хеш-таблица вычисляет хеш-функцию именно для ключа key, а не для
значения value, поэтому значения в хеш-таблице могут быть абсолютно любые, как
все одинаковые, так и все разные, и неважно, какой хеш-код может быть у самих
этих значений.
Если же мы говорим про ключи, тут важно понимать, что в хеш-таблице могут храниться разные ключи с одинаковыми хеш-кодами. Это и есть коллизия, и хорошая хеш-таблица обязана уметь хранить такие ключи.
При попытке вставить новое значение newValue по тому же самому ключу key в
таблицу:
table[key] = newValue
новое значение newValue просто перезапишет старое.
Хеш-множества
Хеш-таблицы можно использовать также для моделирования множеств. Вместо хранения пар ключ-значение мы можем хранить только ключи. Используя аналогию с ценами на товары, хеш-множество - это список товаров без указания их цен. Это полезно для быстрой проверки наличия или отсутствия элемента, например, для проверки наличия конкретного товара на складе.
Когда использовать хеш-таблицы или множества?
К распространенным примерам использования хеш-таблиц относятся реализация словарей, подсчет частоты встречаемости, хранение пар ключ-значение и обработка сценариев, требующих быстрого поиска.
Хеш-множества используют для хранения уникальных элементов, пометки элементов как использованных или посещенных, а также для проверки на наличие дубликатов.
При описании задачи обращайте внимание на такие ключевые слова, как "частота", "уникальный", "карта", "словарь" или "быстрый поиск", поскольку они часто указывают на то, что могут быть полезны хеш-таблицы или множества.