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


 

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

33506. Поняття, предмет кримінального права України 31.5 KB
  Кримінальне право як самостійна окрема галузь права має низку ознак як загальних для всіх галузей права так і специфічних тільки для неї. Норми кримінального права це узагальнені правила що охоплюють безліч відповідних життєвих ситуацій індивідуальних випадків. Таким чином кримінальне право як галузь права це система сукупність юридичних норм а по суті законів прийнятих Верховною Радою України що встановлюють які суспільна небезпечні діяння є злочинами і які покарання підлягають застосуванню до осіб що їх вчинили.
33507. Призначення покарання за сукупністю вироків 31 KB
  71 сукупність вироків має місце там де засуджений після постановлення вироку але до повного відбуття покарання вчинив повий злочин. Таким чином при сукупності вироків: а постановлений вирок яким особа засуджена до певної міри покарання; б це покарання ще цілком не відбуте засудженим; в новий злочин вчинений після постановлення вироку але до повного відбуття покарання. 71 якщо засуджений після постановлення вироку але до повного відбуття покарання вчинив новий злочин суд до покарання призначеного за новим вироком повністю або...
33509. Один день Ивана Денисовича 13.61 KB
  Рассказывается об одном дне из жизни заключённого русского крестьянина и солдата Ивана Денисовича Шухова в январе 1951 года. Один день Ивана Денисовича Солженицына привлекает художественным исследованием характера Ивана Шухова не через какоето исключительное событие лагерной жизни побег поединок со следователем смерть а через описание одного дня от подъема до отбоя. Давайте вглядимся в тот мир вещей что сложился вокруг Ивана Денисовича: белая тряпочка чтоб рот на морозе прикрывать ботинки валенки вязанка шапка ложка...
33510. Поэты советского времени 14.47 KB
  Маяковский смог писать на эти же темы но так что бы выделиться из толпы. Маяковский выдающийся поэт футурист в каждом хлёстком слове бессмертных произведений которого бескомпромиссность и убеждённость трагедия и сарказм. одился Владимир Маяковский 7 июля 1893 года в небольшом грузинском посёлке в семье лесничего. Маяковский ушёл из жизни в возрасте 37 лет выстрелив себе в сердце из револьвера.
33511. Лирика периода Великой Отечественной войны (основные темы, художественные особенности) 16.05 KB
  Жди меня и я вернусь Если бы нас своим могуществом. Жди меня и я вернусь Всем смертям назло стихотворение К. Феномен Жди меня вырезаемого перепечатываемого и переписываемого посылаемого с фронта домой и из тыла на фронт феномен стихотворения написанного в августа 1941 на чужой даче в Переделкино адресованного вполне конкретной земной но в эту минуту далекой женщине выходит за рамки поэзии. Жди меня молитва атеиста заговариванье судьбы хрупкий мост между жизнью и смертью и оно же опора этого моста.
33512. Абрамов. Деревенская тематика 15.05 KB
  В повести “Алька†проблема выбора героем верного пути своего места в жизни. Алька находится в поисках своего “яâ€. Алька хочет показать себя зачастую преувеличивая истинные значения. Алька решает остаться в деревне но приехав в город за вещами теряет решительность.
33513. Анализ поэмы 13.68 KB
  Он открыл новый язык новую реальность нового героя и новый слой в словесности брежневской эпохи. Как понятно уже из заглавия книги цель путешествия героя Петушки подмосковная станция где его ждет возлюбленная. Не случайно в композиционном центре поэмы в ОреховеЗуеве описывается сон героя в котором победоносная революция овладевающая всеми винными магазинами района погибает оттого что на нее решительно никто не обращает ни малейшею внимания. Сочетание ироничности и трагичности маргинальное и интеллектуальности в фигуре главного...
33514. Метод соцреализма в литературе (идейно-тематическая нормативность, концепция личности) 15.02 KB
  Социалистический реализм художественный метод литературы и искусства представляющий собой эстетическое выражение социалистически осознанной концепции мира и человека обусловленной эпохой борьбы за установление и созидание социалистического общества. Изображение жизни в свете идеалов социализма обусловливает и содержание и основные художественноструктурные принципы искусства соцреализма.Социалистический реализм художественный метод литературы и искусства построенный на социалистической концепции мира и человека. Художник должен был...