Как устроено хеширование в Python?

Как устроено хеширование в Python?

Хеширование — фундаментальный механизм, который лежит в основе словарей, множеств и оптимизации памяти. Разберём, как это работает на уровне интернала.

Что такое хеширование?

Хеш — это целое число, которое однозначно идентифицирует объект. Python вычисляет его через функцию hash():

print(hash("hello"))      # 3626403611768859413
print(hash((1, 2, 3)))    # -9223372036854775826
print(hash(42))           # 42
print(hash(3.14))         # 322818021289917153

Ключевое свойство: один и тот же объект всегда должен давать один и тот же хеш.

Hashable vs Unhashable

Hashable (хешируемые): строки, числа, кортежи, frozenset

hash("string")        # OK
hash((1, 2, 3))       # OK
hash(frozenset([1]))  # OK

Unhashable (нехешируемые): списки, словари, множества

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

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

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

Внутри словарь — это хеш-таблица с массивом ячеек:

d = {"name": "Alice", "age": 30}

# Что происходит при d["name"] = "Alice":
# 1. hash("name") -> допустим, 12345
# 2. index = 12345 % table_size  -> допустим, индекс 5
# 3. В ячейке 5 хранится: ("name", "Alice")
# 4. При доступе d["name"] снова вычисляем хеш и находим ячейку

Коллизии хешей

Что если два ключа имеют одинаковый хеш?

# Упрощённый пример
hash_value_1 = hash("cat") % 10    # -> 7
hash_value_2 = hash("dog") % 10    # -> 7  (коллизия!)

Python использует открытую адресацию (open addressing) с методом quadratic probing:

# Если ячейка i занята, пробуем:
# i + 1^2, i + 2^2, i + 3^2 ...
# до тех пор, пока не найдём пустую

Плюс для каждой ячейки хранится и ключ, и значение, чтобы убедиться, что это правильная ячейка.

Реализация кастомного хеширования

Для класса: магические методы

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def __hash__(self):
        return hash((self.name, self.age))
    
    def __eq__(self, other):
        if not isinstance(other, Person):
            return False
        return self.name == other.name and self.age == other.age

# Теперь можно использовать в словарях и множествах
person = Person("Alice", 30)
my_dict = {person: "developer"}
my_set = {Person("Bob", 25), Person("Alice", 30)}

Важно: если переопределяешь __hash__, ОБЯЗАТЕЛЬНО переопредели и __eq__!

p1 = Person("Alice", 30)
p2 = Person("Alice", 30)

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

Встроенные функции хеширования

hashlib — криптографические хеши:

import hashlib

text = "password123"

# MD5 (не рекомендуется для паролей)
md5_hash = hashlib.md5(text.encode()).hexdigest()
print(md5_hash)  # 482c811da5d5b4bc6d497ffa98491e38

# SHA-256 (рекомендуется)
sha256_hash = hashlib.sha256(text.encode()).hexdigest()
print(sha256_hash)

# Для паролей используй bcrypt
import bcrypt
hashed = bcrypt.hashpw(b"password123", bcrypt.gensalt())

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

Поиск в словаре — O(1) в среднем случае, но может быть O(n) в худшем (много коллизий):

# Быстро
d = {i: i**2 for i in range(1000000)}
value = d[999999]  # O(1), миллисекунды

# Медленно (в теории)
# Если все ключи имеют одинаковый хеш

Почему хеши случайны между запусками?

Python 3.3+ использует рандомизированное хеширование для защиты от DoS атак:

python -c "print(hash('test'))"
# 7669829066259890873

python -c "print(hash('test'))"
# -8944596200140737652  (другой результат!)

То же значение может иметь разный хеш при разных запусках. Это сделано, чтобы злоумышленник не смог специально создать коллизии.

Если нужны стабильные хеши, используй hashlib.

Best Practices

1. Используй встроенный hash() для логики, hashlib для криптографии.
2. Для паролей: bcrypt, argon2, scrypt — никогда обычные хеши.
3. Кастомные классы: переопредели оба метода (__hash__ и __eq__).
4. Immutable объекты: хешируются, mutable — нет.
5. Словари быстрее, чем линейный поиск в 1000+ раз для больших данных.

Зачем это нужно на собеседовании?

Понимание хеширования показывает, что ты понимаешь:

• Как работают словари и множества
• Алгоритмическую сложность О(1) vs O(n)
• Почему нельзя использовать изменяемые объекты как ключи
• Основы информационной безопасности

Это базовые знания для любого серьёзного разработчика.