> Как Python определяет уникальность объекта для ключей словаря (Python)

Короткий ответ

Python определяет уникальность ключа словаря через два механизма: __hash__() для вычисления хэша и __eq__() для проверки равенства при коллизиях. Сначала вычисляется хэш ключа, затем по нему находится bucket, и если там уже есть объекты, вызывается __eq__() для сравнения с существующими ключами. Объекты с одинаковым хэшем и __eq__() == True считаются одним ключом. Ключ должен быть hashable и immutable, иначе его хэш может измениться, что сломает словарь.

Подробное объяснение

Процесс вставки и поиска ключа в dict:

1. Вызывается hash(key) - встроенная функция, которая вызывает key.__hash__().
2. Полученный хэш (целое число) используется для вычисления индекса в массиве buckets: index = hash & mask, где mask - размер массива минус 1.
3. Если bucket пуст - ключ вставляется.
4. Если bucket занят - Python проверяет, совпадает ли хэш уже хранящегося ключа с хэшем нового. Если хэши разные - это коллизия, Python переходит к следующему bucket (open addressing).
5. Если хэши совпадают - вызывается __eq__() для сравнения объектов. Если __eq__() возвращает True - ключи считаются одинаковыми, значение перезаписывается. Если False - продолжается поиск следующего bucket.

Важные детали:

• Для встроенных типов (int, str, tuple) __hash__ и __eq__ уже реализованы и согласованы: если a == b, то hash(a) == hash(b).
• Для пользовательских классов по умолчанию __hash__ основан на id() объекта, а __eq__ - на is. Поэтому разные экземпляры считаются разными ключами.
• Если класс переопределяет __eq__, Python автоматически устанавливает __hash__ = None, делая объекты unhashable. Нужно явно определить __hash__.
• Требование неизменяемости: если ключ меняется после вставки, его хэш меняется, и словарь не сможет его найти - объект "теряется" в dict.

На практике

Для пользовательских классов, используемых как ключи, нужно:

• Реализовать __hash__ на основе неизменяемых атрибутов.
• Реализовать __eq__ согласованно с __hash__.
• Сделать атрибуты, участвующие в хэше, неизменяемыми (например, через @property без сеттера или __slots__).

Пример типичной ошибки - mutable-атрибут в хэше:

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

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

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

p = Point(1, 2)
d = {p: "value"}
p.x = 3  # хэш изменился, ключ потерян
d[p]  # KeyError

Правильный подход - сделать x и y readonly.

Пример кода

PYTHON
class ImmutablePoint:
    __slots__ = ("_x", "_y")

    def __init__(self, x, y):
        self._x = x
        self._y = y

    @property
    def x(self):
        return self._x

    @property
    def y(self):
        return self._y

    def __hash__(self):
        return hash((self._x, self._y))

    def __eq__(self, other):
        if not isinstance(other, ImmutablePoint):
            return NotImplemented
        return (self._x, self._y) == (other._x, other._y)

    def __repr__(self):
        return f"ImmutablePoint({self._x}, {self._y})"

p1 = ImmutablePoint(1, 2)
p2 = ImmutablePoint(1, 2)
d = {p1: "first", p2: "second"}
print(d)  # {ImmutablePoint(1, 2): 'second'} - p1 и p2 считаются одним ключом

# Попытка изменить атрибут вызовет AttributeError
# p1.x = 5  # AttributeError: can't set attribute

Как отвечать на собеседовании

Начни с двух механизмов: __hash__ для позиционирования и __eq__ для разрешения коллизий. Объясни порядок: сначала хэш, потом сравнение при совпадении хэша. Подчеркни требование согласованности: если объекты равны, их хэши обязаны совпадать. Упомяни, что для пользовательских классов при переопределении __eq__ нужно явно задавать __hash__. Добавь про неизменяемость ключей и последствия мутации. Если спросят про производительность - скажи, что в среднем доступ O(1), но при плохом __hash__ (например, константа) деградирует до O(n).

Что проверяет интервьюер

• Понимание разницы между __hash__ и __eq__ и их ролей.
• Знание требований к hashable объектам: согласованность, неизменяемость.
• Понимание последствий нарушения контракта (мутация ключа, несогласованный __eq__).
• Умение реализовать корректный __hash__ для пользовательского класса.
• Осведомленность о поведении встроенных типов и edge cases (например, float('nan') как ключ).

Типичные ошибки

• Утверждение, что уникальность определяется только по __hash__ - без __eq__ коллизии не разрешаются.
• Забывают, что переопределение __eq__ без __hash__ делает объект unhashable.
• Используют mutable-атрибуты в __hash__ - ключ "теряется" после изменения.
• Путают __eq__ и is - для словаря важно именно __eq__.
• Говорят, что dict хранит ключи в порядке вставки - это верно, но не относится к вопросу об уникальности.
• Не упоминают, что hash() для int - это сам int, а для str - сложный алгоритм, но это не критично для ответа.