Для чего нужна хешируемость объектов в Python?

Хешируемость объектов в Python

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

Основная потребность в хешируемости

1. Ключи в словарях (dict)

# Хешируемые типы можно использовать как ключи
d = {
    'name': 'Ivan',        # str — хешируем
    42: 'number',          # int — хешируем
    (1, 2, 3): 'tuple',    # tuple — хешируем
    3.14: 'pi',            # float — хешируем
}

# Нехешируемые типы — ошибка!
# d[[1, 2, 3]] = 'list'  # TypeError: unhashable type: 'list'
# d[{'a': 1}] = 'dict'   # TypeError: unhashable type: 'dict'

2. Элементы множеств (set)

# Хешируемые типы можно добавлять в set
my_set = {1, 2, 3, 'hello', (4, 5)}

# Нехешируемые типы — ошибка!
# my_set.add([1, 2, 3])  # TypeError: unhashable type: 'list'

3. Поиск и уникальность

Хеширование позволяет быстро проверять наличие элемента:

# O(1) поиск благодаря хешированию
if 'key' in my_dict:       # Быстро
if 'value' in my_set:      # Быстро

# Без хеширования пришлось бы проходить по всему списку (O(n))
if 'value' in my_list:     # Медленнее при большом списке

Как работает хешированием

# Встроенная функция hash()
print(hash('hello'))       # 123456789 (может быть разным между запусками)
print(hash(42))            # 42
print(hash((1, 2, 3)))     # 529344067

# Для одного объекта хеш всегда одинаков
key = 'python'
print(hash(key))           # 123...
print(hash(key))           # 123... — тот же

Dictionary в Python работает так:

# Когда вы пишите d['key'] = 'value'
# 1. Вычисляется hash('key')
# 2. Этот хеш используется как индекс во внутреннем массиве
# 3. Значение сохраняется по этому адресу

# Когда вы ищете d['key']
# 1. Вычисляется hash('key') — ТОТ ЖЕ хеш
# 2. Ищется значение по тому же индексу
# 3. Находится за O(1) в среднем случае

Хешируемые vs нехешируемые типы

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

hash(42)                   # int
hash(3.14)                 # float
hash('hello')              # str
hash(True)                 # bool
hash((1, 2, 3))            # tuple (если элементы хешируемы!)
hash(None)                 # NoneType

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

hash([1, 2, 3])            # TypeError: unhashable type: 'list'
hash({'a': 1})             # TypeError: unhashable type: 'dict'
hash({1, 2, 3})            # TypeError: unhashable type: 'set'

# Почему? Потому что они изменяемы (mutable)

Tuple — особый случай

# Tuple хеширующий, если все его элементы хешируемы
hash((1, 2, 3))            # OK
hash(('a', 'b'))           # OK

# Но если в tuple хоть один нехешируемый элемент — ошибка
hash((1, [2, 3]))          # TypeError: unhashable type: 'list'
hash(([1, 2], 'a'))        # TypeError

Реальные примеры использования

Кеширование результатов функций

from functools import lru_cache

@lru_cache(maxsize=128)
def fibonacci(n):          # n должно быть хешируемо
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

fibonacci(10)  # Результаты кешируются по хешу аргумента

# Это работает с int, str, tuple
# Но не с list: @lru_cache не может кешировать функции с list аргументами

Удаление дубликатов

# С помощью set (использует хеширование)
items = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(items))  # [1, 2, 3, 4] — быстро

# С хешируемыми кортежами
data = [(1, 2), (1, 2), (3, 4)]
unique_tuples = list(set(data))  # O(n) благодаря хешированию

Группировка данных

# Подсчет частоты элементов
from collections import Counter

frequencies = Counter(['a', 'b', 'a', 'c', 'a'])
# Counter использует dict под капотом, нужна хешируемость

for item, count in frequencies.items():
    print(f'{item}: {count}')  # a: 3, b: 1, c: 1

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

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

class Person:
    def __init__(self, name):
        self.name = name

p1 = Person('Alice')
p2 = Person('Alice')

print(hash(p1) == hash(p2))  # False — разные объекты
print(p1 == p2)               # False — разные объекты

# Но если переопределить __eq__, нужно переопределить и __hash__

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

p1 = PersonFixed('Alice')
p2 = PersonFixed('Alice')

print(p1 == p2)              # True
print(hash(p1) == hash(p2))  # True

# Теперь можно использовать как ключи в dict
d = {p1: 'person1'}
print(d[p2])  # 'person1' — работает!

Почему изменяемые типы нехешируемы

# Если бы list был хеширующим...
my_dict = {[1, 2]: 'value'}
my_list = [1, 2]

my_list.append(3)  # Теперь [1, 2, 3]
# Хеш сменился бы! Поиск в dict перестал бы работать
# Это нарушило бы консистентность dict

Поэтому изменяемые типы специально сделаны нехешируемыми — это гарантирует корректность работы dict и set.