Cтраница 1
Обработка коллизий может происходить следующим образом. Если ячейка, адрес которой получен после операции перемешивания, свободна, то имя записывается в поле имени, а в поле признака устанавливается признак конечного элемента списка. Если строка занята, то новое имя и имя, находящееся в ячейке, сравниваются. При совпадении функции HASH присваивается значение - 1 и ее выполнение завершается. При несовпадении новое имя записывается в первую свободную ячейку области переполнения; ячейка помечается ( устанавливается соответствующий признак) как конечный элемент списка и связывается с тем списком коллизий, в голове которого находится ячейка с индексом, получаемым в результате перемешивания имени. [1]
Обработка коллизий может происходить следующим образом. Если ячейка, адрес которой получен после операции перемешивания, свободна, то имя записывается в поле имени, а в поле признака устанавливается признак конечного элемента списка. Если строка занята, то новое имя и имя, находящееся в ячейке, сравниваются. При совпадении функции HASH присваивается значение - 1 и ее выполнение завершается. При несовпадении новое имя записывается в первую свободную ячейку области переполнения; ячейка помечается ( устанавливается соответствующий признак) как конечный элемент списка и связывается с тем списком коллизий, в голове которого находится ячейка с индексом, получаемым в результате перемешивания имени. [2]
Для обработки коллизий разработаны специальные методы, рассмотренные ниже. [3]
Для обработки коллизий записи, входящие в класс коллизий, вместе с их ключами организуются в виде линейного списка, первый элемент которого размещается по адресу, получаемому при перемешивании. Для нахождения конкретной записи список просматривается и ключи записей сравниваются с заданным ключом. Хороший алгоритм перемешивания хотя и не сможет предотвратить возникновение коллизий совсем, обычно позволяет сохранять небольшой размер списков коллизий, делая приемлемым их последовательный просмотр. Отметим, что списки коллизий требуют дополнительной памяти. В то же время некоторые участки памяти могут остаться свободными из-за того, что ключи, соответствующие адресам этих участков, могут никогда не встретиться. Поэтому файл, для адресации записей которого используются методы перемешивания, неизбежно имеет дыры ( в связи с этим данный метод часто называют рассеянной памятью), но это вполне окупается получаемыми преимуществами. [4]
В методах хеширования, используемых для хранения множеств, в обоих способах обработки коллизий - рехешировании и последовательнрм сканировании - возникают трудности, если разрешены исключения Из множества. [5]
S: / Я), и для ключей, содержащихся в списке, установим К битов равными 1 и 0 - для прочих; обработку коллизий в таблицах проводить не будем. Для таких условий проведем следующее рассуждение, которое позднее несколько скорректируем. [6]
Указатель кольца высказывания указывает на узел с тем же идентификатором pi, таким образом, все узлы с данным идентификатором высказывания связываются в кольцо. Такая ортогонализация упрощает обработку коллизий. [7]
Каждый элем-ент центральной таблицы ц поч-ек содержит саму цепочку и указатель на ее значение. Когда во время выполнения программы создается новая цепочка, центральная таблица просматривается, чтобы выяснить, не была ли эта цепочка ранее внесена в таблицу. Если была, то используется указатель на найденный элемент таблицы. Эта простая схема вносит в язык значительную гибкость; она позволяет во время выполнения создавать при желании новые переменные. Ее недостаток заключается в стоимости поиска по таблице каждый раз, когда создается новая цепочка. Поскольку многие инструкции Снобола 4 создают новые цепочки, поиск по таблице происходит часто. Обычным представлением для центральной таблицы является хеш-таблица с дополнительным пространством для обработки коллизий. [8]