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

49 чел.

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 элемента таблицы.


 

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

50211. Визначення довжини світлової хвилі за допомогою біпризми Френеля 459 KB
  2 Прилади і матеріали Біпризма Френеля джерело світла – лампочка розжарювання розсувна щілина оптичний мікроскоп вертикальна масштабна шкала лінійка світлофільтри Опис установки Для пояснення методу отримання інтерференційної картини за допомогою біпризми Френеля необхідно використати оптичну схему яка наведена на рис. 1 1 – джерело світла із змінними світлофільтрами; 2 – конденсорна лінза; 3 –розсувна щілина; 4 – біпризма Френеля; 5 – оптичний мікроскоп. Увімкнути джерело світла 1 в мережу 220 В.
50212. Вивчення особливостей коливальної системи ультразвукових верстатів і визначення змін швидкості робочої подачі інструмента при прошиванні отвору 139.5 KB
  Перетворювача електричних коливань у механічні; Концентратора трансформатора пружних коливань який збільшує амплітуду коливань перетворювача та погоджує параметри перетворювача та навантаження; Виконують роль ланок резонансної довжини при пере дачі коливань від перетворювача інструмента та в робочу зону. Амплітуда коливань торця перетворювача звичайно не більше за 5.
50213. Дослідження властивостей напівпровідників методом ефекту Холла 75 KB
  Схема вимірювання питомого опору зразка і холлівської різниці потенціалів зображена на рис. – досліджуваний зразок; 1 – зонд для вимірювання холлівської напруги; 2 – зонд для вимірювання питомого опору. Зразки на яких проводяться вимірювання мають форму паралелепіпеда і закріплені на спеціальному держаку. Зонди для вимірювання питомого опору та холлівської напруги припаюють до зразка припоєм підібраним так щоб зменшити перехідний опір.
50215. Визначення радіуса кривизни лінзи допомогою кілець Ньютона 235 KB
  1 вміти описати утворення інтерференційних смуг однакової товщини та кілець Ньютона 2.5 Прилади і матеріали Мікроскоп плоскоопукла лінза великого радіуса кривизни плоскопаралельна пластинка освітлювач з блоком живлення світлофільтри Теоретичні відомості та опис установки Оптична схема для спостереження кілець Ньютона у відбитому світлі в даній лабораторній роботі наведена на рис. Якщо визначити експериментально радіуси темних – го і – го кілець Ньютона то із співвідношень 2.
50216. Проблеми та шляхи розвитку міжнародного ринку інформаційних технологій 557.5 KB
  Дослідження сутності міжнародного ринку інформаційних технологій та його ролі в світовій економіці; класифікація обʼєктів ринку інформаційних технологій; аналіз розвитку міжнародного ринку інформаційних технологій; знаходження механізму регулювання світового ринку інформаційних технологій; відображення напрямків розвитку міжнародного ринку інформаційних технологій.
50217. КЕРУВАННЯ ЕНЕРГЕТИЧНИМИ ПАРАМЕТРАМИ ЛАЗЕРНОЇ ТЕХНОЛОГІЧНОЇ УСТАНОВКИ. ККД ЛАЗЕРА 702 KB
  ККД ЛАЗЕРА Ціль роботи: вивчити склад і пристрій електричної частини лазерної технологічної установки ЛТУ; ознайомитися з етапами перетворення енергії в лазерних установках і з методами виміру енергетичних параметрів лазерного випромінювання; зняти енергетичну характеристику ЛТУ залежно від параметрів схеми накачування; визначити ККД лазера при різних режимах його роботи. Устаткування й прилади Лазерна технологічна установка Квант16 ; вимірювальник енергії ИКГ1М; лазер газовий ЛГ105.1: індуктивноємнісний перетворювач...
50218. Развитие околоносовых пазух ребенка, связь со становлением зубной дуги. Причины воспалительных изменений околоносовых пазух и возможность внутричерепных осложнений 15.54 KB
  Околоносовые пазухи у новорожденных недоразвиты и формируются в процессе развития лицевых костей и роста ребенка. При рождении у ребенка имеются две околоносовые пазухи: достаточно хорошо развитая решетчатая и рудиментарная
50219. ИЗУЧЕНИЕ ЗАТУХАЮЩИХ ЭЛЕКТРОМАГНИТНЫХ КОЛЕБАНИЙ В КОЛЕБАТЕЛЬНОМ КОНТУРЕ С ПОМОЩЬЮ ОСЦИЛЛОГРАФА 242 KB
  Цель работы: Изучение с помощью электронного осциллографа электромагнитных колебаний возникающих в колебательном контуре содержащем индуктивность емкость и активное сопротивление; изучение условий возникновения затухающих колебаний в контуре; расчет основных...