6.3. Хеширование

6.3.1.       Понятие хэш-таблицы и хешфункции. Коллизии и их разрешение.

Идея этого метода состоит в отыскании функциональной зависимости k=f(x), которая бы позволяла за не зависящие от длины входа время (т.е. за 1 шаг) вычислить адрес блока, в котором физически находится искомая запись со значе­нием искомого поля, равном x. Но в такой постановке задача в общем случае не­разрешима. Поэтому приходиться воспользоваться хэш-таблицей. Хэш-таблица представляет из себя массив hash, такой что

hash[m]=k, если k - адрес блока, в котором хранится запись со значением поискового поля, равным x, а m=h(x), где h(x) - некоторая функция, вычисляемая за 1 шаг, и называемая хэш-функцией.

Тогда алгоритм хэширования выглядит так:

m:=h(x); k:=hash[m];

Конечно, перед тем как выполнять поиск, следует сформировать хэш-табли­цу^:

for x £ {ммножеств поисковых значений} do hash[h(x)]:= block(x) ; // block(x) _- блок, где находится запись со значением поискового поля, равным x.

Однако, на практике построение такого алгоритма возможно только при условии, что функция h - биекция, т.е.

A)    " x,y[(h(x) = h(y)) ® (x = y)] — условие инъективности

B)    " m^{£ {m}}$^xh(x) = ^m — условие сюръективности

Очевидно, что условие B эквивалентно условию С:

C)    " xh(x) = ^n^^m} = 1..n)

Мощность области значений функции h(x) совпадает с мощностью её опре­делений.

Следует попытаться добиться выполнения условий A и С. Но это в общем случае невозможно. Чем же грозит невыполнение этих условий? Если нарушается условие «A», то существуют две различные записи со значениями поисковых по­лей x и у такими, что h(x)=h(y)=m. Пусть k и l - адреса блоков, где хранятся эти записи. Тогда hash[m]=k и hash[m]=l, что реализовать напрямую невозможно. Та­кая ситуация называется коллизией. Последствия невыполнения условия C менее серьезны, они приводят к увеличению памяти, требуемой на хранение хэш-табли­цы. В принципе на это можно пойти, если увеличение не будет слишком чрезмер­ным. Однако даже добиться только выполнения условия A в общем случае не представляется возможным, поэтому на практике приходится использовать специ­альные приемы для разрешения коллизий. Очевидно, что они зависят от выбора функции h(x).

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

h(x)=x mod q + 1,

где q - наименьшее простое число среди >=n². Тогда 1<=h(x)<=n².

Если x - не числовое значение, то сначала вычисляется каким-либо спосо­бом числовое значение, и оно уже применяется в хеш-функции.

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

Одним из недостатков хеширования является трудность поиска по неключе­вым полям, так как в этом случае неизбежны естественные коллизии.