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

52 чел.

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


 

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

4726. Анализ организации устройства планирования и оборудования торгового предприятия на примере конкретного магазина - № 19 Борисовского ГПТ 480.5 KB
  Торговля Республики Беларусь, как одна из важных отраслей народного хозяйства на пути рыночных преобразований в настоящее время столкнулась с рядом проблем, которые привели эту отрасль в состояние глубокого кризиса. Кризис экономики в РБ за...
4727. Расчет электрического освещения 2.21 MB
  В цехе используется технологическое оборудование, которое и является основным потребителем электроэнергии, но в цехе есть и цепь освещения, которая потребляет сравнительно малое количество электроэнергии. На территории медногорского, термического отделений и в сварочном посту...
4728. Кривая производственных возможностей. Схема экономического кругооборота 68.5 KB
  Кривая производственных возможностей: содержание и графическое изображение. Нарисовать схему экономического кругооборота в рыночной экономике. Раскрыть содержание внутреннего и внешнего круга кругооборота. Экономическая теория изучает деятельнос...
4729. Социальная структура и социальная стратификация общества 135 KB
  Социальная структура и социальная стратификация общества. Понятие социальной структуры и социальной стратификации общества. Причины социальной стратификации. Методологические подходы к анализу социальной стратификации (марксистское учени...
4730. Соотношения между допусками размеров, формы и расположения поверхностей 155 KB
  Соотношения между допусками размеров, формы и расположения поверхностей Допуски размеров фактически полностью определяют точность формы и расположения поверхностей. Поскольку разнотолщинности призматической детали ограничена размерами...
4731. Проблемы отклонения социального поведения личности в условиях российского общества 94.5 KB
  Введение Девиантное поведение, понимаемое как нарушение социальных норм, приобрело в последние годы массовый характер и поставило эту проблему в центр внимания социологов, социальных психологов, медиков, работников правоохранительных органов. Опреде...
4732. Расчет стержневой конструкции на сложное сопротивление 135 KB
  Пояснительная записка представляет собой отчет о выполнении курсовой работы. Дано подробное решение стержневой конструкции на сложное сопротивление. Приведена исходная схема конструкции, построены эпюры поперечных и нормальных сил, а также...
4733. Соціологія, як наука. Її місце в системі наук 910.96 KB
  Предмет соціології та її місце в системі суспільної науки. Структура та функції соціології. Мета вивчення соціології. Societas – суспільство. Logos – наука...
4734. Современные проблемы отечественной энергетики 49.5 KB
  Введение В данном реферате отображены некоторые проблемы, стоящие перед энергетическим сектором страны, и возможные пути их решения. В работе рассмотрены вопросы выработки ресурса энергетического оборудования, эксплуатирующегося в РАО ЕЭС России...