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

56 чел.

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


 

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

85991. СУБЪЕКТЫ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 93.64 KB
  События в мире показывают что закономерный характер развития международных отношений требует иного подхода и иных оценок которые не сразу адекватно воспринимаются исследователями дисциплины. Сознательная деятельность людей как проявление особенностей исторического детерминизма Естественно-историческое развитие международных отношений не отрицает а предполагает сознательную деятельность людей. Выше мы уже выяснили что основной функцией международных отношений является процесс взаимодействия субъектов.
85992. ГЕОПОЛИТИЧЕСКИЕ АСПЕКТЫ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 82.92 KB
  Например в России прошел II Всероссийский конгресс политологов а в Беларуси ряд международных конференций и семинаров. Распад СССР как геополитическая катастрофа Афганистан Косово и Средняя Азия как плацдармы контроля две войны России в Чечне с целью сохранения целостности страны и контроля за добычей нефти в Каспии. В данном случае он просто повторил опыт царской России. Замятин приводит в этой связи интересный пример: Так политическое и военное соперничество России и Великобритании в Средней Азии во второй половине XIX в.
85993. ОСНОВНЫЕ ТЕОРИИ, МЕТОДИКИ И СТРУКТУРЫ ПРИНЯТИЯ РЕШЕНИЙ ВО ВНЕШНЕЙ ПОЛИТИКЕ 59.97 KB
  Теории и анализ принятия решений в области внешней политики обозначились еще в 1950е гг. Объектом теорий принятия решений во внешней политике являются не общие проблемы касающиеся например предмета и сущности международных отношений конфликта или другие а конкретные вопросы связанные с действиями государства. Некоторые исследователи справедливо отмечают что изучение детерминант внешней политики без учета процесса принятия решений может оказаться или напрасной потерей времени поскольку результаты не будут иметь практического значения...
85994. ВНЕШНЕПОЛИТИЧЕСКИЙ ПРОЦЕСС 60.01 KB
  Ответы на этот вопрос призваны дать социологический и политический анализы внешней политики. Втретьих существует четкое осознание противоречия между с одной стороны требованиями максимально высокого профессионализма во внешней патетике а с другой императивами сохранения и укрепления и в этой сфере демократических начал. Оно ведет к поиску путей и средств оптимального преодоления названного противоречия какими оказываются многочисленные общественные организации по проблемам внешней политики как внутри социальной и политической элит так...
85995. МЕСТО И РОЛЬ КОНФЛИКТОВ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 123.4 KB
  Понятие конфликта Проблема конфликта является одной из сложнейших в теории международных отношений. Оставаясь важнейшим элементом международных отношений она переходит в качественно иное состояние наполняя внутреннюю жизнь любого субъекта напряженностью и возможной взрывоопасностью. Хотя среди аналитиков нет единого мнения в вопросе определения конфликта они в общем соглашаются что под конфликтом в международных отношениях понимается особый вид внешнеполитического взаимодействия субъектов прежде всего государств который выражается в...
85996. ПОНЯТИЕ И СУЩНОСТЬ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 155.5 KB
  В русском языке понятие «международные отношения» существенно расходится с вроде бы родственным ему «international relations» в английском языке, на котором почти исключительно создавалась эта наука. В нашем понимании «международные отношения» в изначальном и прямом...
85997. ОСОБЕННОСТИ СОВРЕМЕННОГО МИРА И ИХ ВЛИЯНИЕ НА МЕЖДУНАРОДНЫЕ ОТНОШЕНИЯ И ВНЕШНЮЮ ПОЛИТИКУ РЕСПУБЛИКИ БЕЛАРУСЬ 56.64 KB
  В современных условиях глобализация как важнейшая особенность международных отношений вызывает неоднозначную оценку. Сущность глобализации Сам термин глобализация по своей внутренней определенности предполагает формирование подлинного мира в котором по мнению некоторых аналитиков стираются географические границы социальных и культурных систем и сами люди во все большей степени осознают исчезновение подобных границ. Тем не менее глобализация имеет объективные источники и следовательно является естественным ходом истории. Таким образом...
85998. МЕТОДОЛОГИЧЕСКИЕ ПРИНЦИПЫ И ОСНОВНЫЕ КАТЕГОРИИ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 72.11 KB
  Поскольку в нашем пособии рассматривается интеллектуальная карта дисциплины международных отношений ни одно представление в этой академической области не будет приниматься само по себе. Кукулка выработать же объективистский взгляд на проблему международных отношений очень и очень трудно если вообще возможно. Так в основе историкоописательного метода лежат представления о дипломатических отношениях между государствами в тот или иной период развития истории; Он только описывает взаимодействие между основными субъектами международных...
85999. ОСНОВНЫЕ НАУЧНЫЕ НАПРАВЛЕНИЯ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 193.5 KB
  Поэтому в современной науке о международных отношениях все чаще обнаруживается стремление к переходу от теоретического к методологическому и нормативному модусу рассмотрения этих отношений, в границах которых она нередко воспринимается как форма делегитимизации