Ответ
Хеш-функция — это детерминированный алгоритм, который принимает на вход данные произвольного размера (ключ) и возвращает фиксированное значение (хеш-код) фиксированной длины (например, 32-битное целое число в Java).
Ключевые свойства хорошей хеш-функции:
- Детерминированность: Один и тот же вход всегда даёт одинаковый хеш.
- Равномерность (равномерное распределение): Выходные значения должны равномерно распределяться по всему диапазону возможных хешей, чтобы минимизировать коллизии.
- Эффективность: Вычисление хеша должно быть быстрым (O(1) в идеале).
- Устойчивость к коллизиям: Вероятность того, что два разных входа дадут одинаковый хеш (коллизия), должна быть крайне низкой.
Применение в программировании:
- Хеш-таблицы (HashMap, HashSet): Хеш-код используется для быстрого определения "корзины" (bucket), в которой хранится или ищется элемент, обеспечивая среднюю сложность O(1) для операций
get()иput(). - Криптография: Специальные криптографические хеш-функции (SHA-256) используются для проверки целостности данных, цифровых подписей, хранения паролей.
- Кеширование: Хеш может выступать в качестве ключа для быстрого поиска закэшированных данных.
Пример в Java:
String text = "Hello";
int hashCode = text.hashCode(); // Вычисляет хеш-код строки
System.out.println(hashCode); // Вывод, например: 69609650
// Важно: для корректной работы в HashMap должны быть переопределены
// и equals(), и hashCode() у объектов-ключей.