Открытая адресация. Двойное хеширование. Анализ открытой адресации с двойным хешированием

Санкт-Петербургский  Государственный университет

 

Факультет ПМ - ПУ

 

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

 

по дисциплине

«Дискретная математика»

 

Открытая  адресация. Двойное хеширование. Анализ открытой адресации с двойным  хешированием

 

 

 

 

 

                                           

 

 

 

 

          Выполнил: студент 109 гр.

                             Капустинский К.В..

 

                                                   Научный руководитель:

ассистент кафедры МТМПСУ Пешехонов К.А..

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Санкт-Петербург

2012

 

 

Содержание

 

Введение 3

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

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

Квадратичная адресация 5

Двойное хеширование 5

Анализ хеширования с открытой адресацией 6

Заключение 7

Приложение (демонстрационная программа) 7

Список литературы: 8

 

Введение

В повседневной жизни мы довольно-таки часто сталкиваемся с хешированием: словари и текстовые редакторы, списки Web-ссылок в браузерах, компиляторы (таблицы символов).

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

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

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

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

 

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

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

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

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

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

 

При выполнении вставки элемента, в случае, если ячейка с вычисленным индексом занята, необходимо проверять следующие записи таблицы по порядку до тех пор, пока не будет найден ключ К или пустая позиция в таблице. Для этого в исходную хеш-функцию добавляется еще один аргумент-номер исследования. То есть для каждого ключа К последовательность исследований <h(k,0), h(k,1), … ,h(k,m-1)>, где h(k, i)- хеш-функция, должна представлять собой перестановку множества <0,1, …, m-1>.

 

Пример: Пусть задана последовательность чисел: data={59,70,96,81,13,41,79}. И дана хеш-функция h(data, i)=data%10, то есть остаток от деления на 10. Размер хеш-таблицы m = 10. На основании исходных данных заполняем таблицу.

 

 

• Хеширование первых пяти ключей дает различные  индексы (хеш-адреса):
•  i = 59 % 10 = 9; i = 70 % 10 = 0; i = 96 % 10 = 6;
•  i = 81 % 10 = 1; i = 13 % 10 = 3.
•  Первая коллизия возникает между ключами 81 и 41 - место с индексом 1 занято. Поэтому просматриваем хеш-таблицу с целью поиска ближайшего свободного места, в данном случае - это i = 2.
•  Следующий ключ 79 также порождает коллизию: позиция 9 уже занята. Эффективность алгоритма резко падает, т.к. для поиска свободного места понадобилось 6 проб (сравнений), свободным оказался индекс i = 4.

Общее число  проб такого метода от 1 до n - 1 пробы на элемент, где n - размер хеш-таблицы

В дальнейшем анализе  будем исходить из предположения  равномерного хеширования: каждый ключ равновероятно может получить любую из m! перестановок последовательностей исследования таблицы независимо от других ключей.

Для открытой адресации обычно используют 3 метода вычисления последовательностей исследования: линейное, квадратичное и двойное  хеширование.

 

Линейное исследование

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

h(k,i)=(h’(k)+it)mod m, где h’(k) – вспомогательная хеш-функция. Для данного ключа k она задает первую исследуемую ячейку. Затем исследуется ячейка  [h’(k)+i*t] и так далее до [m-1]. Далее осуществляется переход в начало хеш-таблицы и исследование ячеек [0], [1] до [h’(k)-1]. 

Представленное исследование не сложно в реализации, однако с ним связана проблема первичной кластеризации: После добавления большого количества элементов в таблицу, возникает конфликт между новыми элементами и уже имеющимися, что в свою очередь заметно увеличивает время поиска.  Кластеры возникают вследствие того, что вероятность заполнения ячейки, которой предшествуют i заполненных, равна (i+1)/m. Если же кластер начинает расти, то его рост продолжается до тех пор, пока он не дойдет до соседнего кластера. Затем два кластера соединяются, создавая новый кластер еще большего размера, который соответственно растет еще быстрее, сливается с другими кластерами и так далее.

 

Квадратичное исследование

Квадратичное исследование использует хеш-функцию вида: h(k,i)=(h’(k)+c₁i+c₂i²)mod m,

где h’(k) – вспомогательная хеш-функция, а c₁, c₂ – некоторые, не равные нулю, константы. h’(k) так же задает начальную ячейку исследования, а остальные определяются  величинами, которые описаны квадратичной зависимостью от номера исследования. Данные способ работает много лучшего линейного пробирования, хотя и приводит к более мягкой вторичной кластеризации. Это происходит из-за того что если два ключа имеет одинаковую стартовую ячейку  для исследования, то последовательности исследования будут также одинаковы. То есть из h₁(k,0)=h₂(k,0) => h₁(k,i)=h₂(k,i).

Двойное хеширование

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

Сама хеш-функция имеет  вид: h(k,i)=(h₁(k)+ih₂(k))mod m, где h₁(k) и h₂(k) – вспомогательные хеш-функции. В отличие от линейного и квадратичного пробирований, последовательность исследований зависит от ключа k по двум параметрам: выбор стартовой ячейки и расстояние между двумя исследуемыми. Двойное хеширование также превосходит линейное и квадратичное в плане количества исследований(Ɵ(m²) при двойном хешировании, и Ɵ(m) при линейном и квадратичном), так как пара (h₁(k), h₂(k)) дает практически уникальную последовательность исследований.

 

Рассмотрим на примере. Пусть  дана хеш-таблица размером m=20 и 2 вспомогательные хеш-функции: h₁(k)=k mod 15 и h₂(k)=2+(k mod 12)

 

Хеш-таблица(m=20)

 

Индекс ячейки	0	1	2	3	4	5	6	7	…	19	20
Элемент		61		103		20		37		16

 

Допустим, требуется вставить число 16. 16 mod 15=1; 16 mod 12=4.После исследований что 1 и 7 ячейки заняты, исходный элемент вставляется в ячейку 19.

Для охвата всей таблицы  требуют, чтобы h₂(k) была взаимно простой с размером таблицы. Один из способов: выбрать в качестве m простое число и реализовать функцию h₂(k) таким образом, чтобы она возвращала натуральные значения, меньше m.

Анализ  хеширования с открытой адресацией

Анализ  хеширования с открытой адресацией выполняется при помощи коэффициента заполнения a=n/m, где n – количество элементов в таблице, а m – размер хеш-таблицы. Так как при открытой адресации на одну ячейку не может приходиться более одного элемента, следовательно, n ≤ m,а значит a ≤ 1. Анализ будем проводить из предположения равномерного хеширования. И для начала рассмотрим количество исследований в случае неуспешного поиска:

При неуспешном поиске каждая последовательность исследований завершается на пустой ячейке. Обозначим за T количество исследований при неуспешном поиске и за A_i - событие, обозначающее, что i-е исследование пришлось на занятую ячейку. Следовательно, событие {T≥i}=A₁∩A₂∩…A_i.  Для дальнейшего анализа ограничим вероятность {A₁∩A₂∩…A_i}, а, следовательно, и {T≥i}. Вероятность {A₁}=n/m. Соответственно вероятность того, что j-е исследование будет произведено над занятой ячейкой = (n-j+1)/(m-j+1) (C учетом того, что (j-1) исследование также были произведены над заполненными ячейками). Так как количество элементов в таблице не может превосходить ее размеры, то получаем что (n-j+1)/(m-j+1)  ≤  n/m. Обобщая полученный факт для всех i, приходим к выводу: вероятность {T≥i} = ∙ ∙…∙ ≤ = .                 Следовательно, математическое ожидание количества исследований представимо в виде:   ≤ = = .                                                                    Допустим, если таблица заполнена на 60%, то среднее количество исследований будет 1/(1-0.6)=2.5. Из всего этого можно сделать вывод, что при вставке элемента в таблицу требуется не более 1/(1-a) исследований.

Вторым  пунктом анализа будет математическое ожидание количества исследований при  удачном поиске. Из того, что при  вставке элемента в таблицу требуется  не более 1/(1-a) исследований,  следует, что, если k был (i+1)-м ключом, вставленным в таблицу, то математическое ожидание количества проб при поиске k не превышает 1/(1-i/m) = m/(m-i) (так как поиск ключа выполняется с той же последовательностью исследований, что и его вставка). Возьмем средние значения по всем n ключам. Это даст нам среднее количество исследований при удачном поиске: = = (H_m-H_m-n), где H_i = – гармоническое число. Пользуясь формулой ограничения суммы интегралом, получаем верхнюю границу математического ожидания количества исследований при успешном поиске: (H_m-H_m-n) = ≤  = ln = ln. Соответственно, если хеш-таблица заполнена наполовину, то  количество исследований при удачном поиске не превысит 1.387.

 

Заключение

Исходя  из представленных выше фактов и результатов  анализа математических ожиданий последовательностей  исследований, можно сделать  вывод:

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

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

Как логическое продолжение данной работы, будет  представлен набор из программ и  задач, которые в той или иной степени раскрывают особенности, как двойного хеширования, так и открытой адресации в целом:

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

 

Список литературы:

 

1. Кнут  Д., Искусство программирования, т.3. М.: Вильямс, 2000.
2. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 2001
3. http://cs5486.userapi.com/u62977828/docs/b2d8c5717431/10Hashing.pdf
4. http://www.intuit.ru/department/algorithms/staldata/38/
5. Вирт Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.
6. http://www.rulibrary.com/book-101-43.html