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


 

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

32164. Продуктовый профиль. SWOT и SNW анализ по продукту 405 KB
  Важнейшая задача реального менеджмента и она же составляет ключевой элемент продуктовомаркетинговой стратегии программы это оптимизация продуктовой программы организации на текущий год и заданную стратегическую перспективу. Применяя при работе над продуктовым профилем конкретной организации предложенные трафареты рекомендуется использовать максимум конкретных данных а также иной формализованной и неформализованной информации по продукту которая должна готовиться заранее и представляться соответствующими службами организации. При...
32165. Корпоративная стратегия организации – система бизнес-стратегий 27.5 KB
  Корпоративная стратегия организации система бизнесстратегий В качестве ключевой стратегии в настоящем модуле предложена продуктовомаркетинговая стратегия. к разработке общей стратегии организации как системы стратегий ее относительно обособленных бизнесов и их централизованного обеспечения. Важнейшим направлением развития современной предпринимательской организации является ее становление как системы которая эффективно сочетает в себе два главных элемента: подсистему из небольшого количества относительно обособленных бизнесов и...
32166. Система бизнес-стратегий: типовые модели: BCG. GE/McKinsey 46.5 KB
  Модель BCG. Модель BCG модель называется по имени фирмыразработчика: Boston Consulting Group или матрица доля рынка темп роста представляет особое отображение позиции конкретного бизнеса в стратегическом пространстве которое задается двумя координатными осями. Модель BCG предлагает следующий типовой набор стратегических решений по конкретным бизнесам в зависимости от их попадания в тот или иной квадрант матрицы: 1. Таким образом в конкретной ситуации на заданную стратегическую перспективу рост объема соответствующего рынка может...
32168. ПЕРЕСТРАХОВАНИе И СОСТРАХОВАНИЕ 118 KB
  Сущность и роль перестрахования. Методы перестрахования. Особенности перестрахования рисков у нерезидентов. Сущность и роль перестрахования.
32169. Доходы, расходы и прибыль страховщика 143.5 KB
  Расходы страховой компании. Главной особенностью деятельности страховой компании является то что в отличие от сферы производства где товаропроизводитель сначала осуществляет расходы на выпуск продукции а потом уже компенсирует их за счет выручки от реализации страховщик вначале аккумулирует средства которые поступают от страхователя создавая необходимый страховой фонд а лишь после этого несет расходы связанные с компенсацией убытков по заключенным страховым соглашениям. Двойственный характер деятельности страховщика одновременное...
32170. ФИНАНСОВАЯ НАДЕЖНОСТЬ СТРАХОВЩИКА 104.5 KB
  Особенностью деятельности страховщика является обеспечение страховой защиты при условии аккумулировании средств в виде поступлений страховых премий в страховые резервы. Использование средств страховых резервов имеет целевое назначение. Страховщик в отличие от промышленных и коммерческих предприятий принимает от страхователя деньги не в обмен на материальный товар или услуги а в обмен на услугу которая обеспечивает страховую защиту в виде будущих страховых выплат только тем страхователям которые понесли урон и требуют финансовой помощи....
32171. Сущность, функции и роль страхования 52.5 KB
  Сущность функции и роль страхования. Возникновение страхования и основные этапы его развития. Сущность и функции страхования. Принципы страхования.
32172. Страховая терминология и классификация 44.5 KB
  Характеристика основных понятий договора страхования. Классификация страхования. Характеристика основных понятий договора страхования. Страховые термины можно условно разделить на три подгруппы: Страховые понятия и термины выражающие наиболее общие условия страхования.