Структуры и алгоритмы обработки данных


Переполнение таблицы и рехеширование - часть 2


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

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

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

Вставка

  • i = 0
  • a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
  • Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

  • Если i > m , то стоп требуется рехеширование

  • i = i + 1, перейти к шагу 2

В данном алгоритме номер итерации сравнивается с пороговым числом m. Следует заметить, что алгоритмы вставки, поиска и удаления должны использовать идентичное образование адреса очередной записи.

Удаление

  • i = 0
  • a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
  • Если t(a) = key, то t(a) =удалено, стоп элемент удален

  • Если t(a) = свободно или i>m, то стоп элемент не найден

  • i = i + 1, перейти к шагу 2

Поиск

  • i = 0
  • a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
  • Если t(a) = key, то стоп элемент найден

  • Если t(a) = свободно или i>m, то стоп элемент не найден

  • i = i + 1, перейти к шагу 2




Начало  Назад  Вперед



Книжный магазин