Системное программное обеспечение. Лабораторный практикум - страница 15

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

На рис. 1.2 проиллюстрировано заполнение хэш-таблицы и таблицы идентификаторов для ряда идентификаторов: A_>1, A_>2, A_>3, A_>4, A_>5 при условии, что h(A_>1) = h(A_>2) = h(A_>5) = n_>1; h(A_>3) = n_>2; h(A_>4) = n_>4. После размещения в таблице для поиска идентификатора A_>1 потребуется одно сравнение, для A_>2 – два сравнения, для A_>3 – одно сравнение, для A_>4 – одно сравнение и для A_>5 – три сравнения (попробуйте сравнить эти данные с результатами, полученными с использованием простого рехэширования для тех же идентификаторов).

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

Рис. 1.2. Заполнение таблицы идентификаторов при использовании метода цепочек.

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