Таблицы с прямым доступом

Модуль "Хеш-таблицы" • урок 1 из 4 • ~10 минут

Суть урока. Хеш-таблица (Hash Table) - это структура данных, реализующая интерфейс ассоциативного массива (словаря), а именно позволяет хранить пары "ключ-значение" и выполнять добавление, удаление и поиск элементов в среднем за константное время O(1).

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

Представьте, что вам нужно реализовать телефонную книгу. У вас есть имена (строки) и номера телефонов. Вы хотите быстро находить номер по имени.

Если хранить данные в неотсортированном массиве, поиск займет O(N).
Если массив отсортировать и использовать бинарный поиск, время сократится до O(log N).
Сбалансированное бинарное дерево поиска (например, АВЛ) тоже даст O(log N) для всех операций.

Но что, если нам нужно еще быстрее? Что, если мы хотим находить данные за O(1)?

Идеальным решением был бы массив, где само имя служило бы индексом. Но индексы массива - это целые числа (0, 1, 2...). Тут на помощь приходит хеш-функция.

Хеш-функция

Хеш-функция - это алгоритм, который принимает на вход данные произвольного размера (например, строку) и возвращает число фиксированного размера (хеш-код).

Таблицы с прямым доступом: от ключа к индексу

Таблицы с прямым доступом: хеш-функция превращает три ключа-строки в числовые индексы массива — Иван, Анна и Мария проходят через одну и ту же хеш-функцию H и получают разные индексы: 2, 1 и 4 - в этом примере ни один индекс не повторился.

Этот хеш-код затем приводится к размеру массива (обычно через операцию взятия остатка от деления hash % size), чтобы указать на конкретный индекс, по которому будут лежать данные.

Требования к идеальной хеш-функции

Детерминированность: для одного и того же ключа функция всегда должна возвращать один и тот же хеш.
Скорость вычисления: вычисление хеша должно быть быстрым (в идеале O(1) от размера ключа).
Равномерное распределение: функция должна равномерно распределять ключи по доступным индексам, чтобы не создавались "скопления" данных в одном месте.

Коллизии

В примере выше трем именам повезло: индексы 2, 1 и 4 не совпали. Но так будет не всегда. Поскольку множество возможных ключей (например, все возможные имена или строки в мире) бесконечно, а размер массива ограничен, неизбежна ситуация, когда разные ключи дадут один и тот же индекс. Такая ситуация называется коллизией.

Наличие коллизий - это абсолютно нормальное явление для хеш-таблиц. Эффективность работы со структурой напрямую зависит от того, насколько хорошо алгоритм умеет эти коллизии разрешать. О популярных способах разрешения коллизий (метод цепочек и открытая адресация) мы детально поговорим в следующем уроке.

Коротко: главное

Хеш-таблица предоставляет прямой доступ к данным по ключу за среднее время O(1).
Хеш-функция преобразует произвольный ключ (например, строку) в числовой индекс массива.
Идеальная хеш-функция должна быть детерминированной, быстрой и обеспечивать равномерное распределение.
В обычных хеш-таблицах криптографическая стойкость функции (невозможность восстановления ключа) не требуется.
Ситуация, когда разным ключам назначается одинаковый индекс, называется коллизией и является нормальной частью работы структуры.

Проверьте себя

Какое из перечисленных свойств НЕ является обязательным требованием к хеш-функции, используемой в обычной хеш-таблице (например, для реализации словаря)?

Детерминированность (для одного и того же ключа всегда возвращается один и тот же хеш). Равномерное распределение ключей по доступным индексам. Невозможность восстановить исходный ключ по его хеш-коду (криптографическая стойкость).

Как вам урок? Спасибо за отзыв!