Что такое хеш-функция

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

$h(k) = k \bmod m$

Разбор по случаям

Примеры

Метод деления с остатком. Хеш-таблица на 7 ячеек хранит номера клиентов методом деления с остатком $h(k) = k \bmod 7$. Для ключа $k = 38$ функция даёт остаток $h(38) = 3$, значит запись помещается в ячейку с индексом 3. Поиск номера клиента занимает одно вычисление формулы вместо перебора всех записей подряд по очереди. Пример подходит под определение хеш-функции: входу произвольной величины однозначно и быстро сопоставлен короткий индекс фиксированного размера.

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

Частые ошибки

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

Коротко

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