ХЕШ-ТАБЛИЦЫ

Хеш-таблица — это обобщение способа хранения множества целых чисел (ключей) в форме вектора битов на случай, когда мощность универсума U очень велика по отношению к мощности множеств, с которыми нужно работать. Функция отображения преобразует значения ключей к интервалу [0, m – 1], где m — размер хеш-таблицы, m ≪ | U |. Очевидно, что при этом каждому индексу хеш-таблицы будет соответствовать много различных значений ключей. Поэтому, во-первых, в хеш-таблице приходится хранить не биты, а сами значения ключей, а во-вторых, иметь возможность размещать в ней более одного ключа для каждого значения функции отображения (разрешать коллизии).

Количество возможных коллизий можно уменьшить, если выполнить два условия:

1) выбрать размер хеш-таблицы с запасом. Если размер таблицы превышает мощность хранимого множества более чем вдвое, вероятность коллизии становится меньше 0, 5. Если мощность множества заранее неизвестна, то выбирают некоторый начальный размер, а когда его оказывается недостаточно, таблицу перестраивают с увеличением размера (обычно вдвое);

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

По способу разрешения коллизий различают таблицы двух типов:

1) хеш-таблица с открытой адресацией. Конфликтующие значения ключей размещаются в свободных ячейках таблицы;

2) хеш-таблица с цепочками переполнения. Каждая ячейка таблицы содержит указатель на список конфликтующих ключей.

Подробнее о хеш-таблицах см. [1], с. 529–556, [2], с. 567–601, [3], с. 115–128, [4], с. 316–338.

Таблицы второго типа применяются чаще, потому что для них не существует проблемы переполнения. Если мощность хранимого множества становится слишком большой, таблица просто начинает работать как m списков. Если же таблица правильно построена и не переполнена, проверка принадлежности элемента множеству, а также вставка и удаление элемента выполняются в ней за постоянное время, примерно такое же, как и в массиве битов.

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

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

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

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

h (x) = (a * x + b) % m,

где m – размер таблицы, а a и b — простые числа.

Обычно a выбирается близким по величине к m, а b — к 1. Так, при m = 100 можно взять a = 97, b = 11. Такой выбор обеспечивает равномерное использование всех ячеек таблицы в большинстве практических случаев.