- не смотря на то, что часть позиций в массиве свободна, вставить новую запись не удается, так как значения функции повторного хеширования указывают только на занятые позиции.
Первая ситуация может быть обнаружена с помощью счетчика числа записей в массиве. Вторая возможность связана с критерием выбора для функции повторного хеширования. Для любого индекса i последовательно выполняемые шаги повторного хеширования
rh(i), rh(rh(i00, rh(rh(rh(i))) …
распространяются на максимально возможное число целых чисел от нуля до m-1, где m – число элементов в массиве (в идеальном случае – на все это множество). Можно привести пример такого класса функций.
Любая функция
rh(i) = (i+c) mod m, где с – некоторая целая константа, такая, что с и m являются взаимно простыми числами, выдает последовательность значений, распространяющихся на все множество 0..m.
Имеется другая мера пригодности функции повторного хеширования связанная с другой отрицательной ситуацией, характерной для повторного хеширования. Явление, при котором два значения ключа, которые первоначально хешируются в разные значения индексов, начинают при повторном хешировании конкурировать за одни и те же позиции массива, называется скучиваньем.
Например в случае выбора в качестве функции повторного хеширования
rh(i0 = (i+21) mod 1000
при занятых позициях 10,31,52,73,94 любая запись, чей ключ хешируется в одно из этих целых чисел будет конкурировать за позицию 115. В действительности любая функция повторного хеширования, зависящая только от индекса, который требуется повторно хешировать, вызывает скучиванье.
Одним из способов исключения скучиванья является использование двойного хеширования. Это предполагает наличие наряду с функцией h1(key) для первичного хеширование функции h2(key), используемой в составе функции повторного хеширования. Например можно использовать функцию повторного хеширования вида
rh(i) = (i+h2(key)) mod m
до тех пор, пока не будет найдена пустая позиция. Конечно, с учетом сказанного выше h2(key) и m должны быть взаимно простыми числами.
При таком подходе записи с ключами key1 и key2 не будут соревноваться за одну и туже позицию, если h2(key1) не равно h2(key2) при совпадении позиции на предыдущем шаге хеширования. То есть принципиально важно, что функция повторного хеширования зависит не только от индекса, который нужно повторно хешировать, но также от первичного ключа. В оптимальном случае функции h1 и h2 должны быть выбраны таким образом, чтобы они выполняли хеширование и повторное хеширование равномерно на интервале от нуля до m-1, а также минимизировали скучиванье.
Имеется ряд причин, из-за которых повторное хеширование может оказаться неадекватным методом для обработки коллизий:
- оно предполагает фиксированный размер массива, что может привести к неразрешимой задаче по размещению записи,
- из таблицы после разрешения коллизий трудно удалить запись.
Метод цепочек предполагает организацию связанного списка из всех записей, чьи значения ключей хешируются в одно и то же значение. Удаление узла из таблицы, которая построена с применением метода цепочек заключается просто в исключении записи из массива, либо исключении ее из соответствующего связанного списка.
Основным недостатком метода цепочек является то, что для узлов указателей требуется дополнительное пространство. Главное же заключается в том, что при неудачном выборе функции хеширования цепочки могут стать настолько длинными, что в этом случае теряет смысл исходная идея хеширования. Однако в алгоритмах, которые используют метод цепочек первоначальный массив меньше, чем в алгоритмах, использующих повторное хеширование. В методе цепочек не катастрофично заполнение всего массива. При наличии динамической памяти всегда есть возможность выделить дополнительные узлы и добавить их к соответствующим спискам.
Ясно, что выбор хорошей хеш-функции предполагает знание природы ключей. Хотя до выбора и применения хеш-функции редко известны ключевые значения записей списка, обычно имеется некоторая информация об их свойствах, которую необходимо полноценно использовать.
В качестве примера можно привести следующие хеш-функции:
- метод деления
h(key) = key mod m;
- метод середины квадрата: ключ умножается сам на себя и в качестве индекса используются несколько средних цифр квадрата;
- метод свертки, при котором ключ разбивается на несколько сегментов, над которыми выполняется операция двоичного сложения или нетождественности для формирования значения хеш-функции.
Если ключи не являются целыми числами, перед хешированием они должны быть преобразованы в целые числа.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.