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


 

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

60988. ФОРМУВАННЯ МОВНОЇ ОСОБИСТОСТІ В БІЛІНГВАЛЬНОМУ СЕРЕДОВИЩІ 79.5 KB
  У сучасних умовах розбудови Української держави особливої актуальності набула проблема становлення особистості яка здатна вправно володіти засобами рідної мови в усіх видах мовленнєвої діяльності.
60989. УРОВНЕВАЯ ДИФФЕРЕНЦИАЦИЯ НА УРОКАХ ИНФОРМАТИКИ ОБЩЕОБРАЗОВАТЕЛЬНОЙ ШКОЛЫ 861.5 KB
  Задания репродуктивного уровня включают в себя обязательный уровень образования. Ученикам дается алгоритм для решения таких задач они выполняют задания пошагово исходя из общего алгоритма решения.
60990. Створення умов для вільного розвитку особистості дитини в процесі навчально-виховної діяльності 1.28 MB
  Педагогічний колектив її прагнув створити умови для вільного розвитку особистості дитини в процесі навчально-виховної діяльності; щоб кожен день у школі був для учнів радісним від навчання від спільної корисної справи від...
60991. Стилістичні засоби фразеології 42 KB
  Мета уроку: розширити знання учнів про стилістичні засоби фразеології, дати поняття фразеологічних синонімів, ознайомити із стилістичною диференціацією стійких мовних одиниць; формувати вміння й навички стильового розподілу фразеологізмів...