хэш-функции (продолжение) Лекция 4

Универсальное хеширование Возможна ситуация когда ключи для хеширования выбираются при помощи конкретной хеш-функции и получаются n значений, которые будут хешироваться в одну и ту же ячейку таблицы, приводя к среднему времени выборки 0(n). Таким образом, любая фиксированная хеш-функция становится уязвимой, и единственный эффективный выход из ситуации случайный выбор хеш-функции, не зависящий от того, с какими именно ключами ей предстоит работать. Такой подход, который называется универсальным хешированием, гарантирует хорошую производительность в среднем, независимо от того, какие данные будут выбраны злоумышленником. Главная идея универсального хеширования состоит в случайном выборе хеш- функции из некоторого тщательно отобранного класса функций в начале работы программы. 2

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

Пусть Н конечное множество хеш-функций, которые отображают пространство ключей U в диапазон {0,1,2,..., m 1}. Такое множество называется универсальным, если для каждой пары различных ключей к,j Є U количество хеш- функций h Є H, для которых h(k) = h (j), не превышает |Н|/т. Другими словами, при случайном выборе хеш-функции из Н вероятность коллизии между различными ключами к и j не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества {0,1,2,..., m 1}, которая равна 1/m. Следующая теорема показывает, что универсальные хеш- функции обеспечивают хорошую среднюю производительность. В приведенной теореме n i, как уже упоминалось, обозначает длину списка Т [i]. 4

Следующая теорема показывает, что универсальные хеш-функции обеспечивают хорошую среднюю производительность. Теорема Пусть хеш-функция h, выбранная из универсального множества хеш-функций, используется для хеширования n ключей в таблицу Т размера m, с использованием для разрешения коллизий метода цепочек. Если ключ к отсутствует в таблице, то математическое ожидание Е[n h(k) ] длины списка, в который хешируется ключ к, не превышает а. Если ключ к находится в таблице, то математическое ожидание Е [n h(k) ] длины списка, в котором находится ключ к, не превышает 1 + а. 5

Следствие из данной теоремы гласит, что универсальное хеширование обеспечивает желаемый выигрыш: теперь невозможно выбрать последовательность операций, которые приведут к наихудшему времени работы. Путем рандомиза­ции выбора хеш-функции в процессе работы программы гарантируется хорошее среднее время работы алгоритма для любых входных данных. Следствие Использование универсального хеширования и разрешения коллизий методом цепочек в хеш-таблице с m ячейками дает математическое ожидание времени выполнения любой последовательности из n вставок, поисков и удалений, в которой содержится O(m) вставок, равное θ(n). 6

Построение универсального множества хеш-функций Построить такое множество довольно просто, что следует из теории чисел. Начнем с выбора простого числа р, достаточно большого, чтобы все возможные ключи находились в диапазоне от 0 до р 1 включительно. Пусть Z p обозначает множество {0,1,...,р 1}, a Z* множество {1,2,...,р 1}. Поскольку р простое число, мы можем решать уравнения по модулю р. Из предположения о том, что пространство ключей больше, чем количество ячеек в хеш-таблице, следует, что р> т. Теперь определим хеш-функцию h a,b для любых a Є Z p * и b Є Z p следующим образом: h a,b (к) = ((ак + b) mod р) mod т. (*) 7

Например, при р = 17 и m = 6 h 3,4 (8) = 5. Семейство всех таких функций образует множество H p,m = {h a,b : a Є Z p * и b Є Z p }. (**) Каждая хеш-функция h a,b, отображает Z p на Z m. Этот класс хеш-функций обладает тем свойством, что размер т выходного диапазона произволен и не обязательно представляет собой простое число. Поскольку число а можно выбрать р 1 способом, и р способами число b, всего во множестве H p,m содержится р(р 1) хеш-функций. Множество хеш-функций H p,m, определяемое уравнениями (*) и (**), является универсальным. 8

Открытая адресация При использовании метода открытой адресации все элементы хранятся непосредственно в хеш-таблице, т.е. каждая запись таблицы содержит либо элемент динамического множества, либо значение NIL. При поиске элемента мы систематически проверяем ячейки таблицы до тех пор, пока не найдем искомый элемент или пока не убедимся в его отсутствии в таблице. Здесь, в отличие от метода цепочек, нет ни списков, ни элементов, хранящихся вне таблицы. Таким образом, в методе открытой адресации хеш-таблица может оказаться заполненной, делая невозможной вставку новых элементов; коэффициент заполнения а не может превышать 1. 9

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

Вместо фиксированного порядка исследования ячеек 0,1,..., т 1 (для чего требуется θ(n) времени), последовательность исследуемых ячеек зависит от вставляемого в таблицу ключа. Для определения исследуемых ячеек мы расширим хеш-функцию, включив в нее в качестве второго аргумента номер исследования (начинающийся с 0). В результате хеш-функция становится следующей: h : U х {0,1,..., т 1} > {0,1,..., т 1}. В методе открытой адресации требуется, чтобы для каждого ключа к последовательность исследований {h (к, 0), h (к, 1),..., h (к, т 1)) представляла собой перестановку множества (0,1,..., m 1), чтобы в конечном счете могли быть просмотрены все ячейки хеш-таблицы. 11

В приведенном далее псевдокоде предполагается, что элементы в таблице Т представляют собой ключи без сопутствующей информации; ключ к тождественен элементу, содержащему ключ к. Каждая ячейка содержит либо ключ, либо значение NIL (если она не заполнена): H ASH _I NSERT (T, к) 1 i 0 2 repeat j h(k, i) 3 if T[j] = NIL 4 then T[j] к 5 return j 6 else i i until i = m 8 error Хеш-таблица переполнена 12

Алгоритм поиска ключа к исследует ту же последовательность ячеек, что и алгоритм вставки ключа к. Таким образом, если при поиске встречается пустая ячейка, поиск завершается неуспешно, поскольку ключ к должен был бы быть вставлен в эту ячейку в последовательности исследований, и никак не позже нее. (предполагается, что удалений из хеш-таблицы не было.) Процедура H ASH _S EARCH получает в качестве входных параметров хеш-таблицу Т и ключ к и возвращает номер ячейки, которая содержит ключ к (или значение NIL, если ключ в хеш- таблице не обнаружен): H ASH _S EARCH (T, к) i 0 repeat j h(k, i) if T[j] = к then return j i i +1 until T[j] = NIL или i = m return NIL 13

Процедура удаления из хеш-таблицы с открытой адресацией достаточно сложна. При удалении ключа из ячейки n мы не можем просто пометить ее значением nil. Поступив так, мы можем сделать невозможным выборку ключа к, в процессе вставки которого исследовалась и оказалась занятой ячейка i. Одно из решений состоит в том, чтобы помечать такие ячейки специальным значением deleted вместо NIL. При этом мы должны слегка изменить процедуру HASH_lNSERT, С тем чтобы она рассматривала такую ячейку как пустую и могла вставить в нее новый ключ. В процедуре Hash_Search никакие изменения не требуются, поскольку мы просто пропускаем такие ячейки при поиске и исследуем следующие ячейки в последовательности. Однако при использовании специального значения deleted время поиска перестает зависеть от коэффициента заполнения а, и по этой причине, как правило, при необходимости удалений из хеш-таблицы в качестве метода разрешения коллизий выбирается метод цепочек. 14

В нашем дальнейшем анализе мы будем исходить из предположения равномерного хеширования, т.е. мы предполагаем, что для каждого ключа в качестве последовательности исследований равновероятны все m! перестановок множества {0,1,..., т 1}. Равномерное хеширование представляет собой обобщение определенного ранее простого равномерного хеширования, заключающееся в том, что теперь хеш-функция дает не одно значение, а целую последовательность исследований. Реализация истинно равномерного хеширования достаточно трудна, однако на практике используются подходящие аппроксимации такие, например, как определенное ниже двойное хеширование. 15

Для вычисления последовательности исследований для открытой адресации обычно используются три метода: линейное исследование, квадратичное исследование и двойное хеширование. Эти методы гарантируют, что для каждого ключа к (h (к, 0), h (к, 1),..., h (к, т 1)) является перестановкой (0,1,..., т 1). Однако эти методы не удовлетворяют предположению о равномерном хешировании, так как ни один из них не в состоянии сгенерировать более т 2 различных последовательностей исследований (вместо т!, требующихся для равномерного хеширования). Наибольшее количество последовательностей исследований дает двойное хеширование и, как и следовало ожидать, дает наилучшие результаты. 16

Линейное исследование Пусть задана обычная хеш-функция h : U > {0,1,..., т 1}, которую мы будем в дальнейшем именовать вспомогательной хеш-функцией (auxiliary hash function). Метод линейного исследования для вычисления последовательности исследований использует хеш-функцию h (k, i) = (h (k) + i) mod m, где i принимает значения от 0 до m 1 включительно. Для данного ключа к первой исследуемой ячейкой является Т [h' (k)], т.е. ячейка, которую дает вспомогательная хеш-функция. Далее мы исследуем ячейку Т [h(к) + 1] и далее последовательно все до ячейки Т [m 1], после чего переходим в начало таблицы и последовательно исследуем ячейки Т [0], Т[1], и так до ячейки Т [h(к) 1]. 17

Поскольку начальная исследуемая ячейка однозначно определяет всю последовательность исследований целиком, всего имеется m различных последовательностей. Линейное исследование легко реализуется, однако с ним связана проблема первичной кластеризации, связанной с созданием длинных последовательностей занятых ячеек, что, само собой разумеется, увеличивает среднее время поиска. Кластеры возникают в связи с тем, что вероятность заполнения пустой ячейки, которой предшествуют i заполненных ячеек, равна (i + 1 )/m. Таким образом, длинные серии заполненных ячеек имеют тенденцию ко все большему удлинению, что приводит к увеличению среднего времени поиска. 18

Квадратичное исследование Квадратичное исследование использует хеш-функцию вида h (к, i) = (h(к) + c 1 i + c 2 i 2 ) mod m, где h вспомогательная хеш-функция, c 1 и c 2 0 вспомогательные константы, а n принимает значения от 0 до m 1 включительно. Начальная исследуемая ячейка Т [h' (к)]; остальные исследуемые позиции смещены относительно нее на величины, которые описываются квадратичной зависимостью от номера исследования n. Этот метод работает существенно лучше линейного исследования, но для того, чтобы исследование охватывало все ячейки, необходим выбор специальных значений c 1, c 2 и m. 19

Кроме того, если два ключа имеют одну и то же начальную позицию исследования, то одинаковы и последовательности исследования в целом, так как из h 1 (k, 0) = h 2 (k, 0) вытекает h 1 (k, i) = h 2 (k, i). Это свойство приводит к более мягкой вторичной кластеризации. Как и в случае линейного исследования, начальная ячейка определяет всю последовательность, поэтому всего используется m различных последовательностей исследования. 20

Двойное хеширование Двойное хеширование представляет собой один из наилучших способов использования открытой адресации, поскольку получаемые при этом перестановки обладают многими характеристиками случайно выбираемых перестановок. Двойное хеширование использует хеш- функцию вида h (к, i) = (h 1 (к) + ih 2 (к)) mod m, где h 1 (к) и h 2 вспомогательные хеш- функции. 21

Начальное исследование выполня­ется в позиции Т [h 1 (k)], а смещение каждой из последующих исследуемых ячеек относительно предыдущей равно h 2 (k)) по модулю m. Следовательно, в отличие от линейного и квадратичного исследования, в данном случае последовательность исследования зависит от ключа к по двум параметрам в плане выбора началь­ной исследуемой ячейки и расстояния между соседними исследуемыми ячейками, так как оба эти параметра зависят от значения ключа. 22

Пример вставки при двойном хешировании. хеш-таблица размером 13 ячеек, в которой используются вспомогательные хеш- функции h 1 (к) = к mod 13 и h 2 (к) = 1 + (к mod 11). Так как 14 = 1 (mod 13) и 14 = 3 (mod 11), ключ 14 вставляется в пустую ячейку 9, после того как при исследовании ячеек 1 и 5 выясняется, что эти ячейки заняты. Для того чтобы последовательность исследования могла охватить всю таблицу, значение h 2 (к) должно быть взаимно простым с размером хеш- таблицы m. 23

Удобный способ обеспечить выполнение этого условия состоит в выборе числа m, равного степени 2, и разработке хеш-функции h 2 таким образом, чтобы она возвращала только нечетные значения. Еще один способ состоит в использовании в качестве m простого числа и построении хеш- функции h 2 такой, чтобы она всегда возвращала натуральные числа, меньшие т. Например, можно выбрать простое число в качестве m, а хеш-функции такими: h 1 (к)= к mod m, h 2 (к)= 1 + (к mod m), где т должно быть немного меньше т (например, m 1). 24

Скажем, если к = , т=701,а т= 700, то h 1 (к)= 80 и h 2 (к) = 257, так что первой исследуемой будет ячейка в 80-й позиции, а затем будет исследоваться каждая 257-я (по модулю т) ячейка, пока не будет обнаружена пустая ячейка, или пока не окажутся исследованы все ячейки таблицы. Двойное хеширование превосходит линейное или квадратичное исследования в смысле количества θ (m 2 ) последовательностей исследований, в то время как у упомянутых методов это количество равно θ (m). Это связано с тем, что каждая возможная пара (h 1 (к) и h 2 (к) ) дает свою, отличающуюся от других последовательность исследований. В результате производительность двойного хеширования достаточно близка к производительности идеальной схемы равномерного хеширования. 25

Анализ хеширования с открытой адресацией Анализ открытой адресации, как и анализ метода цепочек, выполняется с использованием коэффициента заполнения а = n/т хеш-таблицы при n и m, стремящихся к бесконечности. Само собой разумеется, при использовании открытой адресации у нас может быть не более одного элемента на ячейку таблицы, так что n т и, следовательно, а 1. Будем считать, что используется равномерное хеширование. При такой идеализированной схеме последовательность исследований h(k, 0), h(k, 1),..., h(k, т 1), используемая для вставки или поиска каждого ключа к, с равной вероят­ностью является одной из возможных перестановок (0,1,..., т 1). C каждым конкретным ключом связана единственная фиксированная последовательность исследований, так что при рассмотрении распределения вероятностей ключей и хеш- функций все последовательности исследований оказываются равновероятными. 26

математическое ожидание количества исследований для хеширования с открытой адресацией в предположении равномерного хеширования, и начнем с анализа количества исследований в случае неуспешного поиска. Теорема. Математическое ожидание количества исследований при неуспешном поиске в хеш-таблице с открытой адресацией и коэффициентом заполне­ния а = n/т < 1 в предположении равномерного хеширования не превышает 1/(1-а). 27

Эта теорема практически непосредственно дает нам оценку производительности процедуры H ASH _I NSERT. Следствие. Вставка элемента в хеш-таблицу с открытой адресацией и коэффициентом заполнения а в предположении равномерного хеширования, требует в среднем не более 1/(1 а) исследований. 28

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

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

Идеальным хешированием мы называем методику, которая в наихудшем случае выполняет поиск за О (1) обращений к памяти. Основная идея идеального хеширования достаточно проста. Используется двухуровневую схему хеширования с универсальным хешированием на каждом уровне. Первый уровень по сути тот же, что и в случае хеширования с цепочками: n ключей хешируются в т ячеек с использованием хеш-функции h, тщательно выбранной из семейства универсальных хеш- функций. 31

Использование идеального хеширования для хранения множества К = {10,22,37,40, 60,70, 75} вместо того, чтобы создавать список ключей, хешированных в ячейку j, мы используем маленькую вторичную хеш- таблицу S j со своей хеш-функцией h j. 32 Путем точного выбора хеш-функции h j мы можем гарантировать отсутствие коллизий на втором уровне.

Внешняя хеш-функция имеет вид h (к) = ((ак + b) mod р) mod m, где а = 3, b = 42, р = 101 и т = 9. Например, h (75) = 2, так что ключ 75 хешируется в ячейку 2. Вторичная хеш-таблица Sj хранит все ключи, хешированные в ячейку j. Размер каждой таблицы S j равен m j, и с ней связана хеш-функция h j (к) = ((a j к + b j ) mod р) mod m j. Поскольку h 2 (75) = 1, ключ 75 хранится в ячейке 1 вторичной хеш-таблицы S 2. Ни в одной из вторичных таблиц нет ни одной коллизии, так что время поиска в худшем случае равно константе. 33

Для того чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер m j хеш-таблицы S j был равен квадрату числа n j ключей, хешированных в ячейку j. Такая квадратичная зависимость m j от n j может показаться чрезмерно расточительной, однако при корректном выборе хеш-функции первого уровня ожидаемое количество требуемой для хеш- таблицы памяти остается равным О (n). 34

Выбираем хеш-функцию из универсальных множеств хеш-функций. Хеш-функция первого уровня выбирается из множества H p,m, где, р является простым числом, превышающим значение любого из ключей. Ключи, хешированные в ячейку j, затем повторно хешируются во вторичную хеш- таблицу Sj размером m j с использованием хеш- функции hj, выбранной из класса Н р,m j 35

Работа будет выполнена в два этапа. Сначала мы выясним, как гарантировать отсутствие коллизий во вторичной таблице. Затем мы покажем, что ожидаемое количество памяти, необходимой для первичной и вторичной хеш-таблиц, равно О (n). Теорема. Если т ключей сохраняются в хеш- таблице размером т = n 2 с использованием хеш- функции h, случайно выбранной из универсального множества хеш-функций, то вероятность возникновения коллизий не превышает 1/2. 36

Заключение Алгоритмы хеширования изложены в книгах Кнута (Knuth) и Гоннета (Gonnet). Согласно Кнуту, хеш-таблицы и метод цепочек были изобретены Луном (Н. P. Luhn) в 1953 году. Примерно тогда же Амдал (G. М. Amdahl) предложил идею открытой адресации. Универсальные множества хеш-функций были предложены Картером (Carter) и Вегманом (Wegman) в 1979 году. Схему идеального хеширования для статических множеств, разработали Фредман (Fredman), Комлёс (Komlos) и Семереди (Szemeredi). Расширение этого метода для динамических множеств предложено Дицфельбингером (Dietzfelbinger) и др. 37