Хеш-функции

Основная идея хеширования заключается в том, чтобы работать с массивом размера |S| (вместо размера, сравнимого с астрономическим размером U).

Предположим, требуется организовать хранение множества S с размером до n. Для хранения информации создается массив H размера n, а функция     h : U → {0, 1, …, n − 1} отображает элементы U на позиции массива.

Такая функция называется хеш-функцией, а массив H называется хеш-таблицей. Если потребуется добавить элемент u в множество S, u просто сохраняется в позиции h(u) массива H. В случае сортировки абзацев текста h(·) может рассматриваться как вычисление некоторой числовой сигнатуры или «контрольной суммы» абзаца u; результат определяет позицию массива для хранения u.

Хеширование превосходно работает, если для всех разных u и v в множестве S выполняется условие h(u) ≠ h(v). В таком случае проверка u выполняется за постоянное время: вы проверяете позицию массива H[h(u)], которая либо пуста, либо содержит только u.

Однако в общем случае на такое везение рассчитывать не приходится: могут встретиться два элемента u, v Ѯ S, для которых h(u) = h(v). Возникает коллизия: два элемента отображаются на одну позицию в H. Существуют разные методы разрешения коллизий.

Мы будем считать, что в каждой позиции H[i] хеш-таблицы хранится связанный список всех элементов u Ѯ S с h(u) = i. Операция Lookup(u) работает по следующей схеме:

• вычислить хеш-функцию h(u);
• проверить связанный список в позиции H[h(u)] и проверить, присутствует ли u в списке.

Отсюда следует, что время, необходимое для Lookup(u), пропорционально сумме времени вычисления h(u) и длине связанного списка в позиции H[h(u)]. В свою очередь, последняя величина представляет собой количество элементов в S, находящихся в коллизии с u.

Операции Insert и Delete работают аналогично: Insert добавляет u в связанный список в позиции H[h(u)], а Delete просматривает этот список и удаляет элемент u, если он присутствует.

Теперь цель ясна: нужно найти хеш-функцию, которая «равномерно распределяет» добавляемые элементы, чтобы ни один элемент хеш-таблицы H не содержал слишком много позиций. В задачах такого рода анализ худшего случая не слишком информативен. В самом деле, допустим, что |U| ≥ n2  (а в некоторых случаях намного больше).

Тогда для любой выбранной хеш-функции h существует некоторое множество S из n элементов, которые отображаются на одну позицию. В худшем случае будут вставлены все элементы множества, и тогда в операции Lookup будет задействован перебор связанного списка длины n.

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