Страница 4

Хеш-фукнция

Свойства хеш-функции

Хеш-функция (англ. hash function от hash — «превращать в фарш»), или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».[7]

Свойства хеш-функции:

• Должна обладать свойствами функции.
• Не должна обязательно являться инъективной или сюръективной.

Определения :

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

Хеш

элемент области значений, соотнесённый с заранее известным элементом из области определения.

Хеширование

это процесс получения хеша.

Коллизия

ситуация, при которой нарушается условие инъективности хеш-функции.

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