Переполнение таблицы и рехеширование

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

Рис. 8.8. Циклический переход к началу таблицы.

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

Однако здесь не учитывается возможность многократного превышения адресного пространства. Более корректным будет алгоритм, использующий сдвиг адреса на 1 элемент в случае каждого повторного превышения адресного пространства. Это повышает вероятность найти свободные элементы в случае повторных циклических переходов к началу таблицы. Формула вычисления адреса будет иметь следующий вид:

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

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

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

Алгоритм вставки, реализующий такой подход:

1.

2.

3. Если или , то , записать элемент, элемент добавлен. Если , требуется рехеширование , перейти к шагу 2.