Что такое хэширование и зачем оно нужно?

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

Хэширование - это процесс, в котором вы подаёте на вход некоторого хэширующего алгоритма некоторые достаточно большие по объёму данные (допустим миллион байт) и получаете на выходе относительно короткую (допустим 32 байта), но при этом достаточно уникальную строку, которая позволяет отличить эти ваши данные (что были на входе) от каких-то других данных. Эта строка называется "хэш".

Хэш используется для того, чтобы быстрее отличать одни данные от других без необходимости сравнивать каждый-каждый бит этих данных. Достаточно обработать эти данные один раз (вычислить их хэши) и можно сравнивать только их, а это гораздо быстрее. Идея такая. Если хэши различаются, значит, это совершенно точно разные данные. Если хэши одинаковы, значит, с вероятностью в 99,99999... (и ещё 70 девяток, если предположить идеальное распределение 256-битных хэшей), это одинаковые данные. Хотя всегда существует маленький шанс, что данные всё-таки разные, несмотря на одинаковые хэши.

Хэширующий алгоритм (хэш-функция) должен стремиться как можно лучше выполнять следующие требования:

1. Одни и те же данные должны давать всегда один и тот же хэш. Это обязательное условие.

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

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

1. Весь доступный диапазон хэшей используется по максимуму. То есть, если на хэш отведено 32 байта, то разные данные дают максимально разнообразный хэш, который может являться совершенно любой комбинацией битов. То есть, диапазон хэшей не "простаивает".

2. Даже небольшое изменение входных данных (даже изменение 1 бита входных данных) должно давать другой хэш. Не должно быть такого, что небольшие изменения дают тот же самый хэш. Тот же самый хэш должен возникать в результате какого-то совершенно другого набора данных, чтобы вероятность случайного присутствия двух таких данных (дающих одинаковый хэш) была минимальной.

Для чего нужен хэш. Допустим, у вас есть массив из миллиона разных (неодинаковых) строк. В каждой строке миллион символов (то есть, всего у вас 1 терабайт = 1000 гигабайт данных). Вам приходит такое указание: добавьте строку, которая содержит "тото-сёто-пятое-десятое-и-ещё-миллион-символов", в ваш массив, но только в том случае, если такой строки там ещё нет.

В итоге, ваша задача превращается в посимвольное сравнение миллиона символов в миллионах строк. Очень хорошо, если начала строк у вас разные и вы сможете быстро отсеивать неподходящие строки. Но если все строки содержат примерно одинаковый текст, то вам нужно провернуть гигантское количество работы.

Но если перед записью вы имеете (вычислили их ранее) хэши эти строк, то ваша задача превращается в сравнение 32 символов вместо миллиона символов (32 мегабайта данных на весь массив). Если вы обнаружили, что у вас в списке есть точно такой же хэш, то для полной надёжности, вы можете сравнить посимвольно только эту строку. Гораздо меньше затрат, чем проверять терабайт целиком, не так ли? (На самом деле, даже 32 мегабайта хэшей проверять не потребуется, поскольку по теории вероятностей, лишь 1-2 первых символа хэшей будут совпадать, да и то очень редко, а 3 одинаковых символа подряд, возможно, не найдутся во всём миллионе хэшей. И это при том, что изначальные данные могли быть очень похожими.)

Хэш также может использоваться для проверки целостности данных при передаче. Вы передали гигабайт данных. А затем передали 32-байтный хэш. Получатель на своей стороне захешировал этот гигабайт тем же способом (той же хэш-функцией) и получил тот же самый хэш. Теперь он уверен, что он имеет точно те же данные, что и отправитель (вероятность случайной ошибки примерно около 1e-70, поэтому ей можно пренебречь; на самом деле, вероятность, скорее всего, ещё меньше, потому что хорошая хэш-функция не даст такой же хэш на похожих данных).

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