Почему ключом словаря может быть только хэшируемый объект?

Почему ключом словаря может быть только хэшируемый объект

Это вопрос о внутреннем устройстве словарей в Python и требованиях к ключам. Ответ лежит в том, как работает хеширование и поиск по ключам.

Что такое хешируемость

Хешируемый объект — это объект, который:

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

# Хешируемые объекты
print(hash(42))          # 42
print(hash("hello"))     # -6269882022127485970 (для этой сессии)
print(hash((1, 2, 3)))   # -5934435307929783025
print(hash(frozenset([1, 2])))  # -5936396997816256263

# Нехешируемые объекты
try:
    hash([1, 2, 3])  # TypeError: unhashable type: 'list'
except TypeError as e:
    print(e)

try:
    hash({"key": "value"})  # TypeError: unhashable type: 'dict'
except TypeError as e:
    print(e)

Как работают словари в Python

Словарь в Python — это хеш-таблица, внутренняя структура данных, которая использует хеширование для быстрого поиска.

┌─────────────────────────────────────┐
│  Словарь (Hash Table)               │
├─────────────────────────────────────┤
│  Индекс 0: [('name', 'Alice'), ... ]│
│  Индекс 1: [('age', 30), ...]       │
│  Индекс 2: [('city', 'NYC'), ...]   │
│  Индекс 3: empty                    │
│  Индекс 4: [('email', '...'), ...]  │
│  ...                                │
└─────────────────────────────────────┘

Процесс поиска по ключу в словаре

Когда ты делаешь d['key'] = value:

1. Вычисляется хеш ключа

   hash_value = hash('key')  # например: -5034441684147899033
   

2. Определяется позиция в таблице

   index = hash_value % len(dict_table)  # например: индекс 42
   

3. Проверяется коллизия (если два ключа дают одинаковый хеш)

   На позиции 42 могут быть несколько пар (key, value)
   Словарь сравнивает с каждым ключом: key == 'key'
   

4. Возвращается значение если ключ найден

# Демонстрация
def simplified_dict_get(d, key):
    """
    Упрощённая версия того, как работает d[key]
    """
    hash_val = hash(key)
    index = hash_val % len(d)
    
    # В реальности там может быть несколько элементов
    for k, v in d.items():
        if k == key:
            return v
    
    raise KeyError(key)

my_dict = {'name': 'Bob', 'age': 25}
print(simplified_dict_get(my_dict, 'name'))  # 'Bob'

Почему ключ должен быть неизменяемым

Имагинируй, что изменяемые объекты можно использовать как ключи:

# ❌ ОПАСНО (если бы Python это позволял)
my_list = [1, 2, 3]
d = {my_list: 'value'}  # TypeError сейчас

# Теперь что-то изменилось
my_list.append(4)  # my_list теперь [1, 2, 3, 4]

# Проблема: хеш изменился!
# hash([1, 2, 3]) != hash([1, 2, 3, 4])
# Теперь Python не может найти значение по ключу
print(d[my_list])  # KeyError или неправильный результат

Это нарушило бы инвариант словаря: если ключ в словаре, его можно найти по хешу.

# ✅ ПРАВИЛЬНО с неизменяемыми объектами
my_tuple = (1, 2, 3)
d = {my_tuple: 'value'}  # OK

# Нельзя изменить tuple
# my_tuple[0] = 99  # TypeError: 'tuple' object does not support item assignment

# Хеш остаётся неизменным
print(d[my_tuple])  # 'value' — всегда найдёт

Требование: hash(obj1) == hash(obj2) ⟹ obj1 == obj2

Это критическое требование для хеш-таблиц:

class BuggyClass:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 42  # Всегда одинаковый хеш
    
    def __eq__(self, other):
        return isinstance(other, BuggyClass) and self.value == other.value

obj1 = BuggyClass(1)
obj2 = BuggyClass(1)

# hash(obj1) == hash(obj2), и obj1 == obj2
# ✅ Это работает
d = {obj1: 'first'}
print(d[obj2])  # 'first' — найдёт по хешу

# Но если хеш изменяется:
class BuggyClass2:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return self.value  # Зависит от value
    
    def __eq__(self, other):
        return isinstance(other, BuggyClass2) and self.value == other.value

obj = BuggyClass2(1)
d = {obj: 'value'}
# obj.value = 2  # Если изменить (не делай так!)
# hash(obj) вернёт 2, но словарь хранит его на позиции для hash=1
# d[obj]  # Не найдёт!

Почему коллекции типа list и dict не хешируемы

# list и dict изменяемы
my_list = [1, 2, 3]
my_list.append(4)  # Изменяется

# Их хеш не может быть стабильным
try:
    d = {my_list: 'value'}
except TypeError as e:
    print(e)  # unhashable type: 'list'

# Но кортежи хешируемы, если содержат хешируемые элементы
my_tuple = (1, 2, 3)
print(hash(my_tuple))  # работает

# Если кортеж содержит list, он нехеширем
my_mixed = (1, [2, 3])  # tuple содержит list
try:
    hash(my_mixed)
except TypeError as e:
    print(e)  # TypeError: unhashable type: 'list'

Внутреннее устройство: словарь как реализация

// Упрощённая схема того, как Python реализует dict

struct DictEntry {
    PyObject *key;
    PyObject *value;
    Py_hash_t hash;  // Кешированное значение хеша
};

struct Dict {
    DictEntry *entries;
    Py_ssize_t size;
    Py_ssize_t capacity;
};

// Функция поиска
static PyObject *
dict_lookup(PyDictObject *mp, PyObject *key)
{
    Py_hash_t hash = PyObject_Hash(key);  // Вычисляется хеш
    if (hash == -1) return NULL;  // Ошибка если нехеширем
    
    Py_ssize_t ix = hash % mp->capacity;  // Позиция в таблице
    
    // Проверяются коллизии
    while (mp->entries[ix].key != NULL) {
        if (mp->entries[ix].hash == hash &&
            PyObject_RichCompareBool(mp->entries[ix].key, key, Py_EQ) == 1) {
            return mp->entries[ix].value;  // Найдено!
        }
        ix = (ix + 1) % mp->capacity;  // Следующая позиция
    }
    
    return NULL;  // Не найдено
}

Практические следствия

# ✅ Хешируемые ключи — лучше всегда
dict_users = {
    1: {'name': 'Alice'},
    'user_2': {'name': 'Bob'},
    ("coordinates", 10, 20): {'name': 'Charlie'},
}

# ❌ Нехешируемые ключи — ошибка
try:
    dict_bad = {
        ['user', 1]: {'name': 'Alice'},  # TypeError
    }
except TypeError:
    pass

# ✅ Обходной путь: использовать кортежи вместо списков
dict_good = {
    ('user', 1): {'name': 'Alice'},
    ('user', 2): {'name': 'Bob'},
}

# Если нужно изменяемое отображение
from collections import defaultdict
mutable_mapping = defaultdict(list)  # Ключи всё равно хешируемые
mutable_mapping['key'].append('value')

Вывод

1. Словари используют хеш-таблицы — это структура данных, которая требует быстрого вычисления позиции по ключу

2. Хешируемость обеспечивает O(1) поиск — вычисляется хеш, определяется позиция, поиск

3. Неизменяемость гарантирует стабильность хеша — если хеш изменится, словарь не найдёт ключ

4. Это центральное ограничение Python, защищающее целостность данных и производительность

5. Для нехешируемых объектов используй frozenset вместо set или кортежи вместо списков когда нужны как ключи