Какими свойствами должна обладать хорошая хеш-функция?

Основные свойства хорошей хеш-функции

Хеш-функция преобразует произвольные данные в число фиксированной длины. Чтобы она была полезной на практике, она должна удовлетворять нескольким ключевым требованиям. Рассмотрим их по порядку.

Детерминированность

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

Равномерность распределения

Хеш-функция должна равномерно распределять входные данные по всему диапазону выходных значений. Это снижает вероятность коллизий, когда разные входы дают одинаковый хеш. Например, для хеш-таблицы с 1000 ячейками идеально, чтобы каждый ключ попадал в любую ячейку с вероятностью 1/1000.

Лавинный эффект

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

Устойчивость к коллизиям

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

Пример простой хеш-функции

function simpleHash(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash * 31 + str.charCodeAt(i)) | 0;
  }
  return hash;
}

Эта функция использует умножение на простое число 31 и побитовое ИЛИ с нулём для ограничения 32-битным диапазоном. Она детерминирована и даёт приемлемое распределение для строк.

Вывод

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