Хеш-функции и их применение
💻 Информатика · 9 класс
Что такое хеш-функция
Хеш-функция — это правило, которое любому входному значению (числу, строке, файлу) сопоставляет короткое число фиксированной длины, называемое хешем. Одинаковый вход всегда даёт одинаковый хеш, а небольшое изменение входа сильно меняет результат.
Хеш-функции используют для быстрого поиска данных, проверки целостности файлов и безопасного хранения паролей. Важно, что хеш гораздо короче исходных данных, и именно поэтому им удобно пользоваться как «отпечатком» информации.
Простой пример
Возьмём строку и сложим коды её символов, а затем возьмём остаток от деления на размер таблицы. Это даст номер ячейки, куда поместить данные:
нач
цел h, i
h := 0
нц для i от 1 до длин(S)
h := h + код(S[i])
кц
h := mod(h, 100)
вывод h
кон
Свойства хорошей хеш-функции
| Свойство | Что означает |
|---|---|
| Однозначность | один вход всегда даёт один и тот же хеш |
| Быстрота | хеш вычисляется за короткое время |
| Равномерность | значения распределяются по таблице без скоплений |
| Чувствительность | малое изменение входа меняет хеш |
Коллизии
Поскольку входов гораздо больше, чем возможных хешей, иногда разные входы дают одинаковый хеш — это коллизия. От коллизий нельзя полностью избавиться, но хорошая функция делает их редкими. Когда коллизия всё же случается, данные хранят в одной ячейке списком и при поиске дополнительно сравнивают сами значения.
Правило: по хешу нельзя восстановить исходные данные. Поэтому пароли хранят не в открытом виде, а в виде хеша: при входе сравнивают хеши, а не сами пароли.
Где применяют
Хеш-таблицы ускоряют поиск: вместо перебора всех записей программа сразу вычисляет номер нужной ячейки и заглядывает только в неё. Благодаря этому поиск в среднем выполняется почти мгновенно, независимо от размера таблицы.
Хеш файла позволяет проверить, не изменился ли он при скачивании: достаточно сравнить хеш скачанного файла с опубликованным. Хранение паролей в виде хешей защищает их даже в случае, если база данных попадёт к злоумышленнику, ведь обратно пароль из хеша не вычислить. Для надёжности к паролю перед хешированием добавляют случайную добавку, чтобы одинаковые пароли давали разные хеши.
Частые ошибки: считают, что хеш можно «расшифровать»; путают хеш с шифрованием; не учитывают коллизии при построении хеш-таблицы и теряют часть данных.
Кратко о главном
- Хеш-функция сопоставляет данным короткое число.
- Одинаковый вход даёт одинаковый хеш, по хешу вход не восстановить.
- Совпадение хешей у разных входов называется коллизией.
- Применяется для поиска, проверки файлов и хранения паролей.