29367

Реализация операций поиска и записи в хеш-таблицах по методу цепочек

Доклад

Информатика, кибернетика и программирование

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

Английский

2013-08-21

27 KB

11 чел.

35,36) Реализация операций поиска и записи в хеш-таблицах по методу цепочек.

Этот способ более эффект., чем рехеширование как с точки зрения эффект. поиска в таблице, так и с точки зрения отсутствия огранич. на размер таблицы, т.е. ситуация переполнения таблицы отсутствует. Это достигается использованием дополнительных структурных данных при организации таких таблиц.
Для реализации метода цепочек необходимо следующее:
• таблица имён с дополнительным полем связи, которое может содержать либо 0, либо адреса других элементов этой же таблицы.
• перем. указат. последнего записанного элемента таблицы. Заполнение таблицы имён при использовании метода цепочек производится в порядке поступления элементов подобно неупорядоченной таблицы.
• массив адресов, элементы которого в исходном состоянии = 0, а по мере заполнения таблицы имён может содержать индексы (адреса её элементов).
Назначение этих структур
Хеширование некоторого имени S даёт индекс элемента массива адресов, т.е. хеш-функция ссылается не на таблицу имён непосредственно, а на промежуточную структуру, т.е. элемент массива адресов, на котором указ. хеш-функция может быть = 0 или содержать адрес некоторого элемента таблицы имён.
В 1-м случае имена с таким значением 
хеш-функции в таблице имён отсутствуют. В противном случае соответствующая ячейка массива адресов содержит индекс 1-го имени с таким же значение хеш-функцииДо тех пор пока не возникает коллизии записи элементов, в таблице имён производится:
• вычисляется значение хеш-функции h для S,
• переменная p = p + 1,
• имя S записывается в таблице имён в элемент с индексом p. Полю связи этого элемента присваивается значение 0,
• значение р заносится в массив адресов в элемент с индексом h.
При возникновении коллизии х-ф. указ-т на элемент массива адресов, который не равен 0, т.е х-ф. указ-т на адрес другого элемента с таким же значением х-ф. В этом случае элементы в таблице должны объедин. в цепочки с помощью поля связи. Для этого очередной запис-й элемент, если он отсутствует в таблице, добавляется в её конец и подключается к соответствующей цепочке.
Нетрудно заметить, что максимальное количество элементов не ограничено её размерами. По мере заполнения к таблице динам. могут подключаться новые блоки данных. Количество коллизий в таких таблицах определяется числом элементов массива адресов, чем меньше размер этого массива тем больше количество коллизий будет возникать. В реальном трансляторе размер массива адресов колеблется от 100 до 300. Выч-е х-ф. производится с учётом не размерности таблицы, а с учётом размера массива.


 

А также другие работы, которые могут Вас заинтересовать

76072. Показатели эффективности ипотечного кредитования. Анализ экономической и социальной эффективности ипотечного кредитования 297 KB
  Цель и задачи данной работы: рассмотреть понятие и функции ипотеки, особенности и показатели эффективности ипотечного кредитования, а так же проанализировать эффективность ипотечного кредитования.
76073. Организация работы производства семейного ресторана на 60 мест, организация выпуска готовой кулинарной продукции в горячем цехе 320.43 KB
  Определения количества блюд и напитков подлежащих изготовлению. Разбивка блюд по ассортименту в соответствие коэффициентами потребления блюд. Однако первый ресторан то есть заведение где готовятся и подаются блюда заказанные посетителем по своему вкусу появился на Западе лишь в 18 веке.
76074. НАСЛЕДОВАНИЕ ПО ЗАВЕЩАНИЮ 192.5 KB
  Это объясняется в первую очередь тем что в результате становления рыночных отношений закрепления за гражданами права частной собственности на имущество которое может переходить в порядке наследства по завещанию круг объектов значительно расширился.
76075. Усилитель переменного напряжения 452.5 KB
  Цель работы – изучение с устройства и принципа работы операционного усилителя, и устройства переключения. В процессе работы проводились расчеты на структурном уровне, выбор элементов и разработка принципиальной электрической схемы.
76076. Методы построения нейросетевых моделей прогнозирования 1.45 MB
  Далее была усложнена структура персептрона усовершенствована модель математического нейрона разработано множество алгоритмов обучения созданы персептроны на основе гибридных нейросетей а так же расширился круг задач решаемых с помощью нейросетей.
76077. Анализ и синтез зубчатых, рычажных и кулачковых механизмов 2.72 MB
  Качество освоения студентом материала проверяется и оценивается при защите курсовой работы. При этом учитываются уровень знаний, качество оформления чертежей и пояснительной записки, а также ритмичность выполнения работы и срок ее завершения.
76078. Разработка односторонней (симплексной) многоканальной системы связи для телефонии и телеметрии 603.5 KB
  Система уплотнения, в целом, использует частотное разделение каналов, подсистема телеметрии — временне. Затем уплотненный групповой сигнал подсистемы телеметрии передается по каналу тональной частоты для дальнейшего уплотнения.
76079. Разработать лабораторный регламент производства мази борной (на 100 кг) 3.2 MB
  Целью данной работы является составление лабораторного регламента прозводства мази борной. Мази способны образовывать на поверхности кожи или слизистой оболочки ровную не сползающую сплошную пленку.
76080. Повременная заработная плата на предприятии 3.8 MB
  Политика в области оплаты труда является составной частью управления предприятием и от нее в значительной мере зависит эффективность его работы так как заработная плата является одним из важнейших стимулов в рациональном использовании рабочей силы.