Рехеширование

Предположим, что мы хешируем слово S и обнаруживаем, что другое слово уже заняло элемент h. Возникает коллизия. Тогда сравниваем S с элементом h+P₁ (по модулю N, где N – длина таблицы) для некоторого целого P₁. Если снова возникает коллизия, сравниваем S с элементом h+P₂ и т.д. Это продолжается до тех пор, пока не встретится какой-либо элемент h+P_i (по модулю N), который либо пуст, либо содержит S, либо снова является элементом h (P_i=0). В последнем случае мы прекращаем выполнение программы, поскольку таблица полна.

Таким образом, если возникло i коллизий, будет выполнено i+1 сравнений с элементами h_i=h+P_i (по модулю N). Величины P_i должны выбираться так, чтобы ожидаемое число сравнений Е было невелико и чтобы по возможности было рассмотрено большее число элементов.

Рехеширование обычно связывается с термином рассеянной памяти, так как заполненные элементы таблицы оказываются рассеянными по ней. Чтобы отличать пустые элементы от заполненных, все элементы должны быть первоначально заполнены каким–либо значением, которое не может встречаться как символ (слово). Кроме того, таблица должна быть сразу рассчитана на максимальное число элементов. Это объясняется тем, что нет простого способа расширения таблицы (массива), если она заполнена, без повторного вычисления хеш–адресов для всех записанных элементов и занесения их в соответствующие новые позиции. Имеются несколько способов рехеширования, которые и будут рассмотрены ниже.

Линейное рехеширование – старейший и, вероятно, наименее эффективный из них. Он состоит в том, чтобы положить P₁=1, P₂=2, P₃=3 и т. д. То есть сравниваются последовательные элементы. Предположим, например, что символы S1 и S2 были хешированны и записаны в элементы 2 и 4 соответственно (см. рис. 3.8 а)

Теперь предположим, что символ S3 также ссылается на элемент 2. Вследствие коллизии он будет занесен в элемент 3 (рис. 3.8 б). Наконец, предположим, что S4 также ссылается на элемент 2. Возникают последовательно 3 коллизии – с S1, S3 и S2 – прежде чем S4 заносится в элемент 5 (рис. 3.8 в). Причина низкой эффективности этого метода становится достаточно ясной из этого примера; после нескольких коллизий, разрешенных таким образом, элементы скапливаются вместе, образуя длинные цепочки заполненных элементов.

Оценка среднего числа сравнений Е для поиска одного элемента, полученная эмпирическим путем, составляет:

Е = (1 – Lf / 2) / (1 – Lf),

где Lf – коэффициент загрузки. Таким образом, если таблица заполнена на 10% мы можем ожидать 1.06 сравнений, если наполовину – 1.5 сравнений, если на 90%, то – 5.5 сравнений. Заметим, что Е не зависит от размера таблицы, а только от степени заполнения.

Случайное рехеширование снимает проблему скопления за счет выбора в качестве P_i псевдослучайных чисел. Если размер таблицы представляется степенью двойки (N = 2^k, для произвольного k), то хорошие результаты дает следующий способ вычислений P_i:

1. При вызове программы положить целое R, равным 1.

2. Вычислить каждое P_i следующим образом

а) установить R=R*5;

b) выделить младшие k+2 разряда R, и поместить результат в R;

с) взять величину из R, сдвинуть ее вправо на 2 разряда и результат назвать P_i.

Важнейшее свойства этого метода, предотвращающего скопление, состоит в том, что все числа P_i+k – P_i различны. Хорошее приближение ожидаемого числа сравнений в этом случае дает формула:

E = – (1 / Lf) * log (1–Lf),

где Lf – коэффициент загрузки. Так, если таблица заполнена на 10% ожидается 1.05 сравнений, если наполовину – то 1.39, если на 90% – 2.56.

Поиск по сайту: