6.3. Разрешение коллизий методом цепочек
 

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

• методы цепочек;
• методы открытой адресации.

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

Таблицы с внешними цепочками. При использовании внешних цепочек возможны два способа организации хеш-таблицы. В первом способе строка хеш-таблицы содержит запись таблицы с полями данных и полем указателя. Первая запись, поступившая в хеш-таблицу по адресу a_i, помещается в строку таблицы, поле указателя обнуляется. Все другие записи, поступившие по этому же адресу а, т.е. записи, вызвавшие коллизии, помещаются в цепной список переполнения. Таким образом, реально создаются списки только для тех строк хеш-таблицы, при входе в которые возникли коллизии. Во втором способе строка хеш-таблицы содержит только одно поле, поле указателя, т.е. хеш-таблица является адресной таблицей. Первоначально все указатели обнулены. Любая запись, поступившая в хеш-таблицу по адресу а_i, помещается в цепной список переполнения для этого адреса. Данный способ позволяет создавать хеш-таблицы больших объемов, обеспечивая простое разрешение коллизий. Кроме того, когда элементы таблицы имеют переменную длину или когда цепные списки размещаются на ВЗУ, этот способ является наиболее подходящим.

Цепные списки в основной памяти создаются либо в динамической памяти, когда для каждой записи запрашивается память и для каждого хеш-адреса создается свой цепной список, либо в статической памяти — в таблице переполнения, единой для хеш-адресов.

Среднее число проб при удачном поиске равно 1 + к/2, к — коэффициент заполнения таблицы.

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

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

Если коэффициент заполнения таблицы равен к, то средне число проб для метода внутренних цепочек при удачном поиске равно 1 + к/4+1/(8*k)(e^2*k-1-2*k), а при неудачном поиск равно 1 + 1/4*(е^2*k - 1 - 2*к).