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


 

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

64565. Специфіка філософських світоглядних питань. Джерела філософського знання 25 KB
  Однією з особливостей філософського знання його спрямованість на подолання проблемусвідомлення незавершеності процесу пізнання. Філософське знання пройняте суб’єктивністю. Це є знання певного суспільства і певної особи яка сповідує певні цінності.
64567. Творчество Караваджо 15.24 KB
  Ранние работы Караваджо поясные портреты иногда с включением деталей натюрморта которые Караваджо писал мастерски. В капелле Черази церкви СантаМария дель Пополо Караваджо изменил манеру письма. Фигуры у Караваджо изображены таким образом что у зрителя возникает ощущение необыкновенной реалистичности.
64569. Проблема баланса сил в XVIII веке. Военные конфликты 30-х - 60-х годов XVIII века 13.5 KB
  Главным в международной политике стало строгое соблюдение принципа баланса сил. Три основных конфликта этого периода фактически определяли направленность усилий европейских политиков и дипломатов.
64570. Социально-этичный маркетинг 19.73 KB
  Социально-этический маркетинг (социально-этичный маркетинг, социальный маркетинг) – это комплексное взаимодействие коммерческой фирмы, работающей на рынке, с клиентами, контрагентами, различными общественными институтами, основанное на признании решающей роли социальной ответственности фирмы.
64571. ХАРАКТЕРИСТИКИ ДОРОЖНОГО ДВИЖЕНИЯ. ТРАНСПОРТНЫЙ ПОТОК 36.01 KB
  При формировании информации о состоянии дорожного движения в первую очередь необходимы данные характеризующие транспортный поток. По мере совершенствования методов и аппаратуры для исследования транспортных потоков номенклатура показателей используемых в организации...
64573. Основные направления европейской политики XVIII столетия. Проблема баланса сил 15.45 KB
  Причиной войны стал династический спор французских Бурбонов и австрийских Габсбургов за право наследования испанского престола после смерти в ноябре 1700 Карла II (1665–1700), последнего представителя испанских Габсбургов.