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


 

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

55774. Внеклассное мероприятие по французскому языку 64.5 KB
  Bonjour mesdmes et messieurs Dns un instnt on v commencer Instllezvous dns votre futeil bien gentiment Доброго дня пані та панове За мить ми розпочнемо Розташовуйтесь зручніше ujourdhui nous nous sommes reunit pour jouer un peu et bien sûr pour svoir qui est plus intelligent prmi les onzièmes clsses. Permettezmoi de vous présenter des équipes : Дозвольте вам представити команди: Léquipe de 11 clsse ___________________ le chef est _______ Команда 11а класу Кістка вишні командир Тімченко Поліна Léquipe de 11B clsse...
55775. Пізнаємо себе 37 KB
  Слайд 1 Ми з вами будемо розмовляти про емоції почуття риси характеру навчимося керувати своїми емоціями. Слайд 2 Зверніть увагу зараз ми з вами знаходимося у дружньому колі ми всі рівні.
55776. Стиснення, архівування та розархівування даних. Програми-архіватори 48 KB
  Мета: Навчальна: сформувати вміння учнів використовувати програми-архіватори для стиснення архівації та розархівації файлів; Розвивальна: розвивати логічне мислення формувати алгоритмічний стиль думки поглибити знання учнів про впорядкування інформації в компютері...
55777. ЕТНОГРАФІЧНА ПОДОРОЖ УКРАЇНОЮ 64 KB
  До розповсюджених на Україні художніх промислів відносяться вишивка виробництво художніх тканин килимарство різьбярство взагалі художня обробка дерева гончарство гутне скло художнє ковальство обробка металів і ювелірних виробів розпис тканин...
55778. Зародження дисидентського руху в Україні та його особливості. Активізація опозиційного руху в 60-80-х роках XX ст. Василь Стус. Сходження на Голгофу слави. Життєвий і творчий шлях 387.5 KB
  Метою розробки є розкриття процесу зародження дисидентського руху зясування мети та основних цілей дисидентів ознайомлення студентів із провідними учасниками дисидентського руху визначення...
55779. Розробка «робочих матеріалів» як ефективний засіб навчання учнів при написанні творів за картиною 552 KB
  При складанні робочих матеріалів учитель має нагоду попередити виникнення певних помилок наприклад неправильне використання прийменників порушений граматичний звязок слів у словосполученні реченні уникати тавтології русизмів тощо.
55780. Розв’язування комбінаторних задач 532.5 KB
  Мета дидактична (навчальна): формування умінь і навичок розв’язування різних видів комбінаторних задач, застосовування основних теорем комбінаторики – правил суми та добутку, закріплення відомих методів і способів на практиці, вміння застосовувати знання в комплексі;
55781. Таблиці з логічними зв’язками 1.39 MB
  комірка формула книга немає вірної відповіді Що робить Excel якщо в складеній формулі знаходиться помилка повертає 0 як значення комірки виводить повідомлення про тип помилки як значення комірки виправляє помилку у формулі видаляє формулу з помилкою Яке з посилань є абсолютним З22 R1C2 5 5 Впорядкування значень діапазону коміркок у певній послідовності називають. електронні таблиці графіки й діаграми діапазон комірок сортування й фільтрація Яких форматів числових даних не існує числовий грошовий процентний округлений Логічна функція...
55782. Методична розробка з інженерної графіки, збірка завдань та рекомендацій до виконання розрахунково-графічних завдань 4.87 MB
  Мета розробки - надання допомоги студентам в освоєнні теоретичних і практичних знань, графічних умінь і навиків, активізації процесу і пізнавального інтересу. Розвитку просторових уявлень, мислення і творчих здібностей.