Реферат: Хеширование

МинистерствоОбразования РФ

Воронежскийгосударственный университет

ФакультетКомпьютерных наук

Кафедрапрограммирования и информационных технологий

Курсовая работа

по курсу «Технологии программирования» по теме

«Хеширование»

Выполнил: студент 3егокурса

ШадчневЕвгений

Проверил: доцент каф. ПиИТ

ХлебостроевВиктор Григорьевич

Воронеж 2003

<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">

Содержание

 TOC o «1-3» h z u ВведениеPAGEREF _Toc29536964 h 3

Хеш-функции_ PAGEREF _Toc29536965 h 4

Методделения_ PAGEREF _Toc29536966 h 4

Методумножения (мультипликативный)PAGEREF _Toc29536967 h 5

ДинамическоехешированиеPAGEREF _Toc29536968 h 5

Расширяемоехеширование (extendiblehashing)PAGEREF _Toc29536969 h 7

Функции,сохраняющие порядок ключей (Orderpreservinghashfunctions)PAGEREF _Toc29536970 h 8

Минимальноеидеальное хешированиеPAGEREF _Toc29536971 h 8

Разрешениеколлизий_ PAGEREF _Toc29536972 h 10

Методцепочек_ PAGEREF _Toc29536973 h 10

Открытаяадресация_ PAGEREF _Toc29536974 h 10

ЛинейнаяадресацияPAGEREF _Toc29536975 h 11

Квадратичнаяи произвольная адресацияPAGEREF_Toc29536976 h 11

Адресацияс двойным хешированием_ PAGEREF _Toc29536977 h 11

Удалениеэлементов хеш-таблицы_ PAGEREF _Toc29536978 h 12

Применениехеширования_ PAGEREF _Toc29536979 h 13

Хешированиепаролей_ PAGEREF _Toc29536980 h 13

ЗаключениеPAGEREF _Toc29536981 h 15

Приложение(демонстрационная программа)PAGEREF _Toc29536982 h 15

Списоклитературы:PAGEREF _Toc29536983 h 16


Введение

С хешированием мы сталкиваемсяедва ли не на каждом шагу: при работе с браузером (список Web-ссылок),текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором(таблица символов). По словам Брайана Кернигана, это«одно из величайших изобретений информатики». Заглядывая в адресную книгу,энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочениепо алфавиту является не чем иным, как хешированием.

Хеширование есть разбиениемножества ключей (однозначно характеризующих элементы хранения и представленных,как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества(наборы элементов), обладающие определенным свойством. Это свойство описываетсяфункцией хеширования, или хеш-функцией, и называется хеш-адресом. Решениеобратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу ониобеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращениеполучить доступ к элементу, характеризуемому заданным ключом (идеальнаяхеш-функция). Однако, на практике идеал приходится заменять компромиссом иисходить из того, что получающиеся наборы с одинаковым хеш-адресом содержатболее одного элемента.

Термин «хеширование» (hashing) в печатных работах по программированию появилсясравнительно недавно (1967 г., [1]), хотя сам механизм был известен и ранее.Глагол «hash» в английском языке означает «рубить,крошить». Для русского языка академиком А.П. Ершовым [2] был предложендостаточно удачный эквивалент — «расстановка», созвучный с родственнымипонятиями комбинаторики, такими как «подстановка» и «перестановка». Однако онне прижился.

Как отмечает Дональд Кнут [3],идея хеширования впервые была высказана Г.П. Ланом при создании внутреннегомеморандума IBM в январе 1953 г. с предложением использовать для разрешенияколлизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM–Жини Амдал – высказала идею использования открытую линейнуюадресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобноиспользовать остаток от деления на простое число. А. Думиописывал метод цепочек для разрешения коллизий, но не говорил об открытойадресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П.Ершовым (1957, [2]), который разработал и описал метод линейной открытой адресации.Среди других исследований можно отметить работу Петерсона(1957, [4]). В ней реализовывался класс методов с открытой адресацией приработе с большими файлами. Петерсон определилоткрытую адресацию в общем случае, проанализировал характеристики равномерногохеширования, глубоко изучил статистику использования линейной адресации наразличных задачах. В 1963 г. Вернер Букхольц [6]опубликовал наиболее основательное исследование хеш-функций.

К концу шестидесятых годовпрошлого века линейная адресация была единственным типом схемы открытойадресации, описанной в литературе, хотя несколькими исследователями независимобыла разработана другая схема, основанная на неоднократном случайном применениинезависимых хеш-функции ([3], стр. 585). В течение нескольких последующих летхеширование стало широко использоваться, хотя не было опубликовано никакихновых работ. Затем Роберт Моррис [5] обширный обзор по хешированию и ввел термин«рассеянная память» (scatterstorage).Эта работа привела к созданию открытой адресации с двойным хешированием.

Далее будут рассмотрены основныевиды хеш-функций и некоторые их модификации, методы разрешения коллизий,проблемы удаления элементов из хеш-таблицы, а также  некоторые варианты применения хеширования.

<span Arial",«sans-serif»;mso-fareast-font-family: «Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">
Хеш-функции

Хеш-функция – это некотораяфункция h(K), которая берет некий ключ Kивозвращает адрес, по которому производится поиск в хеш-таблице, чтобы получитьинформацию, связанную с K.Например, K– это номер телефона абонента, а искомая информация – егоимя. Функция в данном случае нам точно скажет, по какому адресу найти искомое.Пример с телефонным справочником иллюстрируется демонстрационной программой наприлагаемом компакт-диске.

Коллизия – это ситуация, когда h(K1) = h(K2), вто время как K1 ≠K2. В этом случае, очевидно,необходимо найти новое место для хранения данных. Очевидно, что количествоколлизий необходимо минимизировать. Методикам разрешения коллизий будетпосвящен отдельный раздел ниже.

Хорошая хеш-функция должнаудовлетворять двум требованиям:

ее вычисление должно выполняться очень быстро; она должна минимизировать число коллизий.

Итак, первое свойство хорошейхеш-функции зависит от компьютера, а второе – от данных. Если бы все данныебыли случайными, то хеш-функции были бы очень простые (несколько битов ключа,например). Однако на практике случайные данные встречаются крайне редко, иприходится создавать функцию, которая зависела бы от всего ключа.

Теоретически невозможно определитьхеш-функцию так, чтобы она создавала случайные данные из реальных неслучайныхфайлов. Однако на практике реально создать достаточно хорошую имитацию спомощью простых арифметических действий. Более того, зачастую можноиспользовать особенности данных для создания хеш-функций с минимальным числомколлизий (меньшим, чем при истинно случайных данных) [3].

Возможно, одним из самыхочевидных и простых способов хеширования является метод середины квадрата,когда ключ возводится в квадрат и берется несколько цифр в середине. Здесь идалее предполагается, что ключ сначала приводится к целому числу, для совершенияс ним арифметических операций. Однако такой способ хорошо работает до момента,когда нет большого количества нолей слева или справа. Многочисленные тестыпоказали хорошую работу двух основных типов хеширования, один из которыхоснован на делении, а другой на умножении. Впрочем, это не единственные методы,которые существуют, более того, они не всегда являются оптимальными.

Метод деления

Метод деления весьма прост –используется остаток от деления на M:

h(K) = KmodM

Надо тщательно выбирать этуконстанту. Если взять ее равной 100, а ключом будет случить год рождения, тораспределение будет очень неравномерным для ряда задач (идентификация игроков юношескойбейсбольной лиги, например). Более того, при четной константе значение функциибудет четным при четном Kи нечетным — при нечетном, что приведет к нежелательномурезультату. Еще хуже обстоят дела, если M – это степень счисления компьютера, поскольку при этомрезультат будет зависеть только от нескольких цифр ключа справа. Точно такжеможно показать, что Mне должно быть кратно трем, поскольку при буквенных ключахдва из них, отличающиеся только перестановкой букв, могут давать числовыезначения с разностью, кратной трем (см. [3], стр. 552). Приведенные рассужденияприводят к мысли, что лучше использовать простое число. В большинстве случаевподобный выбор вполне удовлетворителен.

Другой пример – ключ, являющийсясимвольной строкой С++. Хеш-функция отображает эту строку в целое числопосредством суммирования первого и последнего символов и последующеговычисления остатка от деления на 101 (размер таблицы). Эта хеш-функция приводитк коллизии при одинаковых первом и последнем символах строки. Например, строки«start» и «slant» будутотображаться в индекс 29. Так же ведет себя хеш-функция, суммирующая всесимволы строки. Строки «bad» и «dab»преобразуются в один и тот же индекс. Лучшие результаты дает хеш-функция,производящая перемешивание битов в символах.

На практике, метод деления –самый распространенный [7].

Метод умножения (мультипликативный)

Для мультипликативного хеширования используется следующаяформула:

h(K) = [M *((C * K) mod 1)]

Здесь производится умножениеключа на некую константу С, лежащую в интервале [0..1]. После этого беретсядробная часть этого выражения и умножается на некоторую константу M, выбранную таким образом,чтобы результат не вышел за границы хеш-таблицы. Оператор [ ] возвращаетнаибольшее целое, которое меньше аргумента.

Если константа С выбрана верно,то можно добиться очень хороших результатов, однако, этот выбор сложно сделать.Дональд Кнут (см. [3], стр. 553) отмечает, что умножение может иногдавыполняться быстрее деления. 

Мультипликативный метод хорошоиспользует то, что реальные файлы неслучайны. Например, часто множества ключейпредставляют собой арифметические прогрессии, когда в файле содержатся ключи {K, K + d, K + 2d, …, K + td}. Например, рассмотрим имена типа {PART1, PART2, …, PARTN}. Мультипликативный методпреобразует арифметическую прогрессию в приближенно арифметическую прогрессию h(K), h(K + d), h(K + 2d),…различных хеш-значений, уменьшая число коллизий посравнению со случайной ситуацией. Впрочем, справедливости ради надо заметить,что метод деления обладает тем же свойством.

Частным случаем выбора константыявляется значение золотого сечения φ = (√5- 1)/2 ≈ 0,6180339887. Если взять последовательность {φ},{2φ}, {3φ},…где оператор { } возвращает дробную часть аргумента, то на отрезке [0..1] онабудет распределена очень равномерно. Другими словами, каждое новое значениебудет попадать в наибольший интервал. Это явление было впервые замечено Я. Одерфельдом (J. Oderfeld) и доказано С. Сверчковски(S. Świerczkowski)(см. [8]). В доказательстве играют важную роль числа Фибоначчи. Применительно кхешированию это значит, что если в качестве константы С выбрать золотоесечение, то функция будет достаточно хорошо рассеивать ключи вида {PART1, PART2, …, PARTN}. Такое хеширование называетсяхешированием Фибоначчи. Впрочем, существует ряд ключей (когда изменениепроисходит не в последней позиции), когда хеширование Фибоначчи оказывается несамым оптимальным [3].

Динамическое хеширование

Описанные выше методы хешированияявляются статическими, т.е. сначала выделяется некая хеш-таблица, под ее размерподбираются константы для хеш-функции. К сожалению, это не подходит для задач,в которых размер базы данных меняется часто и значительно [9].  По мере роста базы данных можно

пользоваться изначальной хеш-функцией, теряя производительность из-за роста коллизий; выбрать хеш-функцию «с запасом», что повлечет неоправданные потери дискового пространства; периодически менять функцию, пересчитывать все адреса. Это отнимает очень много ресурсов и выводит из строя базу на некоторое время.

Существует техника, позволяющая динамическименять размер хеш-структуры [10]. Это – динамическое хеширование. Хеш-функциягенерирует так называемый псевдоключ (“pseudokey”), который используетсялишь частично для доступа к элементу. Другими словами, генерируется достаточнодлинная битовая последовательность, которая должна быть достаточна дляадресации всех потенциально возможных элементов. В то время, как пристатическом хешировании потребовалась бы очень большая таблица (которая обычнохранится в оперативной памяти для ускорения доступа), здесь размер занятойпамяти прямо пропорционален количеству элементов в базе данных. Каждая запись втаблице хранится не отдельно, а в каком-то блоке (“bucket”). Эти блоки совпадают сфизическими блоками на устройстве хранения данных. Если в блоке нет большеместа, чтобы вместить запись, то блок делится на два, а на его место ставитсяуказатель на два новых блока.

Задача состоит в том, чтобыпостроить бинарное дерево, на концах ветвей которого были бы указатели наблоки, а навигация осуществлялась бы на основе псевдоключа. Узлы дерева могутбыть двух видов: узлы, которые показывают на другие узлы или узлы, которыепоказывают на блоки. Например, пусть узел имеет такой вид, если он показываетна блок:

<table cellpadding=«0» ">

Zero

Null

Bucket

Указатель

One

Null

Если же он будет показывать надва других узла, то он будет иметь такой вид:

<table cellpadding=«0» ">

Zero

Адрес a

Bucket

Null

One

Адрес b

Вначале имеется только указательна динамически выделенный пустой блок. При добавлении элемента вычисляется псевдоключ,и его биты поочередно используются для определения местоположения блока.  Например (см. рисунок), элементы спсевдоключами 00… будут помещены в блок A, а 01… — в блок B.Когда А будет переполнен, он будет разбит таким образом, что элементы 000… и001… будут размещены в разных блоках.

<img src="/cache/referats/13377/image002.jpg" v:shapes="_x0000_i1025">

Расширяемое хеширование (extendiblehashing)

Расширяемое хеширование близко кдинамическому. Этот метод также предусматривает изменение размеров блоков помере роста базы данных, но это компенсируется оптимальным использованием места.Т.к. за один раз разбивается не более одного блока, накладные расходыдостаточно малы [9].

Вместо бинарного дереварасширяемое хеширование предусматривает список, элементы которого ссылаются наблоки. Сами же элементы адресуются по некоторому количеству i битов псевдоключа (см. рис). При поискеберется  iбитов псевдоключа и черезсписок (directory) находитсяадрес искомого блока. Добавление элементов производится сложнее. Сначалавыполняется процедура, аналогичная поиску. Если блок неполон, добавляетсязапись в него и в базу данных. Если блок заполнен, он разбивается на два,записи перераспределяются по описанному выше алгоритму. В этом случае возможноувеличение числа бит, необходимых для адресации. В этом случае размер списка удваиваетсяи каждому вновь созданному элементу присваивается указатель, который содержитего родитель. Таким образом, возможна ситуация, когда несколько элементовпоказывают на один и тот же блок. Следует заметить, что за одну операциювставки пересчитываются значения не более, чем одного блока. Удалениепроизводится по такому же алгоритму, только наоборот. Блоки, соответственно,могут быть склеены, а список – уменьшен в два раза.

<img src="/cache/referats/13377/image004.jpg" v:shapes="_x0000_i1026">

Итак, основным достоинствомрасширяемого хеширования является высокая эффективность, которая не падает приувеличении размера базы данных. Кроме этого, разумно расходуется место наустройстве хранения данных, т.к. блоки выделяются только под реальносуществующие данные, а список указателей на блоки имеет размеры, минимально необходимыедля адресации данного количества блоков. За эти преимущества разработчикрасплачивается дополнительным усложнением программного кода.

Функции, сохраняющие порядок ключей (Orderpreservinghashfunctions)

Существует класс хеш-функций, которые сохраняют порядокключей [11]. Другими словами, выполняется

K1 < <st1:place w:st=«on»>K2</st1:place> <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-char-type: symbol;mso-symbol-font-family:Wingdings">à

h(K1) < h(<st1:place w:st=«on»>K2</st1:place>)

Эти функции полезны длясортировки, которая не потребует никакой дополнительной работы. Другимисловами, мы избежим множества сравнений, т.к. для того, чтобы отсортировать объектыпо возрастанию достаточно просто линейно просканировать хеш-таблицу.

В принципе, всегда можно создатьтакую функцию, при условии, что хеш-таблица больше, чем пространство ключей.Однако, задача поиска правильной хеш-функции нетривиальна. Разумеется, онаочень сильно зависит от конкретной задачи. Кроме того, подобное ограничение нахеш-функцию может пагубно сказаться на ее производительности. Поэтому частоприбегают к индексированию вместо поиска подобной хеш-функции, если толькозаранее не известно, что  операцияпоследовательной выборки будет частой.

Минимальное идеальное хеширование

Как уже упоминалось выше,идеальная хеш-функция должна быстро работать и минимизировать число коллизий. Назовемтакую функцию идеальной (perfecthashfunction)[12]. С такой функцией можно было бы не пользоваться механизмом разрешенияколлизий, т.к. каждый запрос был бы удачным. Но можно наложить еще одноусловие: хеш-функция должна заполнять хеш-таблицу без пробелов. Такая функциябудет называться минимальной идеальной хеш-функцией. Это идеальный случай сточки зрения потребления памяти и скорости работы. Очевидно, что поиск такихфункций – очень нетривиальная задача.

Один из алгоритмов для поискаидеальных хеш-функций был предложен Р. Чичелли [13].Рассмотрим набор некоторых слов, для которых надо составить минимальнуюидеальную хеш-функцию. Пусть это будут некоторые ключевые слова языка С++.Пусть это будет какая-то функция, которая зависит от некоего численного кодакаждого символа, его позиции и длины. Тогда задача создания функции сведется ксозданию таблицы кодов символов, таких, чтобы функция была минимальной иидеальной. Алгоритм очень прост, но занимает очень много времени для работы.Производится полный перебор всех значений в таблице с откатом назад в случаенеобходимости, с целью подобрать все значения так, чтобы не было коллизий. Есливзять для простоты функцию, которая складывает коды первого и последнегосимвола с длиной слова (да, среди слов умышленно нет таких, которые даютколлизию), то алгоритм дает следующий результат:

Буква

Код

Буква

Код

Буква

Код

Буква

Код

Буква

Код

a

-5

e

4

i

2

n

-1

t

10

b

-8

f

12

k

31

o

22

u

26

c

-7

g

-7

l

29

r

5

v

19

d

-10

h

4

m

-4

s

7

w

2

Слово

Хеш

Слово

Хеш

Слово

Хеш

Слово

Хеш

Auto

21

Double

Int

15

Struct

23

Break

28

Else

12

Long

26

Switch

17

Case

1

Enum

4

Register

18

Typedef

29

Char

2

Extern

9

Return

10

Union

30

Const

8

Float

27

Short

22

Unsigned

24

Continue

5

For

20

Signed

3

Void

13

Default

7

Goto

19

Sizeof

25

Volatile

31

Do

14

If

16

Static

6

While

11

Подробный анализ алгоритма, атакже реализацию на С++ можно найти по адресу [12]. Там же описываются методыразрешения коллизий. К сожалению, эта тема выходит за рамки этой работы.

<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">
Разрешение коллизий

Составление хеш-функции – это невся работа, которую предстоит выполнить программисту, реализующему поиск наоснове хеширования. Кроме этого, необходимо реализовать механизм разрешенияколлизий. Как и с хеш-функциями существует несколько возможных вариантов,которые имеют свои достоинства и недостатки.

Метод цепочек

Метод цепочек – самый очевидныйпуть решения проблемы. В случае, когда элемент таблицы с индексом, которыйвернула хеш-функция, уже занят, к нему присоединяется связный список. Такимобразом, если для нескольких различных значений ключа возвращается одинаковоезначение хеш-функции, то по этому адресу находится указатель на связанныйсписок, который содержит все значения. Поиск в этом списке осуществляется простымперебором, т.к. при грамотном выборе хеш-функции любой из списков оказываетсядостаточно коротким. Но даже здесь возможна дополнительная оптимизация. ДональдКнут ([3], стр. 558) отмечает, что возможна сортировка списков по времениобращения к элементам. С другой стороны, для повышения быстродействия желательныбольшие размеры таблицы, но это приведет к ненужной трате памяти на заведомопустые элементы. На рисунке ниже показана структура хеш-таблицы и образованиецепочек при возникновении коллизий.

<img src="/cache/referats/13377/image005.jpg" v:shapes="_x0000_i1027">

Прекрасная наглядная иллюстрацияэтой схемы разрешения коллизий в виде Java-апплета вместе с исходным кодом на C++ представлена по адресу [14].

Открытая адресация

Другой путь решения проблемы,связанной с коллизиями, состоит в том, чтобы полностью отказаться от ссылок,просто просматривая различные записи таблицы по порядку до тех пор, пока небудет найден ключ Kили пустая позиция [3]. Идея заключается в формулированииправила, согласно которому по данному ключу определяется «пробная последовательность»,т.е. последовательность позиций таблицы, которые должны быть просмотрены привставке или поиске ключа K.Если при поиске встречается пустая ячейка, то можно сделать вывод, что K в таблице отсутствует, т.к.эта ячейка была бы занята при вставке, т.к. алгоритм проходил ту же самуюцепочку. Этот общий класс методов назван открытой адресацией [4].

Линейная адресация

Простейшая схема открытойадресации, известная как линейная адресация (линейное исследование, linearprobing) используетциклическую последовательность проверок

h(K), h(K — 1), …, 0, M – 1, M – 2, …, h(K) + 1

и описывается следующим алгоритмом([3], стр. 562). Он выполняет поиск ключа Kв таблице из Mэлементов.Если таблица не полна, а ключ отсутствует, он добавляется.

Ячейки таблицы обозначаются как TABLE[i], где 0 ≤ i< Mи могут быть или пустыми, или занятыми. Вспомогательная переменная Nиспользуетсядля отслеживания количества занятых узлов. Она увеличивается на 1 при каждойвставке.

Установить i= h(K) Если TABLE[i] пуст, то перейти к шагу 4, иначе, если по этому адресу искомый, алгоритм завершается. Установить i = i – 1, если i < 0, то i = i +M. Вернуться к шагу 2. Вставка, т.к. поиск оказался неудачным. Если N = M – 1, то алгоритм завершается по переполнению. Иначе увеличить N, пометить ячейку TABLE[i] как занятую и установить в нее значение ключа K.

Опыты показывают ([3], стр. 564),что алгоритм хорошо работает в начале заполнения таблицы, однако по мерезаполнения процесс замедляется, а длинные серии проб становятся все болеечастыми.

Квадратичная и произвольная адресация

Вместо постоянного изменения на единицу, как в случае слинейной адресацией, можно воспользоваться следующей формулой [15]

h = h + a2,

где a– это номерпопытки. Этот вид адресации достаточно быстр и предсказуем (он проходит всегдаодин и тот же путь по смещениям 1, 4, 9, 16, 25, 36 и т.д.). Чем больше коллизийв таблице, тем дольше этот путь. С одной стороны, этот метод дает хорошее распределениепо таблице, а с другой занимает больше времени для просчета.

Произвольная адресация используетзаранее сгенерированный список случайных чисел для получения последовательности[15]. Это дает выигрыш в скорости, но несколько усложняет задачу программиста.

Адресация с двойным хешированием

Этот алгоритм выбора цепочки очень похож на алгоритм длялинейной адресации, но он проверяет таблицу несколько иначе, используя двехеш-функции h1(K) и h2(K). Последняя должна порождать значенияв интервале от 1 до M –1, взаимно простые с М. 

Установить i= h1(K) Если TABLE[i] пуст, то перейти к шагу 6, иначе, если по этому адресу искомый, алгоритм завершается. Установить c = h2(K) Установитьi= i – c, еслиi< 0, тоi= i +M. Если TABLE[i] пуст, то переход на шаг 6. Если искомое расположено по этому адресу, то алгоритм завершается, иначе возвращается на шаг 4. Вставка. Если N = M – 1, то алгоритм завершается по переполнению. Иначе увеличить N, пометить ячейку TABLE[i] как занятую и установить в нее значение ключа K.

Очевидно, что этот вариант будетдавать значительно более хорошее распределение и независимые друг от другацепочки. Однако, он несколько медленнее из-за введения дополнительной функции.

Дональд Кнут ([3], стр. 566)предлагает несколько различных вариантов выбора дополнительной функции. Если M – простое число и h1(K) = KmodM, можно положить h2(K) = 1 + (K mod (M – 1)); однако, если M – 1 четно (другимисловами, Mнечетно, что всегда выполняется для простых чисел), было былучше положить h2(K) = 1 + (K mod (M – 2)).

Здесь обе функции достаточнонезависимы. Гари Кнотт (GaryKnott) в 1968 предложил припростом Mиспользовать следующую функцию:

h2(K) = 1, если h1(K) = 0 и h2(K) = M– h1(K)в противном случае (т.е. h1(K) > 0).

Этот метод выполняется быстрееповторного деления, но приводит к увеличению числа проб из-за повышениявероятности того, что два или несколько ключей пойдут по одному и тому же пути.

Удаление элементов хеш-таблицы

Многие программисты настолькослепо верят в алгоритмы, что даже не пытаются задумываться над тем, как ониработают. Для них неприятным сюрпризом становится то, что очевидный способудаления записей из хеш-таблицы не работает. Например, если удалить ключ,который находится в цепочке, по которой идет алгоритм поиска, использующий открытуюадресацию, то все последующие элементы будут потеряны, т.к. алгоритм производитпоиск до первого незанятого элемента.

Вообще говоря, обрабатыватьудаление можно, помечая элемент как удаленный, а не как пустой. Таким образом,каждая ячейка в таблице будет содержать уже одно из трех значений: пустая,занятая, удаленная. При поиске удаленные элементы будут трактоваться как занятые,а при вставке – как пустые, соответственно.

Однако, очевидно, что такой методработает только при редких удалениях, поскольку однажды занятая позиция большеникогда не сможет стать свободной, а, значит, после длинной последовательностивставок и удалений все свободные позиции исчезнут, а при неудачном поиске будеттребоваться М проверок (где М, напомним, размер хеш-таблицы). Это будетдостаточно долгий процесс, так как на каждом шаге №4 алгоритма поиска (см.раздел Адресация с двойным хешированием) будет проверяться значение переменной i.

Рассмотрим алгоритм удаленияэлемента iпри линейной адресации.

Пометить TABLE[i] как пустую ячейку и установить j = i i = i– 1  или i = i + M, если iстало отрицательным Если TABLE[i] пуст, алгоритм завершается, т.к. нет больше элементов, о доступе к которым следует заботиться. В противном случае мы устанавливаем r = h(KEY[i]), где KEY[i] – ключ, который хранится в TABLE[i]. Это нам даст его первоначальный хеш-адрес.  Если i ≤ r < jили если r < j < iлибо j < i ≤ r(другими словами, если rциклически лежит между этими двумя переменным, что говорит о том, что этот элемент находится в цепочке, звено которой мы удалили выше), вернуться на шаг 1. Надо переместить запись TABLE[j] = TABLE[i] и вернуться на первый шаг.

Можно показать ([3], стр. 570),что этот алгоритм не вызывает снижения производительности. Однако, корректностьалгоритма сильно зависит от того факта, что используется линейное исследованиехеш-таблицы, поэтому аналогичный алгоритм для

еще рефераты
Еще работы по программированию, базе данных