Какая связь между hash-функцией и изменяемостью/неизменяемостью типов?

Hash-функции и изменяемость типов

Основной принцип: Объект может использоваться как ключ словаря или элемент множества только если его хеш не меняется. Это значит, что только неизменяемые (immutable) типы могут быть hashable.

Неизменяемые типы — hashable

# int, float, str, tuple - неизменяемые, hashable
print(hash(42))           # 42
print(hash(3.14))         # 3.14
print(hash("hello"))      # 8946734968093915261
print(hash((1, 2, 3)))    # -8027176449867935021

# Можно использовать как ключи в словаре
my_dict = {
    42: "answer",
    "name": "John",
    (1, 2): "coordinates",
}
print(my_dict[42])         # "answer"
print(my_dict[(1, 2)])     # "coordinates"

# Можно добавлять в set
unique_values = {1, 2, 3, "hello", (1, 2)}
print(unique_values)       # {1, 2, 3, "hello", (1, 2)}

Изменяемые типы — NOT hashable

# list, dict, set - изменяемые, НЕ hashable
print(hash([1, 2, 3]))     # TypeError: unhashable type: "list"
print(hash({"key": "value"}))  # TypeError: unhashable type: "dict"
print(hash({1, 2, 3}))     # TypeError: unhashable type: "set"

# Нельзя использовать как ключи
my_dict = {
    [1, 2]: "coordinates"  # TypeError: unhashable type: "list"
}

# Нельзя добавлять в set
unique_lists = {[1, 2], [3, 4]}  # TypeError: unhashable type: "list"

Почему так? Логика изменяемости

# Неизменяемый объект - его хеш остаётся одинаковым
name = "Alice"
name_hash_1 = hash(name)
# Строка не может измениться, хеш не меняется
name_hash_2 = hash(name)
print(name_hash_1 == name_hash_2)  # True - всегда True

# Если бы строка была изменяемой и мы могли бы сделать:
# name[0] = "B"  # Измени первый символ
# name_hash_2 = hash(name)  # Хеш изменится!
# Словарь потеряет ключ в своей хеш-таблице!

Пример проблемы с изменяемостью

# Представим, что списки можно было бы использовать как ключи
my_dict = {}
key = [1, 2, 3]
my_dict[key] = "value"
# Словарь добавил ключ в хеш-таблицу

# Потом мы изменили список
key.append(4)
# Хеш изменился: hash([1, 2, 3, 4]) != hash([1, 2, 3])
# Но ключ в словаре остался в СТАРОЙ позиции хеш-таблицы
# Словарь теперь не найдёт свой же ключ!
# my_dict[key]  # KeyError!

Tuple - особый случай

# Кортежи неизменяемы И hashable
coord = (10, 20)
print(hash(coord))        # hashable
my_dict = {coord: "location"}  # Работает
my_set = {coord, (5, 10)}  # Работает

# НО! Если tuple содержит изменяемый объект, он НЕ hashable
mixed_tuple = (1, [2, 3])  # list внутри tuple
print(hash(mixed_tuple))   # TypeError: unhashable type: "list"

# Правило: tuple hashable только если все его элементы hashable
good_tuple = (1, 2, "hello")  # Все элементы hashable
print(hash(good_tuple))    # Работает

bad_tuple = (1, 2, {"a": 1})  # dict внутри - НЕ hashable
print(hash(bad_tuple))     # TypeError

Кастомные классы - важное правило

class Person:
    def __init__(self, name: str, age: int):
        self.name = name
        self.age = age
    
    def __eq__(self, other):
        return self.name == other.name and self.age == other.age
    
    # ВАЖНО! После __eq__ Python считает класс unhashable!
    # Нужно явно определить __hash__

person1 = Person("Alice", 30)
print(hash(person1))       # TypeError: unhashable type

Как правильно сделать класс hashable

from typing import Any

class Person:
    def __init__(self, name: str, age: int):
        self.name = name
        self.age = age
    
    def __eq__(self, other: Any) -> bool:
        if not isinstance(other, Person):
            return False
        return self.name == other.name and self.age == other.age
    
    def __hash__(self) -> int:
        # Хеш должен быть основан на неизменяемых полях
        return hash((self.name, self.age))

person1 = Person("Alice", 30)
person2 = Person("Alice", 30)

print(person1 == person2)  # True
print(hash(person1) == hash(person2))  # True - важно!

my_dict = {person1: "employee"}
print(my_dict[person2])    # "employee" - находит по равенству

Правило для immutable классов

from dataclasses import dataclass

# frozen=True делает класс неизменяемым и автоматически hashable
@dataclass(frozen=True)
class Point:
    x: int
    y: int

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

print(hash(p1) == hash(p2))  # True
print(p1 == p2)              # True

my_set = {p1, p2}
print(my_set)                # {Point(x=1, y=2)} - дубликат удален

Ключевые выводы

• Hashable объекты = неизменяемые (int, str, tuple, frozenset)
• Unhashable объекты = изменяемые (list, dict, set, обычные классы)
• Почему? При изменении объекта его хеш меняется, и словарь/set теряют возможность найти ключ
• Правило: Если переопределяешь __eq__, определи и __hash__
• Лучшая практика: Используй @dataclass(frozen=True) для hashable иммутабельных классов