Что такое хеш-функция?

«Что такое хеш-функция?» — вопрос из категории Алгоритмы и структуры данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

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

Ключевые свойства хорошей хеш-функции:

  1. Детерминированность: Один и тот же вход всегда даёт одинаковый хеш.
  2. Равномерность (равномерное распределение): Выходные значения должны равномерно распределяться по всему диапазону возможных хешей, чтобы минимизировать коллизии.
  3. Эффективность: Вычисление хеша должно быть быстрым (O(1) в идеале).
  4. Устойчивость к коллизиям: Вероятность того, что два разных входа дадут одинаковый хеш (коллизия), должна быть крайне низкой.

Применение в программировании:

  • Хеш-таблицы (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() у объектов-ключей.