Почему не любой тип данных может быть ключом словаря в Python?

Требования к ключам словаря: хешируемость

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

1. Метод __hash__(), возвращающий целое число
2. Метод __eq__() для сравнения
3. Неизменяемость — хеш не должен изменяться в течение жизни объекта

Как словарь работает внутри

Словари в Python построены на хеш-таблицах:

# Когда мы пишем:
user_age = {"Alice": 30, "Bob": 25}

# Внутри Python делает:
# 1. Вычисляет хеш ключа: hash("Alice") → 12416037344
# 2. Использует хеш для вычисления индекса в массиве
# 3. Проверяет коллизии через __eq__()
# 4. Сохраняет пару ключ-значение

Почему нужна хешируемость

Быстрый поиск O(1). Без хеша пришлось бы искать ключ линейно через весь словарь:

# ❌ Если бы списки были хешируемы (медленно)
data = {[1, 2, 3]: "value"}  # TypeError: unhashable type: 'list'

# Пришлось бы сравнивать:
for key, val in data.items():
    if key == [1, 2, 3]:  # Сравнение всех элементов O(n)
        return val

# ✅ С хешем (быстро)
data = {(1, 2, 3): "value"}  # Tuple хешируемый
# Поиск: hash((1, 2, 3)) → индекс → O(1)

Какие типы хешируемы

Встроенные неизменяемые типы:

# Хешируемы
data = {
    "string": 1,        # str — неизменяемый
    42: "int",          # int — неизменяемый
    3.14: "float",      # float — неизменяемый
    True: "bool",       # bool — неизменяемый
    (1, 2): "tuple",    # tuple — если содержит только хешируемые
    None: "none",       # NoneType — хешируемый
}

# НЕ хешируемы
data = {
    [1, 2]: "list",     # ❌ TypeError: unhashable type: 'list'
    {1, 2}: "set",      # ❌ TypeError: unhashable type: 'set'
    {"a": 1}: "dict",   # ❌ TypeError: unhashable type: 'dict'
}

Почему список не может быть ключом

Список изменяемый — его содержимое может меняться:

key = [1, 2, 3]
data = {key: "value"}  # ❌ TypeError

# Даже если бы это работало, проблема:
key.append(4)  # Теперь ключ изменился, но его хеш остался прежним
# Словарь больше не найдет значение!

Поэтому Python запрещает использование изменяемых объектов как ключей.

Интересный случай: кортежи

# Кортеж хешируемый, но только если все его элементы хешируемы
data = {
    (1, 2, 3): "ok",               # ✅ Все int
    ("a", "b"): "ok",              # ✅ Все str
    (1, (2, 3)): "ok",             # ✅ Вложенный кортеж с int
    (1, [2, 3]): "error",          # ❌ Содержит список
    ("text", {"a": 1}): "error",  # ❌ Содержит словарь
}

Как реализовать свой хешируемый класс

class User:
    def __init__(self, user_id: int, email: str):
        self.user_id = user_id
        self.email = email
    
    def __hash__(self):
        # Хеш должен быть основан только на неизменяемых полях
        return hash((self.user_id, self.email))
    
    def __eq__(self, other):
        if not isinstance(other, User):
            return NotImplemented
        return self.user_id == other.user_id and self.email == other.email

# Теперь можно использовать User как ключ
user_mapping = {
    User(1, "alice@example.com"): "Administrator",
    User(2, "bob@example.com"): "User",
}

Важное правило: неизменяемость

class Point:
    def __init__(self, x: float, y: float):
        self.x = x
        self.y = y
    
    def __hash__(self):
        return hash((self.x, self.y))
    
    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

p = Point(1, 2)
locations = {p: "home"}

# ❌ ПРОБЛЕМА: если изменим координаты
p.x = 5
print(locations.get(p))  # None! Не найдет значение

Решение: сделать класс truly immutable:

from dataclasses import dataclass

@dataclass(frozen=True)  # frozen=True делает объект неизменяемым
class Point:
    x: float
    y: float

p = Point(1, 2)
locations = {p: "home"}
p.x = 5  # ❌ FrozenInstanceError

Производительность хеширования

import hashlib

# Хеш строки вычисляется за O(n) где n — длина строки
text = "a" * 1000000
hash(text)  # Медленнее, чем hash("short")

# Хеши чисел — O(1)
hash(42)  # Быстро
hash(42.5)  # Быстро

# Хеши кортежей
hash((1, 2, 3, 4, 5))  # Зависит от размера и типов элементов

Вывод

Ограничение на ключи словаря (только хешируемые типы) — это не баг, а feature. Оно обеспечивает:

1. Производительность O(1) для поиска
2. Безопасность от использования мутабельных объектов
3. Предсказуемость — ключ всегда найдется (если его не удалили)

Этот дизайн критичен для эффективности Python как языка.