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


 

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

75856. Лінгвістичні моделі. Лінгвістичний знак та його особливості 31.83 KB
  Чаще всего под термином понимают: модель тип образец lnguge pttern какихлибо текстовых единиц слов предложений; модель символы схемы для описания языковых объектов ПР: схема модели составляющих в синтаксисе модель формализованная теория структуры с фиксированным метаязыком ПР: формальные грамматики. Главная цель моделирования в лингвистике это моделирование целостной языковой способности человека. Общие свойства моделей: условность образ может быть не только материальным но и мысленным и передаваться посредством...
75857. Корпусна лінгвістика: проблемна галузь та корпус даних. Види корпусних текстів. Принципи розмітки текстів у лінгвістичних корпусах 34.09 KB
  Целесообразность создания текстовых корпусов объясняется: представлением лингвистических данных в реальном контексте; достаточно большой представительностью данных при большом объёме корпуса; возможностью многократного использования единожды созданного корпуса для решения различных лингвистических задач. Корпусная лингвистика занимается разработкой общих принципов построения и использования лингвистических корпусов данных с использованием компьютерных технологий. Она использует три приема: автоматическое извлечение сведений о языке из...
75858. Методи викладання іноземної мови. Особливості програм аудіолінгвального та аудіовізуального підходів 48 KB
  Особливості програм аудіолінгвального та аудіовізуального підходів Аудіолінгвальний метод Аудіолінгвальний метод створений Чарльзом Фрізом 18871967 та Робертом Ладо 1915 в США в 4050і роки XX ст. Ця вимога порівнювати мовні системи відрізняє аудіолінгвальний метод від усіх інших прямих та непрямих методів. Суть запропонованого Фрізом і Ладо методу який пізніше був названий американським методистом Нельсоном Бруком аудіолінгвальним полягає в роботі зі структурами оскільки на їх думку знати мову це уміти користуватися...
75860. Лінгвістичні засоби впливу в рекламі. Маніпулятивні стратегії 56.5 KB
  Что касается грамматической организации рекламных текстов, она представляет собой удивительное своеобразие на фоне нескончаемой однородности. Относительно порядка слов следует подчеркнуть употребление инверсии и пассивных конструкций - Detroit Edison is pleased to be