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

Вернемся к вопросу возникшей коллизии при вставке записи с ключом 0596396 в имеющийся массив записей и с хеш-функцией mod (key, 1000).

Самым простым способом разрешения возникшей коллизии является помещение записи 0596396 в следующую свободную позицию в массиве. Например, если ячейка свободна, то можно поместить запись туда. Этот метод называется линейным опробованием, и он является примером некоторого общего метода разрешения коллизий при хешировании, который называется повторным хешированием или открытой адресацией. В общем случае функция повторного хеширования rh воспринимает один индекс в массиве и выдает другой индекс. Если ячейка массива h (key) уже занята некоторой записью с другим ключом, то функция rh применяется к значению h (key) для того, чтобы найти другую ячейку, куда может быть помещена эта запись. Если ячейка rh (h (key)) также занята, то хеширование выполняется еще раз и проверяется ячейка rh (rh (h (key))). Этот процесс продолжается до тех пор, пока не будет найдена пустая ячейка [3].

Например, если h (key) = mod (key,1000), то в качестве rh функции можно взять функцию mod (i +1,1000), т.е. повторное хеширование какого-либо индекса есть следующая последовательная позиция в данном массиве, за исключением того случая, что повторное хеширование 999 дает 0.

Любая функция rh (i) = mod (i + c, m), где с — константа, такая что c и m являются взаимно простыми числами (т.е. они одновременно не могут делиться нацело ни на какое число, кроме 1), выдает последовательные значения, которые распространяются на всю таблицу.

Рассмотрим ситуацию, возникающую при повторном хешировании, которая называется скучиванием.

Рис. 4.8

 

Обратимся к Рис. 4.8, из которого видно, что помещение записи в позицию 994 в пять раз вероятнее, чем в позицию 401. Это происходит из-за того, что любая запись, чей ключ хешируется в позиции 990–994 будет помещена в 994, а в позицию 401 будет помещена только та запись, чей ключ хешируется в эту позицию. Это явление, при котором два ключа конкурируют друг с другом при повторных хешированиях называется скучиванием.

Одним из способов исключения скучивания является использование двойного хеширования, которое состоит в использовании двух хеш-функций: h ₁ (key) и h ₂ (key). Функция h ₁ (key), называемая первичной хеш-функцией, используется первой при определении позиции, в которую должна быть помещена запись. Если эта позиция занята, то последовательно используется функция повторного хеширования

rh (i) = mod (i + h ₂ (key), m)

до тех пор, пока не будет найдена пустая позиция. Записи с ключами key ₁ и key ₂ не будут соревноваться за одну и ту же позицию, если h ₂ (key ₁) ¹ h ₂ (key ₂).

Другой метод разрешения коллизий при хешировании называется методом цепочек. Он представляет собой организацию связанного списка из всех записей, чьи ключи хешируются в одну и ту же позицию. Предположим, что хеш-функция выдает значения в диапазоне от 0 до m -1. Тогда описывается некоторый массив, например, bucket, размера m. Элемент bucket (i) указывает на список всех записей, чьи ключи хешируются в i. При поиске записи осуществляется доступ к указателю списка, который занимает позицию i в массиве bucket. Если запись не найдена, то она вставляется в конец списка. Обратимся к Рис. 4.9, на котором показан метод цепочек. Предположим, что имеются 14 элементов, хеш-функция равна mod (key, 10). Ключи представлены в таком порядке:

 

75     66 42 192 91 40 49 87 67 16 417 130 372 227

 

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

 

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

 

Обратимся к вопросу, как выбрать хорошую хеш-функцию. Ясно, что она должна создавать как можно меньше коллизий при хешировании, т.е. она должна равномерно распределять ключи на имеющиеся индексы в массиве. Наиболее известная хеш-функция (которую мы использовали в вышеизложенных примерах) использует метод деления, при котором некоторый целый ключ делится на размер таблицы и остаток от деления берется в качестве значения хеш-функции. Она обозначается h (key)= mod (key, m). Предположим, что m равно 1000 и что все ключи оканчиваются на 3 одинаковые цифры (например, последние три цифры номера изделия означают номер завода-изготовителя). Тогда остаток от деления на 1000 для всех ключей будет одинаков, т.е. возникнут коллизии при хешировании для всех записей, кроме первой. Ясно, что при таком наборе ключей допуска должна использоваться другая хеш-функция [3].

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

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

Например, предположим, что внутреннее представление некоторого ключа в виде последовательности разрядов имеет вид 010111001010110 и для индекса отводится 5 разрядов. Над тремя последовательностями разрядов 01011, 10010 и 10110 выполняется операция сложения, что дает 01111 или двоичное представление числа 15.

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

Если ключи не являются числами, то они должны быть преобразованы в целые числа перед применением описанных выше хеш-функций. Для этого имеется несколько способов. Например, для строки символов в качестве двоичного числа может интерпретироваться внутреннее двоичное представление кода каждого символа. Недостатком этого является то, что для большинства ЭВМ двоичное представление букв и цифр очень похоже друг на друга. Если ключи состоят только их одних букв, то индекс каждой буквы в алфавите может использоваться для создания некоторого целого числа. Так, первая буква алфавита (А) представится цифрами 01, а 14 -я буква (N) представляется цифрами 14. Ключ “Hello” представляется целым числом 0805121215. Когда существует некоторое целое представление строки символов, то для сведения его к приемлемому размеру может быть использован метод свертки или середины квадрата.