Хеширование

Материал из Википедии — свободной энциклопедии

Хеши́рование — преобразование входного массива данных в короткое число фиксированной длины (которое называется хешем или хеш-кодом) таким образом, чтобы с одной стороны, это число было значительно короче исходных данных, а с другой стороны, с большой вероятностью однозначно им соответствовало. Преобразование выполняется при помощи хеш-функции. Ясно, что в общем случае однозначного соответствия между исходными данными и хеш-кодом быть не может. Обязательно будут возможны массивы данных, дающих одинаковые хеш-коды, но вероятность таких совпадений в каждой конкретной задаче должна быть сведена к минимуму выбором хеш-функции.

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

Кроме этого, существует много других способов хеширования, подходящих к различным задачам.

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

Криптографическая хеш-функция должна обеспечивать:

• стойкость к коллизиям (два различных набора данных должны иметь различные результаты преобразования)
• необратимость (невозможность вычислить исходные данные по результату преобразования)

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

• хорошая перемешиваемость данных
• быстрый алгоритм вычисления

[править] Применение хеширования

[править] Проверка на наличие ошибок

Например, контрольная сумма может быть передана по каналу связи вместе с основным текстом. На приёмном конце, контрольная сумма может быть рассчитана заново и её можно сравнить с переданным значением. Если будет обнаружено расхождение, то это значит, что при передаче возникли искажения и можно запросить повтор.

Бытовым аналогом хеширования в данном случае может служить приём, когда при переездах в памяти держат количество мест багажа. Тогда для проверки не нужно вспоминать про каждый чемодан, а достаточно их посчитать. Совпадение будет означать, что ни один чемодан не потерян. То есть, количество мест багажа является его хеш-кодом.

[править] Ускорение поиска данных

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

Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.

[править] Список алгоритмов

• CRC
• SHA-1
• SHA-2 (SHA-256, SHA-384, SHA-512)
• HAVAL
• MD2
• MD4
• MD5
• N-Hash
• RIPEMD-160
• Snefru
• Tiger
• Whirlpool
• ГОСТ 3411
• TTH

Это незавершённая статья о компьютерах. Вы можете помочь проекту, исправив и дополнив её.