29366

Разрешения коллизий в хеш-таблицах методом рехеширования

Доклад

Информатика, кибернетика и программирование

Является не пустым возникает коллизия которую надо устранить путём выбора другой ячейки таблицы для имени S. Выбор такой ячейки производится:h1 = h p1mod N p1 – некоторое приращение. Если элемент таблицы h1 тоже не пустой то рассматривается новый элемент:h2 = h p2mod N hi = h pimod N до тех пор пока не будет найден элемент таблицы что1 элемент пустой тогда имя S в таблице отсутствует и записывается в таблице под инд. элементами таблицы должно быть минимальным. p1 = 1 p2 = 2 pi =...

Английский

2013-08-21

31.5 KB

55 чел.

34) Разрешения коллизий в хеш-таблицах методом рехеширования.
Пусть результатом вычисления 
хеш-функции для некоторого имени S является число h. Пусть элемент с этим инд-м h уже занят, т.е. является не пустым, возникает коллизия, которую надо устранить путём выбора другой ячейки таблицы для имени S. 
Выбор такой ячейки производится:
h1 = (h + p1)*mod N, p1 – некоторое приращение
Если элемент таблицы h1 тоже не пустой, то рассматривается новый элемент:
h2 = (h + p2)*mod N
- - - - - - - - - - - - - - -
hi = (h + pi)*mod N
, до тех пор пока не будет найден элемент таблицы, что
1) элемент пустой, тогда имя S в таблице отсутствует и записывается в таблице под инд.hi.
2) элемент с индексом hi является не пустым и содержит имя, совпадающее с именем hS , в этом случае хешир-е имя уже есть в таблице и не должно быть записано в таблице.
3) hi = h, т.е. таблица имен заполнена, т.е. нет пустых ячеек. 
В этом случае S нельзя записать в таблицу и процесс трансляции прекращён.
Операция деления по mod N при вычислении hi обеспечивает циклический просмотр адресов. С точки зрения эффективности организации 
хеш-табл. следует отметить, что время поиска элемента определяется количеством возник-х коллизий. Время вычисления хеш-функции является постоянной величиной, а количество коллизий должно быть уменьшено путем выбора соответствующего способа рехеширования. Чтобы уменьшить количество возник. коллизий приращение pi должно вычисляться с учётом 2-х условий:
- ожид-е число сравнения элемента S др. элементами таблицы должно быть минимальным.
- значение адресов hi должно равномерно распределяться по таблице.
В идеал. случае значение pi должно охватывать целые числа из [1,N-1] строго 1 раз.
Различ. варианты повторного хеширования, отлич-ся способом вычисления pi.

Линейное рехеширование.

p1 = 1, p2 = 2, …, pi = i
Использование этого 
рехеширования при поиске свободного элемента таблицы для записи имени S последовательно рассматриваются все элементы таблицы, начиная с инд. h, получ. в рез-те хеширования.
Оценка среднего числа сравнений при поиске в 
хеш-таблице с линейным рехешированием определяется выражением: Е = (1-К/2) / (1-К).
К = n / N, где n – число непуст. элементов, N – размер таблицы.

К = 0,1 Е = 1,06 
К = 0,5 Е = 1,5
К = 0,9 Е = 5,5
В сравнении с бинарным поиском в упорядоченной таблице, 
хеш-таблица с линейным рехешированием даёт существенно лучшие результаты.
N = 2^10 = 1024 и таблица заполн. на половину n = 512, то требуется в среднем 1,5 сравн., а при бинарном поиске 
Е = log2 n+1 = 10.
При использовании 
хеш-таблиц эффективный поиск как правило не зависит от размера таблицы, а определяется её заполнением.

Случайное рехеширование.

Основным недостатком линейного рехеширования является неравномерное распределение имён с одинаковым значением хеш-функции по таблице. Если несколько имён имеют одинак. знач., то эти имена собираются в цепочку с инд. h. Это определяет соотв-е число коллизий при повторном хешировании. Если записывается новое имя с h, то все имена с этим же значением h обязательно будут просматриваться. Чтобы исключить такое группирование имён в таблице используется случайное рехеширование.
Случайное рехеширование реализуется путём выбора в качестве значений pi последовательности псевдослучайных чисел. Для генерации такой последовательности требуется датчик случайных чисел, который формирует все числа [1,N-1] строго 1 раз. Такой датчик является прогр. И позволяет воспроизводить одну и ту же последовательность при одинаковых исходных данных. За счёт этого обеспеч-ся возможность поиска имён среди уже зап-х в таблицу. Простейший датчик случ. чисел, удовл-й указанному требованию может быть построен, если размер таблицы является степенью 2.
1) R = 1,
2) R = 5*R,
3) R = R*mod(4N),
4) pi = [R / 4] – округляется до меньшего целого,
5) Шаги 2 – 4 повторяются необходимое количество раз.
Если N = 4, то p1 = 1, p2 = 2, p3 = 3.
При использовании хеш-таблиц со случайным рехешированием для данного датчика случайных чисел эффективность поиска оценивается формулой:
Е = (-1 / К)*log2(1-K), где К = n / N – коэф. заполн.

К = 0,1 Е = 1,05 
К = 0,5 Е = 1,39
К = 0,9 Е = 2,56

Квадратичное рехеширование.

При этом pi = ai2 + bi + c, где a,b,c – некоторые константы. Квадратичное рехеширование используется, когда размер таблицы N – простое число. По сравнению сослучайным рехешированием этот метод обеспечивает ещё меньшее число коллизий за счёт равномерного распределения адресов по таблице, а также меньшее время приращения pi .

Рехеширование сложения.

p1 = h, p2 = 2*h, …, pi = i*h.
h- результат хеширования.
Получаем адреса:

hi = ( h + h ) mod N
hi = ( h + 2*h ) mod N
….
hi = ( h + i*h )mod N = h ( i + 1 )mod N
Недостаток:
 невозможность использования 0 элемента таблицы.


 

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

22963. Наукове пізнання 46.5 KB
  Це сукупність способів принципів пізнання прийомів і процедур якими керуються в тій або іншій галузі науки. Ця дисципліна входить до якоїсь галузі науки. Для сучасної науки в цілому характерним є методологічний плюралізм тобто вона прагне використовувати будьякі принципи і прийоми дослідження в їхньому сполученні і взаємодії. Питання етики науки.
22964. Філософський зміст буття 40.5 KB
  Форми буття. Це питання стосовно буття. Буття як філософська категорія означає умоосягаєму одвічну першореальність яка обумовлює все існуюче и пронизує його.
22965. Поняття про світогляд 53 KB
  Особливості ставлення людини до світу 2. А ми пристосовуємось до світу іншим способом ми активно перетворюємо його прагення пристосувати світ до себе змінюючи його своєю діяльністю олюднення світу тобто робити світ більш придатним до людини. Все це означає пізнання людини пізнання світу пізнання одночасно. Висновок: людині щоб існувати треба перетворювати дійність але для цього це перетворювання відбувається в голові людини.
22966. Історичні типи світогляду: світоглядні погляди або уявлення певної епохи 52 KB
  Будьте уважні термін філософія змінювався. Вперше в первинному розумінні терміном філософія позначалась уся сукупність зань про все в перекладі любов до мудрості. Філософія – це любов до мудрості це людська справа мудрими можуть будити лише боги а люди можуть тільки любити мудрість. Те що для буденної свідомості для релігії здається безсумнівною істиною те для філософії є вихідним пунктом роздуму над цим філософія думає.
22967. Форми філософського знання 51 KB
  Онтологія – теорія буття теорія дійсності розглядаються основні принципи що визначають устрій світу. Ми робимо такий висновок що Філософія – це найбільш пізній зрілий тип світогляду це система найбільш загальних теоретичних уявлень про взаємодію людини і світу. В людини є виначальні орієнтації визначаються особливостями її життєдіяльності і духовного світу. Ми змушені рахуватися з закономірностями зовнішнього світу.
22968. Найважливіші філософські питання 42 KB
  Теоретичний раціональний філософія наука. Духовний емоційноціннісний філософія релігія. Але філософія не є ні наукою ні релігією філософія це тип світогляду який повязаний з наукою і релігією не більше.
22969. Структура і архітектура мікропроцесора КР580ВМ80 (8080) 2.99 MB
  Найважливішим елементом у схемі мікропроцесора є мабуть арифметикологічний пристрій АЛП який здійснює обробку інформації. Інформація яка підлягає обробці операнди потрапляє до АЛП з внутрішньої шини даних розрядність якої складає у даного мікропроцесора вісім розрядів. Його можна записати до одного з робочих регістрів РР мікропроцесора: регістрів BCDE.
22970. Як працює мікропроцесор 1.86 MB
  Машинний цикл є процедура звернення процесора до пам’яті чи зовнішнього пристрою для запису читання або обробки інформації. Так наприклад двобайтова команда MVI B A9 тобто записати число А9 у регістр В виконується за два машинні цикли: Звернення до пам’яті за адресою що міститься у лічильнику команд. Пам’ять виставляє на ШД код команди MVI B = 06 H = 0000 0110 B. У другому машинному циклі цей другий байт видобувається з пам’яті і заноситься до робочого регістру В.
22971. Системний контролер.Керуючий пристрій. Мікропрогамування 2.88 MB
  Мікропрогамування Як вже йшлося вище слово стану видається мікропроцесором у першому такті кожного машинного циклу і триває тільки один такт. Тому слово стану повинно десь зберігатися напротязі усього циклу. Роль такого хранителя слова стану виконує спеціальний пристрій що є обов’язковою частиною мікропроцесорної системи і має назву системного контролера. Другою функцією системного контролера є перетворення коду слова стану в керуючі сигнали котрі безпосередньо подаються вже на основну пам’ять або зовнішні пристрої і керують їх роботою.