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

Question

Хеш-функция должна быть детерминированной: для одного и того же объекта (в одном состоянии) она должна возвращать одно и то же число. Главное правило: если a == b, то hash(a) == hash(b) обязательно. Также хеш должен зависеть только от неизменяемых данных объекта, иначе ключ “потеряется” в dict/set. Для скорости важно, чтобы вычисление хеша было быстрым и давало хорошее распределение, чтобы было меньше коллизий.

YeaHub · Accepted Answer

Хеш-таблицы (dict, set) используют хеш, чтобы быстро находить “район” хранения ключа, а затем уточняют совпадение через сравнение ==.ОпределениеОпределение: Хеш-функция — функция, которая отображает объект в целое число (int), используемое для размещения/поиска объекта в хеш-таблице.Обязательные свойства для корректностиЧтобы dict/set работали правильно, нужны свойства ниже.1) Согласованность с равенствомЕсли a == b, то обязательно hash(a) == hash(b)Обратное не требуется: 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__.