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

46 чел.

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


 

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

61764. Фонетика. Звуки и буквы 19.96 KB
  Цели: создать условия для формирования представления о том что в слове количество звуков и букв может совпадать или не совпадать; развивать навык грамотного письма; совершенствовать работу со словарными словами.
61765. Основные способы образования слов в русском языке 19.25 KB
  Научиться определять способы словообразования. Сначала давайте попробуем определить что такое словообразование Дети дают определение по образцу: словообразование это 1 раздел науки о языке который изучает способы образования новых слов...
61766. ПРАВОПИСАНИЕ СЛОВ С НЕПРОИЗНОСИМЫМИ СОГЛАСНЫМИ 20.25 KB
  Цель: развить умение проверять написание непроизносимых согласных. какие согласные называются непроизносимыми какие буквы в сочетаниях стн здн лнц являются орфограммами как проверить непроизносимый согласный...
61767. Буква Ь. Обозначение мягкости согласных на письме 19.67 KB
  Цель урока: Познакомить с буквой Ь мягкий знак. Учить читать слова и предложения с буквой Ь мягкий знак. квадрат с одной полоской согласный твёрдый глухой звук; квадрат с одной полоской и точкой согласный твердый звонкий звук...
61768. Особенности обособления приложений 23.61 KB
  Составьте предложение с приложением выделите приложение на письме и интонационно. Что такое приложение Определение выраженное существительным согласованным с определяемым словом в падеже Прочитайте ваши предложения выделяя интонационно приложение.
61769. Обозначение мягкости согласных звуков на письме с помощью буквы ь 20.11 KB
  Два пальчика с лева отступили с заглавной буквы прописываем букву е и ё целую строчку чередуя эти буквы. Ребята с новой строчки с заглавной буквы отступив два пальчика слева прописываем это слово в строчку.
61770. Работа с тканью. Разметка по шаблону. Игольница в обложке 29.44 KB
  Форма работы: индивидуальная фронтальная; Технология обучения: здоровосберегающая Доминирующая задача: мотивация учебной деятельности и способы постановки учебной задачи; Литература: Конышева Н. Подготовка к уроку 12мин...
61771. Прихватка для горячей посуды. Творческий проект 23.37 KB
  Оборудование: а для учителя: Материалы: учебник готовое изделие лоскутки ткани цветные нитки лист тетрадной бумаги в клетку булавки кусочек мела учебная таблица Раскрой ткани Виды швов панно для демонстрации выполнения шва; Инструменты: ножницы игла. б для учащихся: Материалы: лоскутки ткани цветные нитки; Инструменты: ножницы игла булавки. Сегодня на урок труда вы должны были принести лоскутки ткани цветные нитки булавки иголку и ножницы. Какой материал лучше взять для работы Название хлопчатобумажной ткани произошло...
61772. Конструирование из бумаги. Изготовление новогодней фонарика 21.76 KB
  Цель: углубление и развитие знаний и умений учащихся, связанных с первоначальными приемами обработки бумаги с помощью шаблона, резанием бумаги ножницами; совершенствовать навыки в вырезании по контуру из бумаги, развивать мелкую моторику рук...