Какие условия накладываются на ключ в словаре?

Условия для ключей в словаре Python

Словарь (dict) в Python — это структура данных, которая требует определенные свойства от ключей для корректной работы. Понимание этих условий критично для эффективной разработки.

Основное условие: Хешируемость (Hashability)

Ключ должен быть хешируемым (hashable). Это значит, что объект должен иметь:

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

# Хешируемые типы (могут быть ключами)
hashable_dict = {
    1: 'int',                    # int
    'key': 'str',                # str
    (1, 2): 'tuple',             # кортеж из hashable элементов
    frozenset([1, 2]): 'set',   # frozenset
    True: 'bool',                # bool (это int)
    None: 'none',                # None
    3.14: 'float'                # float
}

# Нехешируемые типы (НЕ могут быть ключами)
try:
    bad_dict = {
        [1, 2]: 'list'           # ошибка! list не hashable
    }
except TypeError as e:
    print(f"Ошибка: {e}")  # unhashable type: 'list'

try:
    bad_dict = {
        {1, 2}: 'set'            # ошибка! set не hashable
    }
except TypeError as e:
    print(f"Ошибка: {e}")  # unhashable type: 'set'

try:
    bad_dict = {
        {'a': 1}: 'dict'         # ошибка! dict не hashable
    }
except TypeError as e:
    print(f"Ошибка: {e}")  # unhashable type: 'dict'

Условие 1: Неизменяемость (Immutability)

Объект не должен менять свое значение после создания. Это гарантирует, что хеш остается константным.

# Правильно: неизменяемые объекты
immutable_keys = {
    'alice': 'id1',
    42: 'id2',
    (10, 20): 'id3'
}

# После создания они не меняются
key_str = 'alice'
key_tuple = (10, 20)
immutable_keys[key_str] = 'updated1'
immutable_keys[key_tuple] = 'updated3'
# Это работает, потому что сами ключи не меняются

# Неправильно: попытка использовать изменяемый объект
my_list = [1, 2]
try:
    d = {my_list: 'value'}
except TypeError:
    print("Нельзя использовать список как ключ")

# Даже если список содержит только hashable элементы
my_list = [1, 2, 3]  # все элементы hashable
try:
    d = {my_list: 'value'}
except TypeError:
    print("Даже список из чисел нельзя как ключ")

Условие 2: Консистентность хеша (Hash Consistency)

Для одного объекта хеш должен оставаться одинаковым на протяжении жизни программы.

# Правильно: хеш остается постоянным
key = 'alice'
hash_1 = hash(key)
hash_2 = hash(key)
hash_3 = hash(key)

print(hash_1 == hash_2 == hash_3)  # True

d = {'alice': 'user1'}
value = d['alice']  # все три хеша указывают на одно место

# Правильно: для чисел
key = 42
hash_1 = hash(key)
hash_2 = hash(key)
print(hash_1 == hash_2)  # True

# Правильно: для кортежей
key = (1, 'a', 3.14)
hash_1 = hash(key)
hash_2 = hash(key)
print(hash_1 == hash_2)  # True

Условие 3: Равенство и хеш должны быть согласованы

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

# Правильно: согласованные hashes
a = 1
b = 1.0

print(a == b)  # True
print(hash(a) == hash(b))  # True! В Python int(1) == float(1.0)

d = {1: 'one'}
print(d[1.0])  # 'one' — можно получить значение

# Правильно: строки
s1 = 'hello'
s2 = 'hello'
print(s1 == s2)  # True
print(hash(s1) == hash(s2))  # True

key_dict = {s1: 'value'}
print(key_dict[s2])  # 'value' — получается то же значение

# Кортежи (содержат hashable элементы)
t1 = (1, 'a')
t2 = (1, 'a')
print(t1 == t2)  # True
print(hash(t1) == hash(t2))  # True

Условие 4: Уникальность (для использования как ключа)

Обычно ключи уникальны в словаре. Если добавить дубликат, старое значение заменяется.

d = {}
d['name'] = 'Alice'
print(d)  # {'name': 'Alice'}

d['name'] = 'Bob'  # заменяет значение
print(d)  # {'name': 'Bob'}
print(len(d))  # 1 — все еще один элемент

# Для одинаковых объектов
d = {}
d[1] = 'one'
d[1] = 'one_updated'
print(d)  # {1: 'one_updated'}
print(len(d))  # 1

# Но можно специально перезаписывать
d[(1, 2)] = 'value1'
d[(1, 2)] = 'value2'  # новое значение
print(d[(1, 2)])  # 'value2'

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

# Хешируемые (могут быть ключами)
hashable_types = {
    'int': 1,
    'float': 3.14,
    'str': 'hello',
    'bool': True,
    'None': None,
    'tuple': (1, 2, 3),
    'frozenset': frozenset([1, 2]),
    'bytes': b'hello'
}

# Проверка
for type_name, value in hashable_types.items():
    try:
        h = hash(value)
        d = {value: 'key'}
        print(f'{type_name}: hashable ✓')
    except TypeError:
        print(f'{type_name}: NOT hashable ✗')

# Нехешируемые (НЕ могут быть ключами)
unhashable_types = {
    'list': [1, 2, 3],
    'dict': {'a': 1},
    'set': {1, 2, 3},
    'bytearray': bytearray(b'hello')
}

for type_name, value in unhashable_types.items():
    try:
        h = hash(value)
        print(f'{type_name}: hashable ✓')
    except TypeError:
        print(f'{type_name}: NOT hashable ✗')

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

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

class User:
    def __init__(self, id, name):
        self.id = id
        self.name = name

u1 = User(1, 'Alice')
u2 = User(1, 'Alice')

# По умолчанию хешируемы
d = {u1: 'user1', u2: 'user2'}
print(len(d))  # 2! Разные объекты

# Чтобы использовать по значению, нужно переопределить __hash__ и __eq__
class UserWithHash:
    def __init__(self, id, name):
        self.id = id
        self.name = name
    
    def __hash__(self):
        return hash((self.id, self.name))
    
    def __eq__(self, other):
        return isinstance(other, UserWithHash) and \
               self.id == other.id and self.name == other.name

u1 = UserWithHash(1, 'Alice')
u2 = UserWithHash(1, 'Alice')

d = {u1: 'user1', u2: 'user2'}
print(len(d))  # 1! Одно и то же значение
print(d[u1])  # 'user2' — последнее присвоение

# Важно: если переопределяешь __eq__, переопредели и __hash__
class BadUser:
    def __init__(self, id, name):
        self.id = id
        self.name = name
    
    def __eq__(self, other):
        return self.id == other.id
    # НО не переопределили __hash__!

bad_u = BadUser(1, 'Alice')
try:
    d = {bad_u: 'value'}
except TypeError:
    print("TypeError: unhashable type 'BadUser'")
    # Python3 делает класс unhashable, если переопределена __eq__ но не __hash__

Frozenset для "множества ключей"

Если нужен ключ из нескольких значений, используй frozenset или кортеж.

# Неправильно: set нельзя как ключ
try:
    d = {{1, 2, 3}: 'value'}
except TypeError:
    print("TypeError: unhashable type 'set'")

# Правильно: frozenset вместо set
d = {frozenset([1, 2, 3]): 'value'}
print(d)  # {frozenset({1, 2, 3}): 'value'}

# Правильно: кортеж вместо списка
d = {(1, 2, 3): 'value'}
print(d)  # {(1, 2, 3): 'value'}

# Использование: группировка
from collections import defaultdict

pairs = [(1, 'a'), (1, 'b'), (2, 'a'), (1, 'a')]
grouped = defaultdict(list)

for value, group in pairs:
    # Нельзя использовать список как ключ
    # grouped[[value, group]] = ...  # ошибка!
    # Используем кортеж
    grouped[(value, group)].append(1)

for key, count in grouped.items():
    print(f'{key}: {len(count)} раз')

Производительность: Hash Table внутри

Понимание хеширования помогает писать эффективный код.

# O(1) доступ благодаря хешу
d = {str(i): i for i in range(1000000)}

# Все эти операции O(1):
value = d['42']  # берется хеш от '42', ищется в таблице
if '100' in d:  # быстро: хеш определяет позицию
    pass
del d['50']  # быстрое удаление

# Если хеш-функция плохая, может быть коллизия
class BadHash:
    def __hash__(self):
        return 1  # ВСЕ объекты имеют одинаковый хеш!

# Этот словарь будет медленным O(n)
bad_keys = [BadHash() for _ in range(1000)]
d = {key: i for i, key in enumerate(bad_keys)}
# Доступ O(n) вместо O(1)!

Практические рекомендации

# ✓ Хорошо: используй встроенные типы
config = {
    'debug': True,
    'timeout': 30,
    'hosts': ('localhost', '127.0.0.1'),
    'tags': frozenset(['api', 'v1'])
}

# ✓ Хорошо: для составных ключей
user_cache = {}
user_cache[('alice', 'role')] = 'admin'
user_cache[('bob', 'role')] = 'user'

# ✓ Хорошо: для пользовательских классов
class Coordinates:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __hash__(self):
        return hash((self.x, self.y))
    
    def __eq__(self, other):
        return isinstance(other, Coordinates) and \
               self.x == other.x and self.y == other.y

map_cache = {
    Coordinates(10, 20): 'mountain',
    Coordinates(30, 40): 'river'
}

# ✗ Неправильно: изменяемые объекты
points = [[1, 2], [3, 4]]
# d = {tuple(p): 'value' for p in points}  # преобразуй в кортеж

# ✗ Неправильно: классы со стороне-эффектами в __hash__
class BadClass:
    def __hash__(self):
        print("Computing hash...")  # побочный эффект!
        return 1

Итоговое резюме

Соблюдение этих условий гарантирует корректность и производительность работы со словарями.