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. Выч-е х-ф. производится с учётом не размерности таблицы, а с учётом размера массива.


 

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

49698. Определение геометрических размеров рамы 148 KB
  Выбираем сечение ригеля 150x300.сечения; ширина ребра таврового и двутаврового сечений; h0 рабочая высота сечения; относительная высота сжатой зоны бетона Rb расчетные сопротивления бетона осевому растяжению; Аs площадь сечения ненапрягаемой арматуры γb 1 где Rbn – значение жесткости бетона призменная прочность выбираемое по таблице СНиП 2. γs 1 по значению Rs выбираем =004 производим расчет арматуры по формуле 2 см2 где относительная высота сжатой зоны бетона равная...
49700. РАДИОПРИЁМНОЕ УСТРОЙСТВО ЧМ СИГНАЛОВ 1.6 MB
  Курсовой проект посвящен проектированию приемника частотно модулированных непрерывных сигналов.В первой главе проведен выбор и обоснование структурной схемы приемника и описаны основные составные части. Во второй главе сделан эскизный расчет приемника и выбраны электрические принципиальные схемы составных частей приемника.
49701. Метрологическое обеспечение механической обработки гильзы 1Е14ОП-ХС1200.5.19.018 211.48 KB
  Целью работы является разработка метрологического обеспечения производства детали Гильза проверка правильности оформления чертежа правильности выбора допусков на размеры и значений шероховатости для поверхностей. СОДЕРЖАНИЕ Введение 5 1 Задача метрологической экспертизы 6 2 Назначение детали 7 3 Требования к точности размеров 8 4 Требования к шероховатости поверхности 10 5 Взаимосвязь допусков размеров формы расположения поверхностей и шероховатости 11 6 Отклонение формы и расположения поверхностей 13 7 Список замечаний и предложений на...