Какими свойствами должна обладать хэш-функция, используемая в хэш-таблицах (например, в `map` в Go)?

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

1. Детерминированность (Determinism)

   • Что это? Для одного и того же входного ключа хэш-функция всегда должна возвращать одно и то же хэш-значение.
   • Почему это важно? Если бы хэш менялся, мы бы не смогли найти элемент, который только что положили в map.

2. Эффективность (Efficiency)

   • Что это? Вычисление хэша должно быть очень быстрым.
   • Почему это важно? Хэш-функция вызывается при каждой операции с map (вставка, поиск, удаление). Медленная хэш-функция сведет на нет все преимущества хэш-таблицы (средняя сложность O(1)).

3. Равномерное распределение (Uniformity)

   • Что это? Хэш-функция должна распределять ключи как можно более равномерно по всему диапазону хэш-значений.
   • Почему это важно? Хорошее распределение минимизирует количество коллизий (когда разные ключи получают одинаковый хэш). Если много ключей попадают в один и тот же "бакет", производительность map деградирует до O(n), так как для поиска элемента придется перебирать все ключи в этом бакете.

Пример плохой хэш-функции:

Она не обеспечивает равномерного распределения. Все строки одинаковой длины получат одинаковый хэш.

// Плохо: высокая вероятность коллизий
func badHash(s string) uint32 {
    return uint32(len(s))
}

Пример хорошей хэш-функции (FNV-1a):

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

import "hash/fnv"

func goodHash(s string) uint32 {
    h := fnv.New32a()
    h.Write([]byte(s))
    return h.Sum32()
}

Важное замечание по Go: В Go разработчик не предоставляет свою хэш-функцию для встроенного типа map. Runtime Go использует собственную, быструю и качественную хэш-функцию. Более того, для защиты от DoS-атак (hash-flooding) хэш-функция в Go инициализируется случайным значением при запуске программы, что делает хэши непредсказуемыми между разными запусками.