Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.
О себе
Студент кафедры информационной безопасности.О хэшировании
В настоящее время практически ни одно приложение криптографии не обходится без использования хэширования.Хэш-функции – это функции, предназначенные для «сжатия» произвольного сообщения или набора данных, записанных, как правило, в двоичном алфавите, в некоторую битовую комбинацию фиксированной длины, называемую сверткой. Хэш-функции имеют разнообразные применения при проведении статистических экспериментов, при тестировании логических устройств, при построении алгоритмов быстрого поиска и проверки целостности записей в базах данных. Основным требованием к хэш-функциям является равномерность распределения их значений при случайном выборе значений аргумента.
Криптографической хеш-функцией называется всякая хеш-функция, являющаяся криптостойкой, то есть удовлетворяющая ряду требований специфичных для криптографических приложений. В криптографии хэш-функции применяются для решения следующих задач:
- построения систем контроля целостности данных при их передаче или хранении,
- аутентификация источника данных.
Хэш-функцией называется всякая функция h:X -> Y , легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X - множество всех сообщений, Y - множество двоичных векторов фиксированной длины.
Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x 1 , x 2)
двух переменных, где x 1
, x 2
и y
- двоичные векторы длины m
, n
и n
соответственно, причем n
- длина свертки, а m
- длина блока сообщения.
Для получения значения h(M)
сообщение сначала разбивается на блоки длины m
(при этом, если длина сообщения не кратна m
то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M 1 , M 2 ,.., M N
применяют следующую последовательную процедуру вычисления свертки:
H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = H N
Здесь v
- некоторая константа, часто ее называют инициализирующим вектором. Она выбирается
из различных соображений и может представлять собой секретную константу или набор случайных данных (выборку даты и времени, например).
При таком подходе свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции.
Выделяют два важных вида криптографических хэш-функций - ключевые и бесключевые. Ключевые хэш-функции называют кодами аутентификации сообщений. Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с доверяющими друг другу пользователями.
Бесключевые хэш-функции называются кодами обнаружения ошибок. Они дают возможность с помощью дополнительных средств (шифрования, например) гарантировать целостность данных. Эти хэш-функции могут применяться в системах как с доверяющими, так и не доверяющими друг другу пользователями.
О статистических свойствах и требованиях
Как я уже говорил основным требованием к хэш-функциям является равномерность распределения их значений при случайном выборе значений аргумента. Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось. Это называется лавинным эффектом.
К ключевым функциям хэширования предъявляются следующие требования:
- невозможность фабрикации,
- невозможность модификации.
Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе - высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.
К бесключевым функциям предъявляют требования:
- однонаправленность,
- устойчивость к коллизиям,
- устойчивость к нахождению второго прообраза.
Под однонаправленностью понимают высокую сложность нахождения сообщения по заданному значению свертки. Следует заметить что на данный момент нет используемых хэш-функций с доказанной однонаправленностью.
Под устойчивостью к коллизиям понимают сложность нахождения пары сообщений с одинаковыми значениями свертки. Обычно именно нахождение способа построения коллизий криптоаналитиками служит первым сигналом устаревания алгоритма и необходимости его скорой замены.
Под устойчивостью к нахождению второго прообраза понимают сложность нахождения второго сообщения с тем же значением свертки для заданного сообщения с известным значением свертки.
Это была теоретическая часть, которая пригодится нам в дальнейшем…
О популярных хэш-алгоритмах
Алгоритмы CRC16/32 - контрольная сумма (не криптографическое преобразование).
Алгоритмы MD2/4/5/6
. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 - очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.
Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 - собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.
Российский стандарт - ГОСТ 34.11-94 .
В следующей статье
Обзор алгоритмов MD (MD4, MD5, MD6).
Литература
А. П. Алферов, Основы криптографии.
Брюс Шнайер, Прикладная криптография.
Алгоритмы хэширования строк помогают решить очень много задач. Но у них есть большой недостаток: что чаще всего они не 100%-ны, поскольку есть множество строк, хэши которых совпадают. Другое дело, что в большинстве задач на это можно не обращать внимания, поскольку вероятность совпадения хэшей всё-таки очень мала.
Определение хэша и его вычисление
Один из лучших способов определить хэш-функцию от строки S следующий:
H(S) = S + S * P + S * P^2 + S * P^3 + ... + S[N] * P^N
где P - некоторое число.
Разумно выбирать для P простое число, примерно равное количеству символов во входном алфавите. Например, если строки предполаются состоящими только из маленьких латинских букв, то хорошим выбором будет P = 31. Если буквы могут быть и заглавными, и маленькими, то, например, можно P = 53.
Во всех кусках кода в этой статье будет использоваться P = 31.
Само значение хэша желательно хранить в самом большом числовом типе - int64, он же long long. Очевидно, что при длине строки порядка 20 символов уже будет происходить переполнение значение. Ключевой момент - что мы не обращаем внимание на эти переполнения, как бы беря хэш по модулю 2^64.
Пример вычисления хэша, если допустимы только маленькие латинские буквы:
Const int p = 31;
long long hash = 0, p_pow = 1;
for (size_t i=0; i В большинстве задач имеет смысл сначала вычислить все нужные степени P в каком-либо массиве. Уже теперь мы в состоянии эффективно решить такую задачу. Дан список строк S, каждая длиной не более M символов. Допустим, требуется найти все повторяющиеся строки и разделить их на группы, чтобы в каждой группе были только одинаковые строки. Обычной сортировкой строк мы бы получили алгоритм со сложностью O (N M log N), в то время как используя хэши, мы получим O (N M + N log N). Алгоритм. Посчитаем хэш от каждой строки, и отсортируем строки по этому хэшу. Vector Предположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S. По определению имеем: H = S[I] + S * P + S * P^2 + ... + S[J] * P^(J-I)
H * P[I] = S[I] * P[I] + ... + S[J] * P[J],
H * P[I] = H - H
Полученное свойство является очень важным. Действительно, получается, что, зная только хэши от всех префиксов строки S, мы можем за O (1) получить хэш любой подстроки
. Единственная возникающая проблема - это то, что нужно уметь делить на P[I]. На самом деле, это не так просто. Поскольку мы вычисляем хэш по модулю 2^64, то для деления на P[I] мы должны найти к нему обратный элемент в поле (например, с помощью Расширенного алгоритма Евклида), и выполнить умножение на этот обратный элемент. Впрочем, есть и более простой путь. В большинстве случаев, вместо того чтобы делить хэши на степени P, можно, наоборот, умножать их на эти степени
. Допустим, даны два хэша: один умноженный на P[I], а другой - на P[J]. Если I < J, то умножим перый хэш на P, иначе же умножим второй хэш на P. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать. Например, код, который вычисляет хэши всех префиксов, а затем за O (1) сравнивает две подстроки: String s; int i1, i2, len; // входные данные
// считаем все степени p
const int p = 31;
vector Вот некоторые типичные применения хэширования: Пусть дана строка S длиной N, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке. Для решения переберём по очереди длину подстроки: L = 1 .. N. Для каждого L мы построим массив хэшей подстрок длины L, причём приведём хэши к одной степени, и отсортируем этот массив. Количество различных элементов в этом массиве прибавляем к ответу. Реализация: String s; // входная строка
int n = (int) s.length();
// считаем все степени p
const int p = 31;
vector Например, мы можем подать на вход 128-битной хеш-функции роман Льва Толстого в шестнадцатеричном виде или число 1. В результате на выходе мы в обоих случаях получим разные наборы псевдослучайных шестнадцатеричных цифр вида: «c4ca4238a0b923820dcc509a6f75849b». При изменении исходного текста даже на один знак результат хеш-функции полностью меняется. Это свойство хеш-функций позволяет применять их в следующих случаях: «Хорошая» хеш-функция должна удовлетворять двум свойствам
: Введём обозначения: В качестве примера «плохой» хеш-функции можно привести функцию с
M
=
1000
{\displaystyle M=1000}
, которая десятизначному натуральному числу
K
{\displaystyle K}
сопоставляет три
цифры, выбранные из середины двадцатизначного квадрата числа
K
{\displaystyle K}
. Казалось бы, значения «хеш-кодов» должны равномерно
распределяться между «000
» и «999
», но для «реальных
» данных это справедливо лишь в том случае, если «ключи
» не имеют «большого» количества нулей слева или справа . Рассмотрим несколько простых и надёжных реализаций «хеш-функций». Хеш-функция может вычислять «хеш» как остаток от деления входных данных на
M
{\displaystyle M}
: где
M
{\displaystyle M}
- количество всех возможных «хешей» (выходных данных). При этом очевидно, что при чётном
M
{\displaystyle M}
значение функции будет чётным при чётном
k
{\displaystyle k}
и нечётным - при нечётном
k
{\displaystyle k}
. Также не следует использовать в качестве
M
{\displaystyle M}
степень основания системы счисления компьютера , так как «хеш-код» будет зависеть только от нескольких
цифр числа
k
{\displaystyle k}
, расположенных справа, что приведёт к большому количеству коллизий . На практике обычно выбирают простое
M
{\displaystyle M}
; в большинстве случаев этот выбор вполне удовлетворителен. Хеш-функция может выполнять деление входных данных на полином по модулю два. В данном методе
M
{\displaystyle M}
должна являться степенью двойки, а бинарные ключи (
K
=
k
n
−
1
k
n
−
2
.
.
.
k
0
{\displaystyle K=k_{n-1}k_{n-2}...k_{0}}
) представляются в виде полиномов
, в качестве «хеш-кода» «берутся» значения коэффициентов полинома
, полученного как остаток от деления входных данных
K
{\displaystyle K}
на заранее выбранный полином
P
{\displaystyle P}
степени
m
{\displaystyle m}
: При правильном выборе
P
(x)
{\displaystyle P(x)}
гарантируется отсутствие коллизий между почти одинаковыми ключами . Обозначим символом
w
{\displaystyle w}
количество чисел, представимых машинным словом . Например, для 32-разрядных компьютеров, совместимых с IBM PC ,
w
=
2
32
{\displaystyle w=2^{32}}
. Выберем некую константу
A
{\displaystyle A}
так, чтобы
A
{\displaystyle A}
была взаимно простой с
w
{\displaystyle w}
. Тогда хеш-функция, использующая умножение, может иметь следующий вид: В этом случае на компьютере с двоичной системой счисления
M
{\displaystyle M}
является степенью двойки, и
h
(K)
{\displaystyle h(K)}
будет состоять из старших битов правой половины произведения
A
∗
K
{\displaystyle A*K}
. Среди преимуществ хеш-функций, основанных на делении и умножении, стоит отметить выгодное использование неслучайности реальных ключей. Например, если ключи представляют собой арифметическую прогрессию (например, последовательность имён «Имя 1», «Имя 2», «Имя 3»), хеш-функция, использующая умножение, отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшит количество коллизий по сравнению со случайной ситуацией . Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи . Хеширование Фибоначчи основано на свойствах золотого сечения . В качестве константы
A
{\displaystyle A}
здесь выбирается целое число, ближайшее к
φ
−
1
∗
w
{\displaystyle \varphi ^{-1}*w}
и взаимно простое с
w
{\displaystyle w}
, где
φ
{\displaystyle \varphi }
- это золотое сечение . Вышеизложенные методы применимы и в том случае, если необходимо рассматривать ключи, состоящие из нескольких слов, или ключи переменной длины. Например, можно скомбинировать слова в одно при помощи сложения по модулю
w
{\displaystyle w}
или операции «исключающее или ». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона. Коллизией (иногда конфликтом или столкновением) называется случай, при котором одна хеш-функция для разных входных блоков возвращает одинаковые хеш-коды. Большинство первых работ, описывающих хеширование, посвящено методам борьбы с коллизиями в хеш-таблицах. Тогда хеш-функции применялись при поиске текста в файлах большого размера. Существует два основных метода борьбы с коллизиями в хеш-таблицах: При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе создаётся новая пара «список ключей» - «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется
N
{\displaystyle N}
ключей и
M
{\displaystyle M}
списков, средний размер хеш-таблицы составит
N
M
{\displaystyle {\frac {N}{M}}}
. В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в
M
{\displaystyle M}
раз. При использовании метода открытой адресации в хеш-таблице хранятся пары «ключ» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; пара «ключ» - «хеш-код» сохраняется в таблице. В этом случае при поиске по таблице по сравнению со случаем, в котором используются связные списки, ссылки не используются, выполняется последовательный перебор пар «ключ» - «хеш-код», перебор прекращается после обнаружения нужного ключа. Последовательность, в которой просматриваются ячейки таблицы, называется последовательностью проб . Хеш-функции широко используются в криптографии. Хеш используется как ключ во многих структурах данных - хеш-таблицаx , фильтрах Блума и декартовых деревьях . Среди множества существующих хеш-функций принято выделять криптографически стойкие , применяемые в криптографии , так как на них накладываются дополнительные требования. Для того, чтобы хеш-функция
H
{\displaystyle H}
считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии: Данные требования не являются независимыми. Процесс поиска данных в больших объемах информации сопряжен с временными затратами, которые обусловлены необходимостью просмотра и сравнения с ключом поиска значительного числа элементов. Сокращение поиска возможно осуществить путем локализации
области просмотра. Например, отсортировать данные по ключу поиска, разбить на непересекающиеся блоки по некоторому групповому признаку или поставить в соответствие реальным данным некий код, который упростит процедуру поиска. В настоящее время используется широко распространенный метод обеспечения быстрого доступа к информации, хранящейся во внешней памяти – хеширование
. Хеширование
(или хэширование
, англ. hashing
) – это преобразование входного массива данных определенного типа и произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями
или функциями свертки
, а их результаты называют хешем, хеш-кодом, хеш-таблицей
или дайджестом
сообщения (англ. message digest
). Хеш-таблица
– это структура данных
, реализующая интерфейс
ассоциативного массива, то есть она позволяет хранить пары вида " ключ
- значение
" и выполнять три операции
: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Хеш-таблица является массивом, формируемым в определенном порядке хеш-функцией
. При этом первое свойство хорошей хеш-функции
зависит от характеристик компьютера, а второе – от значений данных. Если бы все данные были случайными, то хеш-функции
были бы очень простые (например, несколько битов ключа). Однако на практике случайные данные встречаются достаточно редко, и приходится создавать функцию, которая зависела бы от всего ключа. Если хеш-функция
распределяет совокупность возможных ключей
равномерно по множеству индексов, то хеширование
эффективно разбивает множество ключей. Наихудший случай – когда все ключи хешируются в один индекс
. При возникновении коллизий
необходимо найти новое место
для хранения ключей, претендующих на одну и ту же ячейку хеш-таблицы. Причем, если коллизии
допускаются, то их количество необходимо минимизировать. В некоторых специальных случаях удается избежать коллизий
вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую инъективную хеш-функцию, которая распределит их по ячейкам хеш-таблицы без коллизий
. Хеш-таблицы, использующие подобные хеш-функции
, не нуждаются в механизме разрешения коллизий
, и называются хеш-таблицами с прямой адресацией
. Хеш-таблицы должны соответствовать следующим свойствам
. Хеширование
полезно, когда широкий диапазон
возможных значений должен быть сохранен в малом объеме памяти, и нужен способ быстрого, практически произвольного доступа. Хэш-таблицы
часто применяются в базах данных, и, особенно, в языковых процессорах
типа компиляторов и ассемблеров
, где они повышают скорость обработки таблицы идентификаторов. В качестве использования хеширования
в повседневной жизни можно привести примеры распределение книг в библиотеке по тематическим каталогам, упорядочивание в словарях по первым буквам слов, шифрование
специальностей в вузах и т.д. Коллизии
осложняют использование хеш-таблиц, так как нарушают однозначность соответствия между хеш-кодами и данными. Тем не менее, существуют способы преодоления возникающих сложностей: Метод цепочек
. Технология сцепления элементов состоит в том, что элементы множества
, которым соответствует одно и то же хеш- значение
, связываются в цепочку- список
. В позиции номер i
хранится указатель
на голову списка
тех элементов, у которых хеш- значение
ключа равно i
; если таких элементов в множестве нет, в позиции i
записан NULL
. На рис.
38.1 демонстрируется реализация метода цепочек при разрешении коллизий
. На ключ
002 претендуют два значения, которые организуются в линейный список
.
Каждая ячейка
массива является указателем на связный список
(цепочку) пар ключ
- значение
, соответствующих одному и тому же хеш-значению ключа. Коллизии
просто приводят к тому, что появляются цепочки длиной более одного элемента. Операции
поиска или удаления данных требуют просмотра всех элементов соответствующей ему цепочки, чтобы найти в ней элемент с заданным ключом. Для добавления данных нужно добавить элемент в конец или начало соответствующего списка, и, в случае если коэффициент заполнения станет слишком велик, увеличить размер массива и перестроить таблицу. При предположении, что каждый элемент может попасть в любую позицию таблицы с равной вероятностью и независимо от того, куда попал любой другой элемент, Для решения задачи поиска необходимого элемента среди данных большого объема был предложен алгоритм хеширования
(hashing
– перемешивание), при котором создаются ключи, определяющие данные массива и на их основании данные записываются в таблицу, названную хеш-таблицей
. Ключи для записи определяются при помощи функции i = h
(key
)
, называемой хеш-функцией
. Алгоритм хеширования определяет положение искомого элемента в хеш-таблице по значению его ключа, полученного хеш-функцией. Понятие хеширования–
это разбиение общего (базового) набора уникальных ключей элементов данных на непересекающиеся наборы с определенным свойством. Возьмем, например, словарь или энциклопедию. В этом случае буквы алфавита могут быть приняты за ключи поиска, т.е. основным элементом алгоритма хеширования является ключ
(key
). В большинстве приложений ключ обеспечивает косвенную ссылку на данные. Фактически хеширование – это специальный метод адресации данных для быстрого поиска нужной информации по ключам
. Если базовый набор содержит N
элементов, то его можно разбить на 2 N
различных подмножеств. Хеш-таблица и хеш-функции
Функция, отображающая ключи элементов данных во множество целых чисел (индексы в таблице – хеш-таблица
), называется функцией хеширования
, или хеш-функцией
: i
= h
(key
);
где key
– преобразуемый ключ, i
– получаемый индекс таблицы, т.е. ключ отображается во множество целых чисел (хеш-адреса
), которые впоследствии используются для доступа к данным. Однако хеш-функция для нескольких значений ключа может давать одинаковое значение позиции i
в таблице. Ситуация, при которой два или более ключа получают один и тот же индекс (хеш-адрес), называется коллизией
при хешировании. Хорошей хеш-функцией считается такая функция, которая минимизирует коллизии и распределяет данные равномерно по всей таблице, а совершенной хеш-функцией – функция, которая не порождает коллизий: Разрешить коллизии при хешировании можно двумя методами: – методом открытой адресации с линейным опробыванием; – методом цепочек. Хеш-таблица
Хеш-таблица представляет собой обычный массив с необычной адресацией, задаваемой хеш-функцией. Хеш-структуру
считают обобщением массива, который обеспечивает быстрый прямой доступ к данным по индексу. Имеется множество схем хеширования, различающихся как выбором удачной функции h
(key
), так и алгоритма разрешения конфликтов. Эффективность решения реальной практической задачи будет существенно зависеть от выбираемой стратегии. Примеры хеш-функций
Выбираемая хеш-функция должна легко вычисляться и создавать как можно меньше коллизий, т.е. должна равномерно распределять ключи на имеющиеся индексы в таблице. Конечно, нельзя определить, будет ли некоторая конкретная хеш-функция распределять ключи правильно, если эти ключи заранее не известны. Однако, хотя до выбора хеш-функции редко известны сами ключи, некоторые свойства этих ключей, которые влияют на их распределение, обычно известны. Рассмотрим наиболее распространенные методы задания хеш-функции. Метод деления
. Исходными данными являются – некоторый целый ключ key
и размер таблицы m
. Результатом данной функции является остаток от деления этого ключа на размер таблицы. Общий вид функции: int h(int key, int m) { return key % m; // Значения Для m
= 10 хеш-функция возвращает младшую цифру ключа. Для m
= 100 хеш-функция возвращает две младшие цифры ключа. Аддитивный метод
, в котором ключом является символьная строка. В хеш-функции строка преобразуется в целое суммированием всех символов и возвращается остаток от деления на m
(обычно размер таблицы m
= 256). int h(char *key, int m) { Коллизии возникают в строках, состоящих из одинакового набора символов, например, abc
и cab
. Данный метод можно несколько модифицировать, получая результат, суммируя только первый и последний символы строки-ключа. int h(char *key, int m) { int len = strlen(key), s = 0; if(len < 2) // Если длина ключа равна 0 или 1, s = key; // возвратить key s = key + key; В этом случае коллизии будут возникать только в строках, например, abc
и amc
. Метод середины квадрата
, в котором ключ возводится в квадрат (умножается сам на себя) и в качестве индекса используются несколько средних цифр полученного значения. Например, ключом является целое 32-битное число, а хеш-функция возвращает средние 10 бит его квадрата: int h(int key) { key >>= 11; // Отбрасываем 11 младших бит return key % 1024; // Возвращаем 10 младших бит Метод исключающего ИЛИ
для ключей-строк (обычно размер таблицы m
=256). Этот метод аналогичен аддитивному, но в нем различаются схожие слова. Метод заключается в том, что к элементам строки последовательно применяется операция «исключающее ИЛИ». В мультипликативном методе
дополнительно используется случайное действительное число r
из интервала . Если это произведение умножить на размер таблицы m
, то целая часть полученного произведения даст значение в диапазоне от 0 до m
–1. int h(int key, int m) { double r = key * rnd(); r = r – (int)r; // Выделили дробную часть В общем случае при больших значениях m
индексы, формируемые хеш-функцией, имеют большой разброс. Более того, математическая теория утверждает, что распределение получается более равномерным, если m
является простым числом. В рассмотренных примерах хеш-функция i
= h
(key
) только определяет позицию, начиная с которой нужно искать (или первоначально – поместить в таблицу) запись с ключом key
. Поэтому схема хеширования должна включать алгоритм решения конфликтов
, определяющий порядок действий, если позиция i
= h
(key
) оказывается уже занятой записью с другим ключом.Пример задачи. Поиск одинаковых строк
Хэш подстроки и его быстрое вычисление
Применение хэширования
Определение количества различных подстрок
Виды «хеш-функций»
«Хеш-функции», основанные на делении
1. «Хеш-код» как остаток от деления на число всех возможных «хешей»
2. «Хеш-код» как набор коэффициентов получаемого полинома
«Хеш-функции», основанные на умножении
Хеширование строк переменной длины
Универсальное хеширование
Методы борьбы с коллизиями
Методы борьбы с коллизиями в хеш-таблицах
Криптографическая соль
Применение хеш-функций
Криптографические хеш-функции
Методы разрешения коллизий
Рис.
38.1.