Какие знаешь требования к ключу хеш таблицы?

Требования к ключу хеш-таблицы в Python

В Python словари (dict) и множества (set) используют хеш-таблицы для быстрого поиска элементов. К ключам хеш-таблицы предъявляются строгие требования.

1. Требование неизменяемости (Immutability)

Ключи должны быть неизменяемыми (hashable) объектами. Это основное требование.

# ✅ Правильно: используем неизменяемые типы
my_dict = {
    "name": "John",           # str — неизменяемый
    42: "answer",             # int — неизменяемый
    (1, 2, 3): "tuple",      # tuple — неизменяемый
    True: "boolean",          # bool — неизменяемый
    3.14: "float",           # float — неизменяемый
    None: "none_value"        # None — неизменяемый
}

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

my_dict = {
    {"a": 1}: "dict"         # TypeError: unhashable type: "dict"
}

my_dict = {
    {1, 2, 3}: "set"         # TypeError: unhashable type: "set"
}

2. Требование хешируемости (Hashability)

Объект должен иметь метод __hash__(), возвращающий целое число. Это число используется для определения позиции в хеш-таблице.

class GoodKey:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return hash(self.value)
    
    def __eq__(self, other):
        return isinstance(other, GoodKey) and self.value == other.value

class BadKey:
    def __init__(self, value):
        self.value = value
    
    # Нет __hash__ метода для неизменяемого объекта

# Использование
good_key = GoodKey("test")
my_dict = {good_key: "value"}  # ✅ Работает

bad_key = BadKey("test")
my_dict = {bad_key: "value"}   # ❌ TypeError: unhashable type

3. Требование консистентности хеша

Если объект используется как ключ, его хеш не должен меняться во время жизни объекта. Иначе его невозможно будет найти в словаре.

class BadKey:
    def __init__(self, value):
        self.value = value  # Изменяемое поле!
    
    def __hash__(self):
        return hash(self.value)
    
    def __eq__(self, other):
        return isinstance(other, BadKey) and self.value == other.value

# Проблема
key = BadKey("initial")
my_dict = {key: "value"}
print(key in my_dict)  # True

key.value = "changed"  # Меняем значение ключа!
print(key in my_dict)  # False - ключ больше не находится!
print(my_dict[key])    # KeyError

4. Равенство и хеш должны быть согласованы

Если два объекта равны (a == b), их хеши должны быть одинаковыми (hash(a) == hash(b)).

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

# ✅ Правильно
key1 = ImmutableKey(1, 2)
key2 = ImmutableKey(1, 2)

print(key1 == key2)          # True
print(hash(key1) == hash(key2))  # True

my_dict = {key1: "first"}
my_dict[key2] = "second"     # Перезаписывает значение для key1
print(len(my_dict))          # 1 (один ключ, не два!)

5. Встроенные хешируемые типы

Хешируемые (можно использовать как ключи):

# Неизменяемые типы
int, float, complex         # Числовые типы
str, bytes                   # Строковые типы
tuple                        # Кортеж (если содержит только хешируемые элементы)
frozenset                    # Неизменяемое множество
None, True, False           # Синглтоны
range                        # Диапазон

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

list, dict, set             # Изменяемые коллекции
bytearray                    # Изменяемое бинарное представление

6. Tuple как ключ — особенности

Тупли хешируемы, но только если они содержат хешируемые элементы:

# ✅ Правильно
my_dict = {
    (1, "a", 3.14): "tuple with immutable elements"
}

# ❌ Неправильно
my_dict = {
    (1, "a", [2, 3]): "tuple with list"  # TypeError: unhashable type: "list"
}

7. Пользовательские классы

По умолчанию пользовательские классы хешируемы (используют id объекта), но имеют определённые методы __eq__, которые делают их нехешируемыми:

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

# ✅ Работает (используется идентификатор объекта)
point1 = Point(1, 2)
point2 = Point(1, 2)
my_dict = {point1: "p1", point2: "p2"}  # Два разных ключа
print(len(my_dict))  # 2

class PointWithEquals:
    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__, объект становится нехешируемым
point3 = PointWithEquals(1, 2)
my_dict = {point3: "value"}  # TypeError: unhashable type

8. Практический пример правильной реализации

from typing import Tuple
from dataclasses import dataclass

@dataclass(frozen=True)  # frozen=True делает класс неизменяемым
class User:
    id: int
    name: str
    email: str
    
    def __hash__(self):
        return hash((self.id, self.name))
    
    def __eq__(self, other):
        return isinstance(other, User) and self.id == other.id

# Использование
user1 = User(1, "John", "john@example.com")
user2 = User(1, "John", "john@example.com")

user_dict = {user1: "developer"}
print(user2 in user_dict)       # True (одинаковый hash и eq)
print(user_dict[user2])         # "developer"

user_set = {user1, user2}
print(len(user_set))            # 1 (один уникальный пользователь)

Резюме требований

1. Неизменяемость — ключ не должен изменяться после добавления в словарь
2. Хешируемость — объект должен иметь метод __hash__()
3. Консистентность — хеш не должен меняться во время жизни объекта
4. Согласованность с равенством — если a == b, то hash(a) == hash(b)
5. Встроенные типы — используй str, int, tuple, frozenset; избегай list, dict, set
6. Пользовательские классы — правильно реализуй __hash__ и __eq__ вместе

Эти требования гарантируют корректную работу словарей и множеств и позволяют Python быстро находить элементы за O(1).