2.2. «Случайные» методики повторного хеширования
Формула (1) линейного повторного хеширования имеет существенный недостаток. Как только несколько последовательных сегментов будут заполнены (образуя группу), любой новый элемент при попытке вставки в эти сегменты будет вставлен в конец этой группы, увеличивая тем самым длину группы последовательно заполненных сегментов. Другими словами, для поиска пустого сегмента в случае непрерывного расположения заполненных сегментов необходимо просмотреть больше сегментов, чем при случайном распределении заполненных сегментов. Отсюда также следует очевидный вывод, что при непрерывном расположении заполненных сегментов увеличивается время выполнения вставки нового элемента и других операторов.
Фактически любая методика повторного хеширования, где очередная проба зависит только от предыдущей (например, как зависимость от числа предыдущих "неудачных" проб, от исходного значения или от самого элемента ), обнаруживает группирующие свойства линейного хеширования.
Возможна простейшая методика, для которой проблема "группирования" не существует: для этого достаточно положить
,
где
—
"случайные" перестановки чисел
.
В
частности,
***
Конечно, такой набор чисел должен использоваться при реализации всех операторов, выполняемых над словарями, а "случайное" перемешивание целых чисел должно быть сделано (выбрано) еще при разработке алгоритма хеширования.
Генерация "хороших случайных" чисел — достаточно сложная задача, но, к счастью, существуют сравнительно простые методы получения последовательности "случайных" чисел путем "перемешивания" целых чисел из заданного интервала. При наличии такого генератора случайных чисел можно воспроизводить требуемую последовательность при каждом выполнении операторов, работающих с хеш-таблицей.
.