6.3.2. Метод цепочек Метод цепочек подразумевает то, что в каждую ячейку хеш-таблицы действительно должно быть записано несколько значений. Конечно, «в лоб» это сделать просто невозможно, поэтому в ячейках хранятся не сами адреса элементов (точнее блоков), а указатели на списки адресов. В случае коллизии такой список будет содержать несколько значений. Пример.
М'Воронов')=5 М'Фирсов')=3 М'Виталин')=2 М'Логман')=5 М'Зимина')=2 М'Собинова')=6 М'Ларин')=5
|
При поиске следует последовательно
просматривать записи по всем блокам, занесенным в список. Обратим
внимание, что в наихудшем случае в список могут быть занесены все
блоки, но, как показывает анализ, этот случай очень маловероятен. Рис. 24. Разрешение коллизий методом цепочек При поиске следует последовательно
просматривать записи по всем блокам, занесенным в список. Обратим
внимание, что в наихудшем случае в список могут быть занесены все
блоки, но, как показывает анализ, этот случай очень маловероятен. |