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


 

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

71861. Творчество Ж.-Б. Грёза 14.49 KB
  В жанре семейного быта с его драмами у Грёза совсем немного соперников во французской живописи. Картины Грёза были гравированы лучшими мастерами среди которых Леба Флипар и Массаротец. В 1868 году на родине Грёза в Тюрню ему воздвигнут памятник.
71862. Творчество Ж.О. Фрагонара 13.76 KB
  В больших исторических картинах Фрагонара мало оригинальности; в его пейзажах природа является слишком переиначенной и приукрашенной; зато жанровые его картины хотя и не чуждые манерности пленяют зрителя умно изобретённой композицией грациозностью рисунка изящностью...
71863. Творчество Ф. Буше 17.31 KB
  Творчество Буше живописца исключительно многогранно он обращался каллегорическим и мифологическим сюжетам изображал деревенские ярмарки и фешенебельную парижскую жизнь писал жанровые сцены пасторали пейзажи портреты.
71864. Творчество Рембрандта 14.96 KB
  Работы Рембрандта чрезвычайно разнообразные по жанровой принадлежности открывают зрителю вневременной духовный мир человеческих переживаний и чувств. Однако именно искусство Рембрандта заключает итог общих поисков и по существу представляет собой завершение всего развития...
71865. Творчество Ф. Сурбарана 15.05 KB
  В 1628-1630 годах Сурбаран пишет цикл картин о святом Педро Ноласко и цикл картин о жизни св. В самом начале своей деятельности поставив себе за правило писать не иначе как с натуры Сурбаран не отступал от этого правила в течение всей своей жизни.
71866. Творчество Мурильо 14.47 KB
  Известность приходит к Мурильо В 1645 г. Уже в произведениях несмотря на тяжеловатость и резкость их тонов ярко выказываются колористическая наклонность и национальный специально севильский характер Мурильо берущего натурщиков и натурщиц для своих фигур из народа. Всех произведений Мурильо насчитывается свыше 450.
71867. Творчество Х. Риберы 15.45 KB
  Ранние картины Риберы находятся в русле традиции тенебризма и подобно работам его наставника Рибальты выполнены под сильным влиянием Караваджо. Как и в случае с Караваджо стилевая манера Риберы строится на контрастах света и тени.
71868. Контроль функционирования технологического процесса 17.23 KB
  Часто перед руководством возникает вопрос: какая стратегия более оправдана действие в составе технологической цепи или автономная работа всех участников ПВ показатель воздействия ПВ может быть меньше равен или больше 1 цепочки действует хорошо.
71869. Мотивация инноваций 14.17 KB
  Мотивацию инноваций необходимо рассматривать в двух аспектах: мотивация создания и продажи инноваций и мотивация покупки и использования инноваций. Мотивация создания и продажи инноваций Мотивация покупки и использования инноваций...