Хеширование

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

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

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

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

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

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

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

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

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

Содержание

1 Применение хеширования
- 1.1 Проверка на наличие ошибок
- 1.2 Ускорение поиска данных
2 Список алгоритмов

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

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

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

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

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

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

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