Преимущества и недостатки связывания

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

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

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

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

var

cell : PChainCell;

begin

// Определение цепи, содержащей значение.

cell := ListTops* [value mod NumChains].NextCell;

// Поиск элемента.

while (cellonil) do

begin

if (се11Л.Value >= value) then break;

cell := се!1Л.NextCell;

end;

if (cellonil) then

if (cell.Value = value) then

begin

// Какие-либо действия с ячейкой.

,

end;

end;

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