Первая страница / Визуализаторы / Хеш-таблицы / Хеш-таблицы /

Описание алгоритма

Данный апплет реализует алгоритмы формирования хеш-таблиц двумя способами:

  1. хеширование с разрешением коллизий методом цепочек;
  2. хеширование с открытой адресацией.

Описание использованных алгоритмов

1. Постановка задачи

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

Хеш-таблицу можно рассматривать как обобщение обычного массива. Если имеется достаточно памяти для массива, число элементов которого равно числу всех возможных ключей, для каждого возможного ключа можно отвести ячейку в этом массиве и, тем самым, иметь возможность добраться до любой записи за время O(1). У такой адресации есть очевидный недостаток: если реальное количество записей значительно меньше, чем количество возможных ключей, то эффективнее применить хеширование, и вычислять позицию записи в массиве, исходя из ключа. Если при прямой адресации элементу с ключом k отводится позиция номер k, при хешировании этот элемент записывается в позицию h(k), где h(k) — хеш-функция:

h:U->{0...m-1}

Таким образом, экономится память, и мы пользуемся массивом длины m, а не |U|.

Однако, хеш-значения двух разных ключей могут совпасть. Такая ситуация называется коллизией. Хотелось бы выбрать хеш-функцию так, чтобы коллизии были невозможны, но при |U|>m неизбежно существуют разные ключи, имеющие одно и то же хеш-значение. Поэтому программа должна уметь обрабатывать те коллизии, которые всё-таки произойдут.

2. Выбор хеш-функции

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

Обычно предполагают, что область определения хеш-функции — множество целых неотрицательных чисел.

2.1. Деление с остатком

При построение хеш-функции методом деления с остатком ключу k ставится в соответствие остаток от деления k на m, где m — число возможных значений хеш-функции:

h(k)=k mod m

Например, при размере хеш-таблицы m=12 и ключе k=50 h(k)=2.

Некоторых значений основания m следует избегать. Например, если m=2p, то хеш-функция — это просто p младших битов ключа k. Хорошие результаты дает выбор в качестве m простого числа, далекого от степеней двойки.

2.2. Умножение

Выберем константу 0 < A < 1 и положим

h(k)= floor[m(kA mod 1)],

где (kA mod 1) — дробная часть kA, floor[ ] — целая часть числа. Метод умножения работает при различном выборе A, но некоторые значения могут быть лучше других. Например, в [2] рекомендуется A=0.6180339887.

2.3. Универсальное хеширование

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

Подробнее см. [1].

3. Разрешение коллизий методом цепочек

Технология сцепления элементов (chaining) состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i; если таких элементов в множестве нет, в позиции j записан NULL.

4. Разрешение коллизий c помощью открытой адресации

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

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

h: U *{0,1,...,m-1}->{0,1,...,m-1},

Таким образом, процедура вставки элемента в таблицу T выглядит так:

INSERT()
  i=0
  repeat
        j=h(k,i)
        if T[j]==NULL
           then T[j]=k
           return j
        else i=i+1
  until i==m
  error "переполнение таблицы"

При поиске элемента с ключом k в таблице с открытой адресацией ячейки таблицы просматриваются в том же порядке, что и при добавлении в нее элемента с ключом k. Если при этом мы натыкаемся на ячейку, в которой записан NULL, то можно быть уверенным, что искомого элемента в таблице нет (иначе он был бы занесён в эту ячейку). Процедура поиска элемента в таблице выглядит следующим образом:

INSERT()
  i=0
  repeat
        j=h(k,i)
        if T[j]==k
           then return j
        i=i+1;
  until T[j]==NULL or i==m
  return NULL

Удалить элемент из таблицы с открытой адресацией не так просто. Если просто записать на его место NULL, то в дальнейшем мы не сможем найти те элементы, в момент добавления которых в таблицу это место было занято (и из-за этого был выбран более далёкий элемент в последовательности испробованных мест). Возможное решение — записывать на место удалённого элемента не NULL, а специальное значение DELETED, и при добавлении рассматривать ячейку с записью DELETED как свободную, а при поиске — как занятую (и продолжать поиск). Недостаток этого подхода в том, что время поиска может оказаться большим даже при низком коэффициенте заполнения. Поэтому, если требуется удалять записи из хеш-таблицы, предпочтение обычно отдают хешированию с цепочками.

5. Выбор хеш-функции при открытой адресации

5.1. Линейная последовательность проб

h(k,i) выбирается следующим образом:

h(k,i)=(h'(k)+i) mod m,

где h'(k,i) — обычная хеш-функция. Таким образом, для данного ключа k просматриваются ячейки, начиная с h'(k). Этот способ самый простой, но он может приводить к появлению больших блоков в таблице, что замедляет поиск.

5.2. Квадратичная последовательность проб

h(k,i)=(h'(k)+с1i+с2i2) mod m,

где h'(k,i) — обычная хеш-функция. Этот метод работает гораздо лучше, чем линейная последовательность проб, но кластеры все равно могут появляться, хотя и в гораздо более мягкой форме.

5.3. Двойное хеширование

Один из лучших методов открытой адресации. Хеш-функция имеет вид:

h(k,i)=(h1(k)+ih2(k)) mod m,

где h1(k) и h2(k) — обычные хеш-функции. При этом, чтобы последовательность проб покрывала всю таблицу, необходимо, чтобы h2(k) было взаимно простым с m. Например, в качестве m взять степень двойки, а h2(k) — такую, чтобы принимала только нечетные значения. Или m — простое число, h2(k) — целые положительные числа, меньшие m.

6. Использование тестирующего апплета

Апплет демонстрирует работу двух видов алгоритмов хеширования:

хеширование с разрешением коллизий методом цепочек;

хеширование с разрешением коллизий c помощью открытой адресации;

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

Литература

  1. Т.Кормен, Ч.Лейзерсон, Р.Ривест Алгоритмы: построение и анализ, Москва, МЦМНО, 2000.
  2. Д.Кнут Искусство программирования. Т.3 Сортировка и поиск, Москва, Мир, 1978.