Вычисление хеша для объектов класса в Python

Функция hash() в Python вычисляет хеш для неизменяемых объектов (immutable types):

a = hash(123) # 123
b = hash("Python") # -8344082464644304368
c = hash((1, 2, 3)) # 529344067295497451

Если вы попытаетесь взять хеш от изменяемых объектов (например, списка list), то получите ошибку TypeError: unhashable type: 'list'. 😱

Ошибка возникнет даже в том случае, если изменяемый элемент находится внутри неизменяемого объекта. Пример: элементом кортежа является список list. Тогда тоже будет ошибка "unhashable".

Некоторые свойства хешей:
1) Для одинаковых объектов хеши всегда одинаковы.
2) Обратное утверждение в общем случае не верно (разные объекты могут иметь одинаковый хеш — это называется коллизией).
3) Если хеши не равны, то и сами объекты точно не равны.

Зачем это вообще нужно? 🤔

Мы поняли, что такое хеш, теперь давайте разберемся, зачем он нам пригодился! Например, словари используют хеши для быстрого доступа к ключам для быстрого поиска. Ведь помните, словари в ключах требуют только неизменяемые типы данных? Словарь хранит ключи примерно в таком виде: (хеш_ключа, значение_ключа).

А это зачем нужно? Первоначально запись в словаре ищется по хешу, что занимает минимум времени. Далее, если вдруг хеши разных ключей совпали (коллизия), то тогда уже Python дополнительно проверяет объекты на равенство (==).

Хеширование на примере классов

Теперь рассмотрим, как это работает с пользовательскими классами:

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

p1 = Point(1, 2)
p2 = Point(1, 2)

print(hash(p1))
print(hash(p2))

Как думаете? какие будут хеши у этих экземпляров класса? Одинаковые, разные, или вообще ошибка? Разные!
Если p1 == p2 возвращает True, то хеши одинаковые. А если False, то разные(если нет коллизии). Почему так? Коллизия? Нет, все проще. По умолчанию Python вычисляет хеш на основе id объекта (его адреса в памяти) 🧠

Переопределение `__eq__` и `__hash__`

А что если мы переопределим метод __eq__ в классе Point следующим образом?

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

Тогда p1 == p2 станет True. Значит и хеши по идее равны. Но не все так просто) Вылезет ошибка. Хе-хе🙃. Когда мы переопределили __eq__, то функция hash() перестает работать. Т.к. перестает работать стандартный алгоритм вычисления хеша. Иными словами: после переопределения __eq__: Python автоматически делает класс unhashable (`__hash__ = None`), если мы не определили свой `__hash__`. Это защита от нарушения контракта между равенством и хешированием.

Чтобы это исправить, нужно обязательно переопределить метод __hash__ в нашем классе. Он и вызывается (логично, да?), когда мы пишем hash(p1).

    def __hash__(self):
        return hash((self.x, self.y))

Что теперь скажете насчет хешей объектов p1 и p2? Равны! 🎉 Мы теперь вычисляем хеш не от самих объектов (их ID в памяти), а от их координат.

Пример использования в словаре

Например, если по такой логике создавать словарь👇, то получим только одну пару ключ: значение. А если мы не переопределяли эти методы, то получили бы две.

d = {}
d[p1] = 1
d[p2] = 2
print(d) # {<__main__.Point object at 0x0000024D012C8F40>: 2}

Таким образом, мы можем переопределять методы eq и hash под требуемую логику нашей программы. В данном случае, объекты класса Point с одинаковыми координатами воспринимаются как одинаковые объекты. 😏

А вы когда-нибудь сталкивались с ошибкой "unhashable type" в своих проектах? 😁