Хеширование

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

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

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

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

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

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

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

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

Содержание

Применение хеширования

Проверка на наличие ошибок

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

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

Ускорение поиска данных

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

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

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

  • CRC
  • DES
  • SHA-1
  • SHA-2 (SHA-256, SHA-384, SHA-512)
  • HAVAL
  • MD2
  • MD4
  • MD5
  • N-Hash
  • RIPEMD-160
  • Snefru
  • Tiger
  • Whirlpool
  • ГОСТ 3411
  • TTH
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home