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


 

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

3857. Методи розв’язування диференційних рівнянь у частинних похідних 130.5 KB
  Методи розв’язування диференційних рівнянь у частинних похідних Мета роботи: Засвоїти теоретичний матеріал і методи розв’язування диференційних рівнянь у частинних похідних, набути практичні навики знаходження їхніх наближених значень...
3858. Информационные возможности непрерывного канала связи 1.01 MB
  Дайте определение понятию «Информационные возможности» каналов связи на физическом уровне. Изобразите модель передачи информации по каналу с помехами с описанием количественных характеристик. Под информационными возможностями канала будем понимат...
3859. Експлуатація повітряних суден 726 KB
  Експлуатація повітряних суден. На методологічній основі вивчення авіаційної техніки як об'єкту експлуатації, конструктивно-експлуатаційних властивостей і показників повітряних суден, розглянуті структура та зміст системи технічної експлуатації повітряних суден, її організаційні аспекти, а також характеристика програми та основних стратегій технічного обслуговування і ремонту АТ.
3860. Оцінка радіаційної обстановки після аварії на АЕС 62.61 KB
  Оцінка радіаційної обстановки після аварії на АЕС Завдання На північній АЕС сталася аварія з викидом шкідливих радіоактивних речовин в навколишнє середовище. Промисловий об’єкт розташований на відстані Rвід АЕС, може попасти в зону радіац...
3861. Фрейми. Інтерактивні Web-сторінки 33.5 KB
  Фрейми. Інтерактивні Web-сторінки Мета роботи - після виконання роботи студент повинен знати: базові команди мови HTML з реалізації фреймів основи мови HTML зі створення форм базові команди мови HTML із реалізації меню принципи створення інтеракт...
3862. Философия как дисциплина научного познания. Генезис философии 470 KB
  Генезис философии. Нужно отметить, что генезис является проблемой для самой философии, развиваясь, она постоянно сталкивается с проблемой собственного возникновения, ибо, только решив ее, философия сможет в полной мере осознать свою сущность. Сущест...
3863. Контрольна робота. Механіка матеріальної точки 86.01 KB
  Механіка матеріальної точки За заданими рівняннями руху х=х(t), у=у(y) (та z=z(t) для 2 рівня складності) матеріальної точки масою т =1кг встановити: Рівняння та вид траєкторії точки побудувати графік. Вектори переміщення, середньої швидкості та їх...
3864. Управляющие операторы или принятие решений в VB6 428.5 KB
  Управляющие операторы или принятие решений в VB6. Операторы, которые могут изменить последовательность выполнения операторов процедуры. Основанием для принятия решений в управляющих операторах являются условные (логические) выражения. Логические вы...
3865. Основні поняття та закони хімії. Конспект лекцій 3.89 MB
  ВСТУП Без знання основ хімії неможливе успішне вивчення технічних і технологічних дисциплін. Метою курсу є оволодіння студентами знань, необхідних їм для розуміння хімічних та технологічних явищ, які лежать в основі перетворень процесів зварювання...