Слишком сложно? Тогда запросите консультацию специалиста!
Наша компания занимается тем, что помогает студентам выполнять различные учебные работы на заказ. Вы можете ознакомиться с перечнем выполняемых работ, а так же с их стоимостью на странице с ценами.
Он предполагает, что фактическим значением элемента хеш-таблицы является не сама запись, а указатель на динамически размещаемый линейный список записей, при этом список по индексу i содержит все записи, для которых h(x) = i. Пустое значение указателя означает отсутствие таких записей. Возможен и несколько иной вариант представления данных, когда хеш-таблица содержит первую запись каждого списка и указатель на продолжение списка.
Недостаток алгоритма – дополнительный расход памяти на организацию списков, при том, что значительная часть хеш-таблицы может пустовать. Еще хуже то, что выделение динамической памяти (по new или malloc) – довольно медленная операция. Достоинства – отсутствие скучивания и простота удаления записей. Кроме того, в этом алгоритме невозможно переполнение таблицы, наблюдается только снижение скорости поиска при большом числе записей.
Алгоритм Уильямса
Он представляет собой компромиссное решение: записи с одинаковым h(x) организованы в линейные списки, но эти списки размещаются не в динамической памяти, а в основном массиве хеш-таблицы. При этом элементы массива должны, помимо ключа и данных, содержать еще поле связи, в котором указан индекс следующего элемента списка. Кроме того, для ускорения поиска свободного места при вставке используется переменная R, которая при пустой таблице равна N, а затем всегда указывает на позицию в массиве, начиная с которой свободного места наверняка нет. При вставке новой записи, если занята позиция h(k), свободное место ищется вниз от позиции R, а R уменьшается, получая значение индекса найденной позиции. Удаление записей нежелательно, а если оно все же происходит и номер удаляемой записи
i ³ R, то переменной R следует присвоить значение i+1.
