Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Эффективное представление множеств - часть 5


Если по этому индексу был уже занесен элемент данных, то вычисляется следующий индекс и т.д.—до тех пор, пока не будет найдено свободное место в массиве.

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

Различают линейное и

квадратичное зондирование. При линейном зондировании позиции хэш-массива просматриваются с постоянным шагом, а при квадратичном, исходя из значения h(i),—значения индекса

h(i)+1 mod z, h(i)+4 mod z, h(i)+9 mod

z,…,h(i)+j2 mod z.

Простой способ линейного зондирования для определения нового значения индекса в случае коллизии состоит в том, что значение индекса (по модулю z) по мере необходимости увеличивается на 1, пока не будет найдено свободное место в массиве. Впрочем, этот способ имеет то недостаток, что при некоторой статистике скоплений могут возникнуть сгущения в хэш-массиве. Это может привести к тому, что значительные области массива будут интенсивно загружены, вследствие чего потребуется длительный поиск свободного места для заносимого элемента, в то время как другие области будут заняты очень слабо.

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

Метод хэширования весьма эффективен, если используются только рассмотренные операции над элементами множеств.


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