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

Хеш-таблицы (dict, set) используют хеш, чтобы быстро находить “район” хранения ключа, а затем уточняют совпадение через сравнение ==.

Определение

Определение: Хеш-функция — функция, которая отображает объект в целое число (int), используемое для размещения/поиска объекта в хеш-таблице.

Обязательные свойства для корректности

Чтобы dict/set работали правильно, нужны свойства ниже.

1) Согласованность с равенством

1. Если a == b, то обязательно hash(a) == hash(b)

2. Обратное не требуется: hash(a) == hash(b) не означает, что a == b (это коллизия)

2) Стабильность во времени (для ключа)

Хеш не должен меняться, пока объект используется как ключ:

• Если hash меняется после вставки в dict, то поиск по “тому же” объекту может не найти значение

Отсюда практическое правило:

• Ключи должны быть неизменяемыми (или вести себя как неизменяемые)

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

Для одного и того же состояния объекта __hash__ должен возвращать одинаковый результат в рамках процесса выполнения программы.

Свойства для производительности

Они не про “правильно/неправильно”, а про “быстро/медленно”:

• Быстрое вычисление __hash__

• Хорошее распределение значений (меньше коллизий)

Практика в Python: как правильно определить __hash__

Пример корректного ключа (неизменяемые поля)

class Point:
    __slots__ = ("x", "y")
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        return hash((self.x, self.y))  # хеш от неизменяемой комбинации

Пример проблемы: изменили поле после вставки

p = Point(1, 2)
d = {p: "value"}

p.x = 100          # хеш поменялся (если зависит от x)
# теперь d[p] может работать неожиданно

Вывод

• Для корректности важно: a == b ⇒ hash(a) == hash(b) и неизменяемость данных, участвующих в хеше.

• Для скорости важно: хороший “разброс” хешей и быстрый __hash__.