Хеширование

Размещено на http://allbest.ru

Введение

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

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

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

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

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

Роберт Моррис [5] обширный обзор по хешированию и ввел термин «рассеянная память» (scatter storage). Эта работа привела к созданию открытой адресации с двойным хешированием.

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

ХЕШИРОВАНИЕ

До сих пор мы рассматривали методы поиска, основанные на сравнении данного аргумента K с имеющимися в таблице ключами или на использовании его цифр для управления процессом разветвления. Но есть и третий путь: не рыскать вокруг да около, а произвести над K некоторое арифметическое вычисление и получить функцию f(K), указывающую адрес в таблице, где хранится K и ассоциированная с ним информация.

К сожалению, находить подобные функции f(K) довольно сложно.

Функции, дающие неповторяющиеся значения, неожиданно редки даже в случае довольно большой таблицы. Например, знаменитый парадокс дней рождения утверждает, что, если в комнате присутствует не менее 23 человек, имеется хороший шанс на то, что у двух из них совпадет день рождения! Иными словами, если мы выбираем случайную функцию, отображающую 23 ключа в 365-элементную таблицу, то с вероятностью 0.4927 (менее половины) все ключи попадут в разные места.

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

Можно получить гораздо более гибкий метод, если отбросить идею однозначности, допуская совпадения значений f(K) для различных аргументов, и использовать особый метод разрешения неопределенности после вычисления f(K).

Наши рассмотрения приводят к широко известному классу методов, обычно называемых хешированием или рассеянной памятью. Английский глагол "to hash" имеет смысл нарезать, раскрошить что-либо или сделать из этого месиво; идея хеширования состоит в том, чтобы взять некоторые характеристики ключа и использовать полученную частичную информацию в качестве основы поиска. Мы вычисляем хеш-функцию h(K) и берем это значение в качестве адреса начала поиска.

Парадокс дней рождения служит для нас предостережением, что, вероятно, найдутся различные ключи K_i K_j , для которых h(K_i)=h(K_j). Подобное событие называется коллизией; для разрешения коллизий были разработаны интересные подходы. Чтобы использовать рассеянную таблицу, программист должен принять два почти независимых решения: он должен выбрать хеш-функцию h(K) и метод разрешения коллизий. Эти два аспекта задачи поиска мы и рассмотрим по очереди.

Хеш - функции.

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

Коллизия - это ситуация, когда h(K1) = h(K2), в то время как K1 < K2. В этом случае, очевидно, необходимо найти новое место для хранения данных.

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

0 h(K)<M (1)

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

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

Рассмотрим, например, случай десятизначных ключей на десятичном компьютере.

Сам собой напрашивается следующий способ выбора хеш-функции: положить M равным, скажем, 1000, а в качестве h(K) взять три цифры, выбранные примерно из середины 20-значного произведения K*K. Казалось бы, это должно давать довольно равномерное распределение значений между 000 и 999 с низкой вероятностью коллизий. В самом деле, эксперименты с реальными данными показали, что такой метод "середины квадрата" неплох при условии, что ключи не содержат много левых или правых нулей подряд.

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

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

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

h(K)=K mod M. (2)

В этом случае, очевидно, некоторые значения M много лучше других. Например, если M - четное число, то значение h(K) будет четным при четном K и нечетным в противном случае; часто это приводит к значительным смещениям данных. Совсем плохо брать M равным степени основания системы счисления ЭВМ, так как тогда h(K) дает нам правые значащие цифры K (K mod M не зависит от других цифр). Аналогично, M не должно быть кратно 3, ибо буквенные ключи, отличающиеся друг от друга лишь порядком букв, могли бы дать значения функции, разность между которыми кратна 3. (Причина кроется в том, что 10ⁿ mod 3= 4ⁿ mod 3= 1.) Вообще мы хотели бы избежать значений M, делящих r^k a , где k и a -небольшие числа, а r-"основание системы счисления" для множества используемых литер (обычно r =64, 256 и 100), так как остаток от деления на такие значения M обычно оказываются простой суперпозицией цифр ключа.

Наши рассмотрения подсказывают, что лучше всего взять в качестве M такое простое число, чтобы r^k a ( mod M ) при небольших k и a. Практически во всех случаях, этот выбор оказывается вполне удовлетворительным. M=1009 => h(K) вычисляется следующим образом

rX < K

rA < 0 (3)

rA < K mod 1009

Мультипликативную схему хеширования также легко реализовать, но несколько труднее описать, так как нужно представить, что мы работаем с дробями, а не с целыми числами. Пусть w есть размер машинного слова; целое число A можно рассматривать как дробь A/w, если мысленно поставить десятичную (или двоичную) точку слева от машинного слова, в котором записано A. Метод состоит в том, чтобы выбрать A взаимно простым с w и положить

h(K)=[M(((A/w)K) mod 1)]. (4)

В двоичной системе M обычно берут равным степени двойки, так что h(K) состоит из старших битов правой значащей половины произведения AK. В двоичном виде при M=2^m мультипликативная хеш-функция вычисляется так:

rA <K.

rAX <AK. (5)

rAX < AK mod w.

Сдвиг rAX на m битов влево.

Результат получается в регистре A.

Одна из привлекательных черт мультипликативной схемы состоит в том, что в (5) не происходит потери информации; мы могли бы вновь найти K, зная лишь содержимое rAX после выполнения инструкций (5). Дело в том, что A взаимно просто с w, и при помощи алгоритма Евклида можно найти Константу A': AA' mod w = 1 ; отсюда следует, что K=(A'(AK mod w)) mod w. Иными словами,

K₁ ? K₂ влечет f(K₁ ) ? f(K₂ ). (6)

Конечно, f(K)принимает значения в диапазоне от 0 до w-1 и не является сколько-нибудь подходящей хеш-функцией, но она может быть очень полезной в качестве рассеивающей функции, а именно функции, удовлетворяющей (6) и обычно приводящей к рандомизации ключей.

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

a) ее вычисление должно быть очень быстрым;

b) она должна минимизировать число коллизий.

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

До сих пор мы рассматривали хеширование ключей, состоящих из одного слова. С ключами, состоящими из нескольких слов или имеющими переменную длину, можно работать как с представленными с многократной точностью числами и применить к ним рассмотренные методы. Однако обычно оказывается достаточной более быстрая процедура, когда отдельные слова сначала комбинируются в одно, а затем производится единственное умножение или деление. Для комбинирования можно использовать сложение по модулю w или операцию "исключающее или" (на двоичных ЭВМ). Достоинством обеих операций является их обратимость, т.е. их результат зависит от всех битов аргументов, причем "исключающее или" иногда предпочтительнее, так как не может привести к арифметическому переполнению. Заметим, что обе операции коммутативны, поэтому ключи (X, Y) и (Y, X) будут "брошены" по одному адресу. Чтобы избежать этого, Г.Д. Кнотт предложил предварительно делать циклический сдвиг.

Из других испытанных методов хеширования, пожалуй, наиболее интересным является способ, основанный на алгебраической теории кодирования. Идея аналогична методу деления, только вместо деления на целое число используется деление на многочлен по модулю 2. Для предлагаемого метода M должно быть степенью 2: M=2^m ; кроме того, используется многочлен m-й степени

P(x)=x^m + p_m-1 x^m-1 + … + p₀

Двоичный ключ K=(k_n-1 … k₁ k₀ )₂ можно рассматривать как многочлен K(x)=k_n-1 x^n-1+…+ k₁x+ k₀, и вычислить остаток

K(x) mod P(x) = h_m-1 x^m-1+…+ k₁ x+ k₀,

используя полиномиальную арифметику по модулю 2: h(K)=( h_m-1… h₁ h₀)₂. При правильном выборе P(x) такая хеш-функция позволяет избежать коллизий, между почти равными ключами.

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

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

- пользоваться изначальной хеш-функцией, теряя производительность из-за роста коллизий;

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

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

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

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

|Zero |Null |

|Bucket |Указатель |

|One |Null |

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

|Zero |Адрес a |

|Bucket |Null |

|One |Адрес b |

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

Когда А будет переполнен, он будет разбит таким образом, что элементы 000…и 001… будут размещены в разных блоках.

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

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

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

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

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

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

Другими словами, выполняется:

K1 < K2 ( h(K1) < h(K2)

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

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

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

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

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

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

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

|Auto |21 |Double |0 |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 |

Разрешение коллизий методом цепочек

Мы уже говорили, что некоторые адреса могут порождаться несколькими ключами. Пожалуй, наиболее очевидный способ решения проблемы состоит в том, чтобы поддерживать M связанных списков, по одному на каждый возможный хеш-адрес. Все записи должны содержать поля LINK; кроме того, нужно иметь M головных узлов списков HEAD[i], где i меняется от 1 до M. После хеширования ключа мы просто выполняем последовательный поиск в списке с номером h(K)+1.

HEAD[1]: [__] [ TO ][ ] [ FIRE ][ Л ]

HEAD[2]: [__] [ SYV ][ Л ]

HEAD[3]: [__] [ EN ][ Л ]

HEAD[4]: [__] [ TRE ][ Л ]

HEAD[5]: [__] [ FEM ][ Л ]

HEAD[6]: [_Л_]

HEAD[7]: [_Л_]

HEAD[8]: [_Л ]

HEAD[9]: [__] [ SEKS ][ Л ]

Рис. 1. Раздельные цепочки.

Рисунок иллюстрирует этот простой метод цепочек при M=9 для последовательности семи ключей

K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|

(так называются числа от 1 до 7 по-норвежски), имеющих соответственные хеш-коды

h(K)+1 = 3, 1, 4, 1, 5, 9, 2.

Первый список содержит два элемента, три списка пусты.

Метод цепочек является весьма быстрым, поскольку списки коротки. Если в одной комнате собрать 365 человек, то найдется много пар, имеющих один и тот же день рождения, но данный день рождения в среднем имеет лишь один человек! Вообще, если имеется N ключей и M списков, средний размер списка равен N/M; таким образом, хеширование уменьшает количество работы, требуемое на последовательный поиск, примерно в M раз.

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

Иногда можно совершить один проход по данным и выяснить, какие головные узлы будут использоваться, вставляя на следующем проходе "переполняющие" записи в свободные щели. Часто, однако, это нежелательно или невозможно; нам хотелось бы иметь метод, при котором каждая запись обрабатывается лишь один раз, при первом поступлении в систему. Следующий алгоритм, принадлежащий Ф.Уильямсу, является общепринятым способом решения этой задачи.

alg C. (Поиск с вставкой по рассеянной таблице с цепочками.)

Предлагаемый алгоритм позволяет отыскать в таблице из M элементов данный ключ K.

Если K нет в таблице и она не полна, K вставляется в нее.

Элементы таблицы обозначаются через TABLE[i], 0?i? M, и могут быть двух различных типов: свободный и занятый. Занятый узел содержит ключевое поле KEY[i], поле ссылки LINK[i] и, возможно, другие поля.

Алгоритм использует хеш-функцию h(K). Для облегчения поиска свободного пространства используется вспомогательная переменная R; если таблица пуста, R=M+1; по мере проведения вставок будет оставаться в силе утверждение, что узлы TABLE|[j] заняты для всех j в диапазоне R?j?M.

Условимся, что узел TABLE[0] всегда будет свободен.

C1. [Хеширование.] Установить i<h(K)+1. (Теперь 1?i?M.)

C2. [Список?] Если узел TABLE[i] свободен, то перейти на C6.

(В противном случае этот узел занят, и мы последуем на имеющийся здесь список занятых узлов).

C3. [Сравнение.] Если K=KEY[i], поиск завершен удачно.

C4. [Переход к следующему.] Если LINK[i]?0, установить i<LINK[i] и вернуться на C3.

C5. [Найти свободный узел.] (Поиск был неудачным, и мы хотим найти в таблице свободное место.) Уменьшать R до тех пор, пока не будет получено такое значение, что узел TABLE[R] свободен.

Если R=0, алгоритм заканчивается по переполнению (свободных узлов больше нет); в противном случае установить LINK[i]<R, i<R.

C6. [Вставить новый ключ.] Пометить TABLE[i] как занятый узел С KEY[i]<K и LINK[i]<0.

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

Рис. 2. Поиск с вставкой по рассеянной таблице с цепочками.

Рис. 3. Сросшиеся списки.

На первый взгляд шаг C5 может показаться неэффективным, так как в нем поиск свободной позиции производится последовательно. Но в действительности в процессе заполнения таблицы суммарное число проб в шаге C5 не превышает количества элементов в таблице; значит, в среднем на каждую вставку тратится не более одной такой пробы!

Разрешение коллизий "открытой адресацией"

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

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

h(K), h(K)-1,…, 0, M-1, M-2,…, h(K)+1 (*)

alg L. (Поиск с вставкой по открытой рассеянной таблице.)

Алгоритм позволяет разыскать данный ключ K в таблице из M узлов. Если K нет в таблице и она не полна, ключ K вставляется.

Узлы таблицы обозначаются через TABLE[i], 0?i<M, и принадлежат двум различным типам узлов - свободных и занятых. Занятый узел содержит ключ KEY[i] и, возможно, другие поля. Значение вспомогательной переменной N равно числу занятых узлов; эта переменная рассматривается как часть таблицы, и при вставке нового ключа ее значение увеличивается на 1.

Данный алгоритм использует хеш-функцию h(K) и линейную последовательность проб (*) для адресации. Модификации этой последовательности обсуждаются ниже.

L1. [Хеширование.] Установить i<h(K). (Теперь 0?i< M.)

L2. [Сравнить.] Если узел TABLE[i] свободен, то перейти на L4. В противном случае, если KEY[i]=K, алгоритм заканчивается удачно.

L3. [Перейти к следующему.] Установить i<(i-1); если теперь i<0,

Установить i<i+M. Вернуться на L2.

L4. [Вставить.] (Поиск был неудачным.) Если N=M-1, алгоритм заканчивается по переполнению. В противном случае установить N<N+1, отметить, что узел TABLE[i] занят и установить KEY[i]<K.

На рис. 4. (см. ниже) показано, что происходит при вставке с помощью алгоритма ~ L семи "норвежских" ключей , имеющих коды хеширования 2, 7, 1, 8, 2, 8, 1 соответственно. Последние три ключа - FEM, SEKS и SYV-смещены по сравнению со своими начальными адресами h(K).

0 [ FEM ]

1 [ TRE ]

2 [ EN ]

3 [ ]

4 [ ]

5 [ SYV ]

6 [_SEKS ]

7 [_ TO ]

8 [ FIRE ]

Рис. 4. Линейная открытая адресация.

Эксперименты с линейным опробованием показывают, что этот метод работает прекрасно, пока таблица не слишком заполнена, но в конце концов процесс замедляется, длинные серии проб становятся все более частыми. Причину такого поведения можно понять, рассмотрев следующую гипотетическую рассеянную таблицу (M=19, N= 9):

Заштрихованные квадраты обозначают занятые позиции. Ключ K, который должен быть вставлен в таблицу следующим, попадет в одну из десяти свободных позиций, но не с равными вероятностями. В самом деле, K будет вставлен в позицию 11, если 11?h(K)?15, а в позицию 8 он попадет лишь при h(K)=8. Следовательно, вероятность попасть в позицию 11 в пять раз больше, чем в позицию 8; длинные списки стремятся стать еще длиннее.

alg D.(Открытая адресация с двойным хешированием.)

Этот алгоритм почти совпадает с алгоритмом L, но использует несколько иную последовательность проб, вычисляя две хеш-функции h₁(K) и h₂(K). Как обычно, h₁(K) порождает величины от 0 до M-1 включительно; но значения h₂(K) должны лежать от 1 до M-1 и быть взаимно просты с M. (Например, если M - простое число, то h₂(K) может быть любой величиной от 1 до M-1 включительно, или, если M=2^m, то h₂(K) может быть любым нечетным числом между 1 и 2^m-1.)

D1. [Первое хеширование.] Установить i <h₂(K).

D2. [Первая проба.] Если узел TABLE[i] свободен, то перейти на D6. В противном случае, если KEY[i]=K, алгоритм заканчивается удачно.

D3. [Второе хеширование.] Установить c<h₂(K).

D4. [Перейти к следующему.] Установить i<i-c; если теперь i<0, Установить i<i+M.

D5. [Сравнение.] Если узел TABLE[i] свободен, то перейти на D6. В противном случае, если KEY[i]=K, алгоритм заканчивается удачно; в противном случае вернуться на D4.

D6. [Вставка.] Если N=M-1, алгоритм заканчивается по переполнению. В противном случае установить N<N+1, пометить узел TABLE[i] как занятый и установить KEY[i]< K.

Для вычисления h₂(K) было предложено несколько способов.

Если M - простое число и h₁(K)=K mod M, можно положить

h₂(K)=1+(K mod (M-1));

но так как M-1 четно, было бы лучше положить

h₂(K)=1+(K mod (M-2))

Это наводит на мысль о таком выборе M, чтобы M и M-2были простыми числами-близнецами, например 1021 и 1019. Можно взять h₂(K)=1+([K/M] mod (M-2)), ибо частное [K/M] можно получить в регистре как побочный продукт вычисления h₁(K).

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

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

h = h + a2 [15],

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

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

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

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

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

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

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

1. Пометить TABLE[i] как пустую ячейку, и установить j = i;

2. i = i - 1 или i = i + M, если i стало отрицательным;

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

4. Надо переместить запись TABLE[j] = TABLE[i] и вернуться на первый шаг.

Применение хеширования

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

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

Наибольшую известность имеют следующие хеш-функции: MD4, MD5, RIPEMD-128 (128 бит), RIPEMD-160, SHA (160 бит). В российском стандарте цифровой подписи используется разработанная отечественными криптографами хеш-функция (256 бит) стандарта ГОСТ Р 34.11--94.

Хеширование паролей

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

Разумеется, это не более, чем конкретный пример. Хеширование паролей -метод, позволяющей пользователям запоминать не 128 байт, то есть 256шестнадцатиричных цифр ключа, а некоторое осмысленное выражение, слово или последовательность символов, называющуюся паролем. Действительно, при разработке любого криптоалгоритма следует учитывать, что в половине случаев конечным пользователем системы является человек, а не автоматическая система. Это ставит вопрос о том, удобно, и вообще реально ли человеку запомнить 128-битный ключ (32 шестнадцатеричные цифры). На самом деле предел запоминаемости лежит на границе 8-12 подобных символов, а, следовательно, если мы будем заставлять пользователя оперировать именно ключом, тем самым мы практически вынудим его к записи ключа на каком-либо листке бумаги или электронном носителе, например, в текстовом файле. Это, естественно, резко снижает защищенность системы.

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

1. хеш-функция имеет бесконечную область определения,

2. хеш-функция имеет конечную область значений,

3. она необратима,

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

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

Сравнение методов

Итак, мы знаем много методов поиска, чем же нам руководствоваться при выборе наилучшего из них для конкретного приложения? Трудно в нескольких словах описать все, что нам хотелось бы учесть при выборе метода поиска, однако следующие соображения, пожалуй, наиболее важны, если мы заинтересованы в сокращении времени поиска и объема занимаемой памяти.

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

Методы цепочек весьма экономны с точки зрения числа проб, но потребность в дополнительном пространстве памяти для полей ссылок иногда (при небольшом размере записей) делает более привлекательной открытую адресацию. Например, если нужно сделать выбор между таблицей с цепочками на 500 элементов и таблицей с открытой адресацией на 1000 элементов, то последняя, очевидно, предпочтительнее, ибо она обеспечивает эффективный поиск среди 500 записей и способна вместить в два раза больше данных. С другой стороны, порой в силу размера записей или их формата пространство под поля ссылок достается фактически бесплатно.

Как соотносятся методы хеширования с другими стратегиями поиска? Сравнивая их по скорости, можно утверждать, что методы хеширования лучше, если число записей велико, поскольку среднее время поиска для методов хеширования остается ограниченным при N > ? в

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

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

a) После неудачного поиска в рассеянной таблице мы знаем лишь то, что нужного ключа там нет. Методы поиска, основанные на сравнениях, всегда дают больше информации; они позволяют найти наибольший ключ ? K или наименьший ключ ? K , что важно во многих приложениях (например, для интерполяции значений функции по хранящейся таблице).

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

b) Часто довольно трудно распределить память для рассеянных таблиц; под хеш-таблицу нужно отвести определенную область памяти, а размер ее не всегда ясен. Если отвести слишком много памяти, то такая расточительность отразится на других списках или на других пользователях ЭВМ, но если отвести мало места, таблица переполнится! При переполнении рассеянной таблицы, вероятно, лучше всего "рехешировать" ее, т.е. отвести больше пространства и изменить хеш-функцию, а затем вставить записи в большую таблицу. Ф.~Хопгуд предложил рехешировать таблицу, если коэффициент заполнения достигнет б₀ , заменяя M на d₀M.

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

c) Наконец, при использовании методов хеширования нужно свято верить в теорию вероятностей, ибо они эффективны лишь в среднем, а наихудший случай просто ужасен! Как и в ситуации с датчиками случайных чисел, мы не можем быть полностью уверенными в том, что при применении к новому множеству данных хеш-функция будет работать удовлетворительно.

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

Функции BCrypt

Подобно генерации случайных чисел, функции хеширования играют важнейшую роль в обеспечении мер и функций безопасности во множестве задач современной вычислительной техники. Функции хеширования предоставляются в виде объектов в CNG, но, поскольку интерфейс API должен быть доступен из кода режима ядра (написанного в основном на C), это требует некоторой предварительной работы по обратной сборке объекта в единое целое. Как было упомянуто во введении, в CNG поставщики алгоритмов и функции хеширования представляются объектами. Поскольку они являются частью BCrypt, функции BCryptGetProperty и BCryptSetProperty можно использовать для запроса и установки именованных свойств конкретного объекта. Соответствующие функции предоставляются для управления свойствами объектов посредством NCrypt.

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

Размер буфера, необходимый для создания объекта хеша, является свойством поставщика алгоритма, и идентификатор BCRYPT_OBJECT_LENGTH предоставляет имя этого свойства для создания запроса. На рис. 4 показано, как можно было бы загрузить поставщик алгоритма для алгоритма хеширования SHA-256 и запросить размер буфера хеша.

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

Определив размер буфера хеша, необходимо выделить участок памяти для объекта хеша. За исключением случая режима ядра, не имеет большого значения, где размещается этот буфер, и разработчик по своему усмотрению может использовать любое удобное хранилище, если оно находится в стабильном состоянии (другими словами, не допускается использование незафиксированного управляемого массива байтов). На рис. 5 предоставляется простой класс Buffer, который можно использовать для простых выделений буфера пользовательского режима. Этот класс будет снова использоваться при создании объектов ключей шифрования, поэтому рекомендуется иметь наготове какой-нибудь класс Buffer.

Выполнив все предварительные условия, теперь можно, наконец, с помощью функции BCryptCreateHash создать объект хеша, как показано в следующем примере:

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

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

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

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

После того, как функции хеширования переданы все данные, результирующее значение можно получить, вызвав функцию BCryptFinishHash. Размер результирующего значения хеша зависит от конкретного используемого алгоритма хеширования. Если этот размер неизвестен, можно запросить объект хеша с идентификатором BCRYPT_HASH_LENGTH. В следующем примере запрашивается размер значения хеша, создается для него буфер, и, наконец, значение хеша копируется в буфер с помощью BCryptFinishHash:

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

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

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

...