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


 

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

10759. Распознавание автомобильных номеров с помощью нейронных сетей 171.5 KB
  Курсовая работа на тему: Распознавание автомобильных номеров с помощью нейронных сетей. Содержание Введение. 3 Постановка задачи 4 Глава 1. Существующие системы и методы распознавания 4 Глава 2. Шаблоннонейросетевой метод распознавания 8 Ито
10760. Определение АИС. Теория системного анализа 57.5 KB
  Определение АИС. Теория системного анализа Определение АИС организационная совокупность программнотехнических средств технологических процессов и функциональноопределенных групп работников обеспечивающих сбор представление и накопление информационных ресу...
10761. Метафизика и онтология 159.5 KB
  Метафизика и онтология В современной европейской философии проблема бытия попрежнему остается фундаментальной как и во всей предшествующей истории философии. Занимаясь ею философия как и прежде отстаивает свое отличие от науки религии искусства обнаруживая уни
10762. Онтология ПРОБЛЕМА БЫТИЯ В ИСТОРИИ ФИЛОСОФИИ 181 KB
  Онтология ПРОБЛЕМА БЫТИЯ В ИСТОРИИ ФИЛОСОФИИ. Онтология выделилась из учений о бытии природы натурфилософии как учение о самом бытии еще в древнегреческой философии. Хотя специального терминологического обозначения у него не было. Бытие это чистое существова...
10763. Философское осмысление бытия. Философское понимание материи 104.5 KB
  Блок 1. Философское осмысление бытия Н. Лобковиц От субстанции к рефлексии. Пути западноевропейской метафизики. Если мы исходя из философии природы поставим вопрос: Что же есть в собственном смысле слова или соответственно Что означает быть или Что так
10764. История философии Запад-Россия-Восток. Философия Николая Кузанского 134.5 KB
  История философии Запад-Россия-Восток Философия Николая Кузанского. Современник многих итальянских гуманистов Николай Кузанский 1401-1464 один из самых глубоких философов эпохи Возрождения. Он был родом из Южной Германии местечко Куза совсем незнатного происхождени...
10765. Проблема бытия в классической философии (от Античности до эпохи Нового Времени) 47.5 KB
  Проблема бытия в классической философии от Античности до эпохи Нового Времени Онтология выделилась из учений о бытии природы натурфилософии как учение о самом бытии еще в древнегреческой философии. Хотя специального терминологического обозначения у него не было....
10766. Онтология. Учение о развитии. Категории пространства и времени в философии Нового времени 145 KB
  Онтология. Учение о развитии. Категории пространства и времени в философии Нового времени. Устойчивый интерес к пространственновременной проблематике в философии и науке Нового времени объясняется тем что пространство движение а значит и время относились к
10767. Религия и естествознание 103 KB
  Религия и естествознание МАКС ПЛАНК Многоуважаемые дамы и господа В прежние времена естествоиспытатель желая рассказать широкому кругу лиц состоящему не только из специалистов о теме относящейся к своей работе был вынужден для того чтобы пробудить у слушате