Рисунок 6.1 - хеш-таблица с прямым связыванием
Страница 6
В хеш таблице с прямым связыванием (рис 6.1) значения ключей (бункеры) хранятся в специальных наборах записей, называемых блоками. Каждый из них является вершиной связного списка, в котором находятся привязанные к блоку элементы.
Рисунок 6.1 - хеш-таблица с прямым связыванием
Поиск элементов в хеш-таблице пройдёт быстрее, если связанные списки будут содержать ключи в отсортированном порядке. В этом случае алгоритм сделает вывод, что ключа нет, если дойдёт до значения больше ключевого и не станет просматривать список до конца. Теоретически время его работы составит O(N/B), но на практике оно будет немного меньше.
Чтобы найти нужный элемент, программе необходимо хешировать ключ и определить, в каком из блоков он может содержаться, а затем двигаться по связному списку до тех пор, пока не будет достигнут его конец или не обнаружится искомое. Если вы доберётесь до конца списка, значит, запрашиваемого элемента в хеш-таблице нет. Как и в случае с добавлением элемента, предстоит выполнить O(N/B) шагов.
Хеш-таблица с прямым связыванием может расширяться и сжиматься1 по мере необходимости, поэтому вам не нужно специально изменять её размер. Однако если связные списки станут слишком длинными, поиск и удаление элементов займут много времени. В этом случае вам понадобится увеличить таблицу, чтобы создать больше блоков. Поскольку при рехешировании таблицы не надо проводить поиск дубликатов до конца связного списка в каждом блоке, полностью справиться с операцией можно за время O(N).
1Удаление элементов в данном методическом материале рассматриваться не будет