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

45 чел.

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


 

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

34595. Соединенное Королевство: географическое положение, рельеф, природные условия, флора и фауна. Символы 40.5 KB
  Официально же она именуется Соединенное Королевство Великобритании и Северной Ирландии. В целом на их долю приходится приблизительно 1 3 площади Великобритании и бoльшая часть Северной Ирландии. В Северной Ирландии змей нет. Символы: Флаг Соединенного Королевства Великобритании и Северной Ирландии или как его принято называть Юнион Джек Union Jck является сочетанием трех крестов святых покровителей Англии прямой красный крест на белом поле крест Св.
34596. Столетняя война 17.15 KB
  Столетняя война наименование длительного военного конфликта между Англией и Францией 13371453 вызванного стремлением Англии вернуть принадлежавшие ей на континенте Нормандию Мен Анжу и др. а также династическими притязаниями английских королей на французский престол. война между Англией и Францией. причины войны: стремление Франции вытеснить Англию с югозапада страны провинция Гиень и ликвидировать этот последний оплот английской власти на франц.
34597. Династия Тюдоров. Генрих VII 19.17 KB
  Генрих VII Генрих VII Тюдор 28 января 1457 – 21 апреля 1509 – король Англии и государь Ирландии 1485 – 1509. Родители: Эдмунд Тюдор 1й граф Ричмонд; единоутробный брак короля Генриха VI Маргарита Бофорт. 1471 – гибель Генриха VI и принца Уэльского Генрих – почти единственный родственник Ланкастеров. Генрих поклялся в Ренне в случае захвата власти жениться на дочери Эдуарда IV Елизавете Йоркской.
34598. Реформация, противостояние католиков и протестантов 12.42 KB
  Первоначально Генрих VIII был противником Реформации книга против Лютера В защиту 7 таинств 1521 г. Генрих был женат на Екатерина Арагонской единственный ребенок – девочка Мария Тюдор. Поняв что мальчиков не будет Генрих решил добиться развода однако Папа Римский Климент VII на это не согласился. Генрих обвинил английское духовенство в неповиновении статуту статут запрещал признавать любое лицо назначенное Папой без утверждения королем заставил духовенство признать себя главой церкви Англии.
34599. Мария Тюдор 20.58 KB
  Известна как Мария Кровавая Мария Католичка. Мария была единственным выжившим ребенком Генриха от его первой жены Екатерины Арагонской. Франциск I король Франции стремился укрепить свои позиции через свадьбу Марии и французского дофина решение принято осенью 1518 Мария должна выйти замуж по достижении дофином 14летнего возраста если у Генриха не появится наследник мужского пола то корону наследует Мария.
34600. Война с Испанией. «Непобедимая Армада» 33.5 KB
  Непобедимая Армада. Однако в том же 1587 году английская эскадра адмирала Френсиса Дрейка совершила налет на Кадис где базировалась Непобедимая Армада и уничтожила около 100 кораблей. 20 мая 1588 года Непобедимая Армада в составе шести эскадр вышла в море из устья реки Тахо. Армада подвергалась постоянным нападениям более легких и маневренных английских судов адмирала Дрейка.
34601. Культура Англии в XIV –XV в. 20.06 KB
  В конце 14 века оформился единый английский язык. Однако в 14 – 15 веках среди английской знати особенно при дворе была широко распространена литература на французском языке. Огромную роль в развитии английской литературы сыграли Кентерберийские рассказы Джеффри Чосера вторая половина 14 века. В 70е годы 15 века в Англии появилось книгопечатание.
34602. Династия Стюартов: Яков I 20.19 KB
  Династия Стюартов: Яков I Яков VI Шотландский Яков I Английский; 19 июня 1566 – 1625 – король Шотландии Англии первый государь правивший Шотл. Шотландия 24 июля 1567 – восстание отец Якова умер убийцей считали Марию. 29 июля 1567 Стерлинг – Яков коронован Ш. Яков правил при регентском совете с 29 июля 1567 самостоятельно – с 12 марта 1578.
34603. Долгий парламент. Гражданская война (XVII в.) 40.5 KB
  Долгого парламента 16401653 гг. В состав Долгого парламента входило 516 членов Палаты общин и 150 – Палаты лордов. Немало было депутатов бывших членами памятного парламента 1628 г. Положение англиканской церкви стало первым объектом политической атаки парламента и вынужденных уступок короны.