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

# Почему нельзя использовать изменяемые структуры как ключи словаря

Ключевой момент: хеширование и неизменяемость

Словари в Python используют хеш-таблицы для быстрого поиска. Каждый ключ хешируется в индекс массива. Если ключ изменится, его хеш изменится, и словарь не сможет найти значение.

Требование: ключ должен быть hashable

# Hashable объекты (неизменяемые) — подходят как ключи
dict_key = {
    42: "число",           # int ✅
    "name": "строка",      # str ✅
    (1, 2, 3): "кортеж",   # tuple ✅
    True: "булев",         # bool ✅
}

# Non-hashable объекты (изменяемые) — НЕ подходят
try:
    bad_key = {[1, 2, 3]: "значение"}  # list ❌
except TypeError as e:
    print(e)  # unhashable type: 'list'

try:
    bad_key = {{"a": 1}: "значение"}  # dict ❌
except TypeError as e:
    print(e)  # unhashable type: 'dict'

try:
    bad_key = {{1, 2, 3}: "значение"}  # set ❌
except TypeError as e:
    print(e)  # unhashable type: 'set'

Почему изменяемость проблема: хеш нарушается

Сценарий проблемы

# Представим, если бы мы МОГЛИ использовать список как ключ
key = [1, 2, 3]
my_dict = {key: "value"}

# Хеш ключа в момент создания: hash([1, 2, 3]) = H1
# Индекс в таблице: H1 % table_size = 5
# my_dict[5] → "value"

print(my_dict[key])  # Находим: "value" ✅

# Но потом кто-то изменяет ключ
key[1] = 999  # Меняем список на [1, 999, 3]

# Теперь хеш другой: hash([1, 999, 3]) = H2
# Новый индекс: H2 % table_size = 8
# my_dict[8] → None

print(my_dict[key])  # Не находим! ❌
# KeyError или возвращает значение из позиции 8

Внутренний механизм: хеш-функция

# Неизменяемые объекты имеют СТАБИЛЬНЫЙ хеш
a = (1, 2, 3)
print(hash(a))  # 529344067295497451
print(hash(a))  # 529344067295497451 (ОДИНАКОВЫЙ!)

# Изменяемые объекты НЕ имеют хеш
my_list = [1, 2, 3]
print(hash(my_list))  # TypeError: unhashable type: 'list'

# Почему? Потому что Python не может гарантировать,
# что хеш останется таким же после изменения

Как Python проверяет, является ли объект hashable

class MyImmutableClass:
    """Собственный неизменяемый класс"""
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        """Метод __hash__ делает объект hashable"""
        return hash(self.value)
    
    def __eq__(self, other):
        """Нужен для сравнения"""
        return isinstance(other, MyImmutableClass) and self.value == other.value

# Теперь можно использовать как ключ
obj = MyImmutableClass(42)
my_dict = {obj: "значение"}  # ✅ Работает!

class MyMutableClass:
    """Мутируемый класс — НЕЛЬЗЯ использовать как ключ"""
    def __init__(self, value):
        self.value = value
    
    # Если явно устанавливаем __hash__ = None,
    # то объект становится non-hashable
    __hash__ = None

# Теперь НЕЛЬЗЯ использовать как ключ
obj = MyMutableClass(42)
try:
    my_dict = {obj: "значение"}  # ❌
except TypeError as e:
    print(e)  # unhashable type: 'MyMutableClass'

Правило: если переопределяешь eq, нужен hash

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __eq__(self, other):
        """Переопределили сравнение"""
        return self.x == other.x and self.y == other.y
    
    # ВАЖНО: если переопределяем __eq__,
    # нужно либо переопределить __hash__,
    # либо явно запретить (установить = None)
    
    def __hash__(self):
        """Теперь это hashable"""
        return hash((self.x, self.y))

point = Point(1, 2)
my_dict = {point: "координата"}  # ✅ Работает

# Но если бы мы НЕ определили __hash__:
class BadPoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    # __hash__ не определён
    # В Python 3 это автоматически устанавливает __hash__ = None

bad_point = BadPoint(1, 2)
try:
    my_dict = {bad_point: "координата"}  # ❌
except TypeError:
    print("Cannot use BadPoint as dict key")

Практический пример: почему это критично

# ПРОБЛЕМА: использование списка (если бы было возможно)
users = {}
user_id = [123]  # Если бы можно было использовать как ключ

users[user_id] = {"name": "Alice", "age": 30}
print(users[user_id])  # {"name": "Alice", "age": 30}

# Кто-то случайно изменяет список
user_id[0] = 456

# Теперь не можем найти!
print(user_id in users)  # False ❌
print(users.get(user_id))  # None ❌

# Данные потеряны!

Решение: использовать кортежи

# ПРАВИЛЬНО: использовать кортеж (неизменяемый)
users = {}
user_id = (123,)  # Кортеж, неизменяемый ✅

users[user_id] = {"name": "Alice", "age": 30}
print(users[user_id])  # {"name": "Alice", "age": 30}

# Даже если попытаться изменить, это просто создаст новый объект
user_id = (456,)  # Это новый кортеж, старый не изменился
print(user_id in users)  # False (это другой ключ)
print((123,) in users)  # True (оригинальный ключ все ещё там)

# Более сложный пример с вложенными кортежами
coordinates = {
    (0, 0): "origin",
    (1, 2): "point1",
    ((1, 2), (3, 4)): "line",  # Кортеж из кортежей!
}

Как работает хеш-таблица словаря

# Внутренний процесс:

class SimpleDictImpl:
    def __init__(self):
        self.table = [None] * 16  # Начальный размер
        self.size = 0
    
    def put(self, key, value):
        # 1. Вычисляем хеш ключа
        hash_value = hash(key)
        
        # 2. Вычисляем индекс в таблице
        index = hash_value % len(self.table)
        
        # 3. Сохраняем (с обработкой коллизий)
        self.table[index] = (key, value)
        self.size += 1
    
    def get(self, key):
        # 1. Вычисляем хеш ключа (ДОЛЖЕН БЫТЬ СТАБИЛЬНЫМ!)
        hash_value = hash(key)
        
        # 2. Вычисляем индекс
        index = hash_value % len(self.table)
        
        # 3. Получаем значение
        if self.table[index] is not None:
            stored_key, value = self.table[index]
            if stored_key == key:  # Проверяем равенство
                return value
        return None

# Если ключ изменился между put и get, хеши будут разные!
# Поэтому ключ ДОЛЖЕН быть неизменяемым

Почему Python требует неизменяемость: причины

1. Производительность

# С изменяемыми ключами пришлось бы:
# - Каждый раз перехешировать ключ при поиске
# - Проверять, изменился ли ключ
# - Перестраивать таблицу

# Это замедлило бы поиск со O(1) на O(n)

2. Корректность

# Если бы позволили изменяемые ключи,
# словарь мог бы потерять данные:

my_dict = {}
key = [1, 2, 3]
my_dict[key] = "value"

key.append(4)  # Изменяем ключ

# Теперь данные потеряны или доступны неправильно

3. Семантика языка

# Договор: если x == y и x hashable, то hash(x) == hash(y)
# Это условие может быть нарушено с изменяемыми объектами

a = [1, 2]
b = [1, 2]
# a == b (True), но если бы были ключами, нарушилось бы свойство

Что можно использовать как ключи

# ✅ МОЖНО (неизменяемые)
valid_keys = {
    None: "null",
    True: "boolean",
    42: "integer",
    3.14: "float",
    "string": "text",
    b"bytes": "binary",
    (1, 2, "nested"): "tuple",
    frozenset([1, 2, 3]): "frozenset",
}

# ❌ НЕЛЬЗЯ (изменяемые)
invalid = {
    [1, 2]: "list",           # TypeError
    {1, 2}: "set",             # TypeError
    {"a": 1}: "dict",          # TypeError
    bytearray(b"data"): "ba",  # TypeError
}

Заключение

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

1. Хеш должен быть стабильным: неизменяемость гарантирует, что хеш не изменится
2. Быстрый поиск: O(1) поиск требует стабильного хеша
3. Корректность: изменение ключа приведёт к потере данных
4. Семантика: ключ определяет позицию в хеш-таблице, он не может меняться

Используйте неизменяемые типы (кортежи, frozenset) для создания ключей из сложных структур.