58

12.Хеширование

Вид занятия – лабораторная работа Цель – исследование методов хеширования

Продолжительность – 4 часа

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

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

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

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

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

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

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

Рисунок 12.1. - Пример поиска данных в реляционной таблице с помощью хеширования

59

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

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

Идеальная функция хеширования должна обладать следующими свойствами:

1.Быть применимой к аргументу любого размера.

2.Выходное хеш-значение должно иметь фиксированный размер.

3.Скорость вычисления должна быть такой, чтобы опережать время затрачиваемое на обработку исходного значения.

4.Хеш-функция должна быть чувствительной к всевозможным изменениям во входных данных.

5.Хеш-функция должна быть однонаправленной, то есть обладать свойствами необратимости.

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

Отечественный стандарт хеширования

Отечественным стандартом генерирования хэш-функции является алгоритм ГОСТ Р 34.11-94. Этот стандарт является обязательным для применения в качестве алгоритма хеширования в государственных организациях РФ и ряде коммерческих организаций. Коротко данный алгоритм хеширования можно описать следующим образом [9].

Шаг 1. Инициализация регистра хеш-значения. Если длина сообщения не превышает 256 бит - переход к шагу 3, если превышает — переход к шагу 2.

Шаг 2. Итеративное вычисление хеш-значения блоков хешируемых данных по 256 бит с использованием хранящегося в регистре хеш-значения предыдущего блока. Вычисление включает в себя следующие действия:

-генерацию ключей шифрования на основе блока хешируемых данных;

-шифрование хранящегося в регистре хеш-значения в виде четырех блоков

-по 64 бит по алгоритму ГОСТ 28147-89 в режиме простой замены;

-перемешивание результата.

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

Шаг З. Дополнение битовыми нулями необработанной части сообщения до 256 бит. Вычисление хеш-значения аналогично шагу 2. В результате в регистре оказывается искомое хэш-значение.

Создание хеш-функции

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

Наиболее распространённый метод хеширования выбор в качестве размера M хеш-таблицы простого числа и вычисление остатка от деления исходного значения k на M.

h(k) = k mod т (12.1).

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

Хеш-функции для строковых значений, алгоритм Гонера

Как получить хеш-значение для данных больших размерностей? Допустим, что у нас есть исходное слово: “averylongkey”. Если это слово описать в виде 7-ми разрядного ASCII кода, то мы получим примерно следующую картину [2]:

60

97*12811+118*12810+101*1289+114*1288+

121*1287+108*1286+111*1285+110*1284+

103*1283+107*1282+101*1281+121*1280,

что примерно равно 7.5571538*1023.

Как вы понимаете, это абсолютно неприемлемо, но представьте себе какое значение вы получите если вам придётся обрабатывать ещё более значительные строковые типы данных.

Поэтому для обработки строковых значений часто применяется алгоритм Горнера.

(((((((((((97*128+118)*128+101)*128+114)*128+121)*128+108)*128+111)*128+110)*

128+103)*128+107)*128+101)*128+121)*128

Другими словами можно вычислить десятичное число, соответствующее коду соответствующее коду символов строки при просмотре ее слева направо, умножая полученное значение на 128, а затем добавляя кодовое значение следующего символа.

Со временем этот алгоритм создаёт число, которое вообще будет нельзя представить на компьютере. Однако полученное число нас мало интересует, поскольку при хешировании нам требуется остаток от деления исходного числа на M. Результат можно получить даже не сохраняя большое накопленное значение, т.к. в любое время можно отбросить число кратное M – при каждом выполнении сложения и умножения нужно хранить только остаток деления по модулю M.

Задание

Создайте текстовый файл input.txt содержащий 50-60 строк случайных латинских символов (от 1 до 20-ти символов в строке). Указанный файл будет служить источником данных для вашей дальнейшей работы.

1.Разработайте хеш-функцию и структуру хеш-таблицы.

2.Реализуйте операции вставки хеш-значений в хеш-таблицу.

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

4.Внесите предложения по борьбе с коллизиями.