6.3.2. Метод цепочек

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

Пример.
Метод цепочек

ФИО

Телефон

Addr 1 Воронов

111-111

Addr 2 Фирсов

444-444

Addr 3 Виталин

777-777

Addr 4 Логман

666-666

Addr 5 Зимина

555-555

Addr 6 Собинова

333-333

Addr 7 Ларин

222-222

М'Воронов')=5

М'Фирсов')=3

М'Виталин')=2

М'Логман')=5

М'Зимина')=2

М'Собинова')=6

М'Ларин')=5

 

При поиске следует последовательно просматривать записи по всем блокам, занесенным в список. Обратим внимание, что в наихудшем случае в список могут быть занесены все блоки, но, как показывает анализ, этот случай очень маловероятен.
В качестве недостатка также следует отметить необходимость лишней операции, связанной с доступом к списку по адресу (эти проблемы излагаются в дисциплине «Программирование», см. также [9, 10]).

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

При поиске следует последовательно просматривать записи по всем блокам, занесенным в список. Обратим внимание, что в наихудшем случае в список могут быть занесены все блоки, но, как показывает анализ, этот случай очень маловероятен.
В качестве недостатка также следует отметить необходимость лишней операции, связанной с доступом к списку по адресу (эти проблемы излагаются в дисциплине «Программирование», см. также [9, 10]).