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


 

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

75992. Овочі. Т. Коломієць «Лічилка». Загадки 69.5 KB
  Активізувати словниковий запас дітей. Удосконалювати і розвивати орфоепічні вміння; пам’ять, увагу, спостережливість, відповідати на запитання українською мовою. Виховувати любов до усної народної творчості, почуття любові до української мови.
75993. Ніхто не забутий, ніщо не забуто! 53 KB
  Мета. Поглибити знання дітей про Велику Вітчизняну війну, удосконалювати навички виразного, свідомого читання; розвивати мовлення учнів, вміння висловлювати власну думку; виховувати почуття поваги до героїв війни, гордості за наше героїчне минуле.
75994. «Пандора» (за поемою Овідія «Метаморфози») 55.5 KB
  Анотація: Розробка комбінованого уроку українського позакласного читання на заявлену тему у 4 класі мета якого продовжувати ознайомлювати учнів з міфами; вчити дітей аналізувати твір складати план розвивати уявлення учнів про світове значення міфології виховувати повагу до історичної спадщини.
75995. Азбука дороги — дорожные знаки 464.5 KB
  Цель: расширить знания учащихся о дорожных знаках, учить называть группы дорожных знаков, научить различать дорожные знаки, повторить правила уличного движения для пешеходов, развивать умения самостоятельно пользоваться полученными знаниями в повседневной жизни...
75996. Дорога в школу. Школа «Светофорных наук». Современные средства передвижения 49.5 KB
  Школа Светофорных наук. Всех принять участие в уроке приглашаем И важные правила запомнить разрешаем Приветствуем друзей слева и справа Знать правила дорожные это не забава Пожимаем друзьям множество рук И приглашаем в школу Светофорных наук...
75997. Вивчи Правила, знай і завжди їх пам’ятай 2.77 MB
  Ми завітаємо в гості до казки де зустрінемося з Дідусем Правила Руху Казкою живими Дорожніми знаками Бабою Ягою і навіть зі славнозвісним Світлофором Івановичем. Знаки треба розставити вчасно І розмітку накреслити ясно Світлофори усі засвітити А у горах тунелі пробити...
75998. Безпечний перехід вулиці 840.5 KB
  Мета. Ознайомити учнів з місцями, де можна переходити вулицю; як безпечно переходити проїжджу частину дороги; які знаки, прилади, лінії допомагають безпечному переходу; вчити практично визначати безпечні місця переходу вулиці на шляху додому...
75999. Перехрестя долі Кобзаря. Літературно-музичний вечір для учнів 5 – 8 класів 100.5 KB
  Мета: вшанувати великого Кобзаря, поглибити знання учнів про тяжку долю Шевченка та українського народу; розвивати творчі здібності учнів, артистичність; виховувати любов і повагу до спадщини, яку нам залишив поет, учити учнів наслідувати Т.Шевченка та виконувати його заповіти.
76000. Письмовий переказ «Допоможи птахам» 45.5 KB
  Мета: вчити виявляти зміни що сталися у неживій природіу житті птахів удосконалювати навички чітко і повно відповідати на запитання; розвивати спостережливість вміння передавати свої враження від навколишнього; виховувати у дітей дбайливе ставлення до птахів бажання допомагати їм.