Зацикливание метода обработки коллизий

Рейтинг: 0Ответов: 1Опубликовано: 18.04.2011

При обработке коллизии для поиска свободной ячейки методом двойного хеширования цикл "зациклился". В методе написано, что такое возможно для данного метода. Преподша говорила, что надо таблицу увеличить в 1.5-2 раза и сделать все заново.

Только вот вопрос: как определить, что он зациклился? Через какое-то число итераций, отслеживать на повторяемость вычисленных адресов или еще как-то? В-общем как отследить зацикливание?

алгоритм хеширование
Источник: Stack Overflow на русском

Ответы

▲ 1

При правильном алгоритме зацикливания быть не может!

Либо, перебирая элементы таблицы, начиная с вычисленного по хэшу элемента, нашли искомый ключ, либо нашли пустой элемент - значит искомого ключа в таблице нет. Максимальное число просмотров - размер таблицы. Т.е. если сделали N (размер таблицы) шагов, то таблица переполнена (выходим из функции).

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