Хеш-функции возникли как один из вариантов решения задачи «поиска по словарю». Задача состояла в поиске в памяти компьютера (оперативной или постоянной) информации по известному ключу. Возможным способом решения было хранение, например, всего массива ключей (и указателей на содержимое) в отсортированном в некотором порядке списке или в виде бинарного дерева. Однако наиболее производительным с точки зрения времени доступа (при этом обладая допустимой производительностью по времени модификации) стал метод хранения в виде хеш-таблиц. Этот метод ведёт своё происхождение из стен компании IBM (как и многое другое в программировании).
Метод хеш-таблиц подробно разобран в любой современной литературе по программированию [125]. Напомним лишь, что его идея состоит в разделении множества ключей по корзинам (англ. bins) в зависимости от значения некоторой функции, вычисляемой по значению ключа. Причём функция подбирается таким образом, чтобы в разных корзинах оказалось одинаковое число (в идеале – не более одного) ключей. При этом сама функция должна быть быстро вычисляемой, а её значение должно легко конвертироваться в натуральное число, которое не превышает число корзин.
Хеш-функцией (англ. hash function) называется отображение, переводящее аргумент произвольной длины в значение фиксированной длины.
Коллизией хеш-функции называется пара значений аргумента, дающая одинаковый выход хеш-функции. Коллизии есть у любых хеш-функций, если количество различных значений аргумента превышает возможное количество значений результата функции (принцип Дирихле). А если не превышает, то и нет смысла использовать хеш-функцию.
В программировании к свойствам хорошей хеш-функции относят:
Можно назвать и другие свойства, которые были бы полезны для хеш-функции в программировании. К ним можно отнести, например, отсутствие необходимости в дополнительной памяти (неиспользование «кучи»), простоту реализации, стабильность работы алгоритма (возврат одного и того же результата после перезапуска программы), соответствие результатов работы хеш-функции результатам работы других функций, например, функций сравнения (см. например, описания функций hashcode(), equals() и compare() в языке программирования Java).
Однонаправленной функцией $f(x)$ называется функция, обладающая следующими свойствами:
Свойство однонаправленности, в частности, означает, что если в аргументе $x$ меняется хотя бы один символ, то для любого $x$ значение функции $H(x)$ меняется непредсказуемо.
Криптографически стойкой хеш-функцией $H(x)$ называется хеш-функция, имеющая следующие свойства:
Из требования на устойчивость к коллизиям, в частности, следует свойство (близости к) равномерности распределения результата криптографической хеш-функции по области значений. В целом надёжную криптографическую хеш-функ
При произвольной длине последовательности $X$ длина хеш-функции $H(X)$ в российском стандарте ГОСТ Р 34.11-94 равна 256 символам, в американском стандарте SHA несколько различных значений длин: 160, 192, 256, 512 символов.