Методы поиска. Хеширование

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

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ - АНОО ВО

Специальность 09.02.07 Информационные системы и программирование

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

по дисциплине «Разработка ПО»

на тему «Методы поиска. Хеширование»

ВОРОНЕЖ _2022_

Содержание

Введение

Глава 1. Общая информация о хешировании

Глава 2. Методы хеширования

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

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

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

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

2.5 Расширяемое хеширование

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

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

2.8 Разрешение коллизий

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

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

Глава 3. Алгоритм построения и поиска хэш-таблицы

Заключение

Литература



Введение

В век компьютеризации и обилия информации мы часто сталкиваемся с проблемой поиска необходимой информации. Для быстрого поиска в структурах данных, для проверки и исправления ошибок, а так же для поиска информации в криптографии обычно применяется хеширование. Впервые о хешировании узнали в 1967 г. Этот термин произошёл от английского глагола «hash», что в переводе означает «рубить, крошить». Однако сам процесс хеширования в программировании был известен давно.

Хеширование - это процесс получения идентификатора для объекта, который является уникальным. Как правило, это цифровой код. С использованием хеширования люди имеют дело практически каждый день. Например при использовании Web-ссылок во время работы с браузером или текстовым редактором. Так же во время работы с таблицами символов, языками скриптов (Perl, Python, PHP и др.), и переводчиком (словарь).

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

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



1. Общая информация о хешировании

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

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

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

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

Рассмотрим следующие методы хеширования:

Хеш-функция

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

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

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

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

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

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

Разрешение коллизий

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

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

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



2. Методы хеширования

2.1 Хеш-функция

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

Хэш-функция должна удовлетворяет следующим условиям:

функция должна быть очень простой с вычислительной точки зрения

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

При этом преобразовании хеш-функция использует определенный ключ, обозначим его R. Возможно образование коллизий. Коллизия - это ситуация, когда H(R1) = H(R2), в то время как ключи R1 ? R2. Хорошая хеш-функция должна удовлетворять 2-м требованиям: функция должна число коллизий свести к минимуму и ее вычисление должно выполняться очень быстро. Обычно можно использовать свойства данных для создания хеш-функций с минимальным количеством коллизий .

Хеш-функции применяются при:

построении ассоциативных массивов;

поиске двойников в последовательностях наборов данных;

построении уникальных идентификаторов для наборов данных;

сохранении паролей в системах защиты в виде хеш-кода;

создании электронной подписи.

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

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

В методе умножения или в мультипликативном хешировании используется некая формула: H(R) = [L * ((C * R) mod 1)]. В этой формуле происходит умножение некой константы С на ключ R. При этом константа С находится в промежутке [0..1]. После этого берется дробная часть этого выражения и умножается на некоторую константу L. Константа L выбирается так, что бы результат не вышел за границы хеш-таблицы. Оператор [ ] возвращает наибольшее целое, которое меньше аргумента. Если константа С выбрана верно, то можно добиться отличных результатов. Мультипликативный метод хорошо использует то, что реальные файлы неслучайны.

Метод умножения уменьшает число коллизий по сравнению со случайной ситуацией. Частным случаем выбора константы является значение золотого сечения ц = (?5 - 1)/2 ? 0,6180339887.

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

Метод деления - самый распространенный метод на практике. Он заключается в том, что используется остаток от деления на L: H(R) = R mod L. К выбору этой константы надо подойти обдуманно. Если константа L четная, то значение функции будет четным при четном R и нечетным - при нечетном, что приведет к нежелательному результату.

Если L - это степень счисления компьютера, то результат будет зависеть только от нескольких цифр ключа справа. Т

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

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

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

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

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

Узлы дерева могут показывают на другие узлы или на другие блоки.

2.5 Расширяемое хеширование

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

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

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

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

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

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

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

поиск ключ хеширование

Рассмотрим класс хеш-функций, которые сохраняют порядок ключей. То есть выполняется R1 < R2 H(R1) < H(R2). Эти функции отлично подходят для сортировки, которая не потребует никакой другой работы. Т.е. можно избежать большого количества сравнений. Нам достаточно будет линейно просканировать хеш-таблицу для того, что бы произвести сортировку элементов по возрастанию. Эту функцию несложно создать, если пространство ключей меньше, чем хеш-таблица. Однако стоит заметить, что подобное ограничение на хеш-функцию может оказать плохое влияние на ее производительность. Поэтому часто прибегают к индексированию вместо поиска подобной хеш-функции.

2.8 Разрешение коллизий

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

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

метод открытой адресации (закрытое хеширование);

метод цепочек (внешнее или открытое хеширование).

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

Анализ метода открытой адресации:

Плюсы:

Использует мало памяти: для хранения n значений резервируется только n ячеек в памяти

Удобно использовать при малом количестве коллизий на одно хешзначение( не более 3-х)

Минусы:

Поиск определённого значения в хеш-таблице неоптимально

Время работы O(n^2)

Нет чёткой структуры, хеш-значения могут храниться не в отсортированном виде

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

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

Анализ метода цепочек:

Плюсы:

Метод цепочек эффективен и имеет чёткую структуру.

Его удобно использовать, когда неизвестно количество коллизий на одно хеш-значение.

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

Минусы:

Он использует много памяти: для хранения n хеш-значений выделяется ~nІ ячеек памяти.

Время работы метода O(nІ).

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

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

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

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

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

Этот алгоритм выбора цепочки почти такой же как алгоритм для линейной адресации. Однако, алгоритм адресации с двойным хешированием проверяет таблицу по-другому, используя две хеш-функции Н1(R) и Н2(R). Последняя должна порождать значения в интервале от 1 до L - 1, взаимно простые с L.

1. Установить i = H1(R)

2. Если TABLE[i] пуст, то перейти к шагу 6, иначе, если по этому адресу

искомый, алгоритм завершается.

3. Установить c = H2(R)

4. Установить i = i - c, если i < 0, то i = i +L.

5. Если TABLE[i] пуст, то переход на шаг 6. Если искомое расположено по

этому адресу, то алгоритм завершается, иначе возвращается на шаг 4.

6. Вставка. Если N = L - 1, то алгоритм завершается по переполнению.

Иначе увеличить N, пометить ячейку TABLE[i] как занятую и установить в нее значение ключа R.

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

Есть различные варианты выбора дополнительной функции.

Если L - простое число и H1(R) = R mod L, можно положить H2(R) = 1 + (L mod (L - 1)); однако, если L - 1 четном (другими словами, L нечетно, что всегда выполняется для простых чисел), было бы лучше положить H2(R) = 1 + (R mod (L - 2)). Здесь обе функции достаточно независимы.

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

H2(R) = 1, если H1(R)= 0 и H2(R) =L-H1(R) в противном случае (т.е. H1(R) > 0).

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



Глава 3. Алгоритм построения и поиска хэш-таблицы

Построение:

Сначала найдем значение хэш-функции. Потом по этому значению войдем в таблицу

Если таблица пустая, то запишем в нее ключ

Если таблица занятая, то сравним ключ с заданным ключом:

1. если ключи совпадают, то обрабатываем повторный ключ

2. если ключи не совпадают, то добавляем новый ключ в конец списка

Поиск:

Сначала найдем значение хэш-функции для искомого ключа и поэтому значению входим в таблицу

Если ячейка пустая, то поиск оказался неудачным

Если она не пустая, то выполним сравнение ключей:

1. Если ключи совпадают, то поиск заканчивается за одно сравнение

2. Иначе организуем просмотр вспомогательного списка с положительным или отрицательным результатом.



Заключение

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



Литература

1. https://rsdn.org/article/alg/bintree/hash.xml

2. https://www.bibliofond.ru/view.aspx?id=34619

3. https://topref.ru/referat/55742.html

4. http://genius.pstu.ru/file.php/1/pupils_works_2017/MuhinaAlisa.pdf

Размещено на Allbest.ru

...