Может ли у 2 ключей словаря быть одинаковый хэш?

Может ли у 2 ключей словаря быть одинаковый хэш?

Ответ: ДА, два разных ключа могут иметь одинаковый хеш. Это называется "hash collision" (коллизия хешей).

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

Понимание хешей в dictionary

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

1. Вычисляется хеш ключа: hash(key)
2. Используется этот хеш для быстрого поиска в таблице
3. Если обнаруживается коллизия (разные ключи с одинаковым хешем), используется == для проверки равенства

Важный момент: Два ключа считаются одинаковыми, если:

• Они имеют одинаковый хеш И
• Они равны по значению (==)

Демонстрация коллизии хешей

Пример 1: Разные строки с одинаковым хешем (редко, но возможно)

# В Python есть встроенный алгоритм для вычисления хешей
hash("ab")  # -8666387606065833213
hash("ba")  # 6302598434767980903

# Обычно разные строки имеют разные хеши
# Но теоретически коллизия возможна

# Пример с числами
hash(1)  # 1
hash(1.0)  # 1 - одинаковый хеш!

# Но это не проблема, потому что 1 == 1.0
print(1 == 1.0)  # True

my_dict = {}
my_dict[1] = "int"
my_dict[1.0] = "float"

print(len(my_dict))  # 1 - они считаются одним ключом
print(my_dict)  # {1: 'float'} - второе значение перезаписало первое

Пример 2: Умышленная коллизия хешей

# Создаём класс с фиксированным хешем
class BadKey:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 42  # Всегда один и тот же хеш!
    
    def __eq__(self, other):
        return isinstance(other, BadKey) and self.value == other.value
    
    def __repr__(self):
        return f"BadKey({self.value})"

# Используем в dictionary
my_dict = {}
key1 = BadKey("a")
key2 = BadKey("b")
key3 = BadKey("a")

my_dict[key1] = "value1"
my_dict[key2] = "value2"
my_dict[key3] = "value3"  # Перезапишет key1, так как key1 == key3

print(my_dict)  # {BadKey(a): 'value3', BadKey(b): 'value2'}
print(len(my_dict))  # 2

# Проверка
print(hash(key1) == hash(key2))  # True - одинаковый хеш
print(key1 == key2)  # False - разные значения

Как dictionary справляется с коллизиями

Внутри Python использует open addressing с linear probing (в старых версиях) или compact dictionaries (в Python 3.6+).

# Визуально процесс поиска
my_dict = {}

class HashCollisionKey:
    def __init__(self, name):
        self.name = name
    
    def __hash__(self):
        return 42  # Одинаковый хеш для всех
    
    def __eq__(self, other):
        return isinstance(other, HashCollisionKey) and self.name == other.name
    
    def __repr__(self):
        return f"Key({self.name})"

# Добавляем ключи с одинаковым хешем
key1 = HashCollisionKey("first")
key2 = HashCollisionKey("second")
key3 = HashCollisionKey("third")

my_dict[key1] = "val1"
my_dict[key2] = "val2"
my_dict[key3] = "val3"

print(len(my_dict))  # 3 - все разные ключи
print(my_dict[key1])  # "val1"
print(my_dict[key2])  # "val2"
print(my_dict[key3])  # "val3"

Реальный пример из Python: int и float

# В Python int и float с одинаковым значением имеют одинаковый хеш
print(hash(1))  # 1
print(hash(1.0))  # 1
print(1 == 1.0)  # True

# Поэтому они считаются одним ключом
d = {1: "integer", 1.0: "float"}
print(len(d))  # 1
print(d)  # {1: 'float'}

# Проверка
print(d[1])  # 'float'
print(d[1.0])  # 'float' - обращаются к одному и тому же значению

Конфликт между hash() и ==

Правило в Python:

• Если a == b, то hash(a) == hash(b) (обязательно)
• Если hash(a) == hash(b), то a == b может быть False или True

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __hash__(self):
        return hash((self.x, self.y))
    
    def __eq__(self, other):
        if not isinstance(other, Point):
            return False
        return self.x == other.x and self.y == other.y

p1 = Point(1, 2)
p2 = Point(1, 2)
p3 = Point(2, 3)

print(hash(p1) == hash(p2))  # True - одинаковый хеш
print(p1 == p2)  # True - они равны
print(hash(p1) == hash(p3))  # False - разные хеши
print(p1 == p3)  # False - они не равны

d = {}
d[p1] = "first"
d[p2] = "second"  # Перезапишет p1
print(len(d))  # 1

Плохая реализация хеша (нарушение контракта)

class BadPoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __hash__(self):
        return 42  # Плохо: всегда одинаковый хеш
    
    def __eq__(self, other):
        if not isinstance(other, BadPoint):
            return False
        return self.x == other.x and self.y == other.y

# Это работает, но неправильно
p1 = BadPoint(1, 2)
p2 = BadPoint(1, 2)
p3 = BadPoint(3, 4)

print(hash(p1) == hash(p2))  # True
print(p1 == p2)  # True
print(hash(p1) == hash(p3))  # True - ПЛОХО!
print(p1 == p3)  # False - но хеши одинаковые

d = {}
d[p1] = "first"
d[p2] = "second"  # Перезаписывает
d[p3] = "third"  # Тоже добавляется
print(len(d))  # 2 - работает, но неэффективно

# При поиске нужно проверять все коллизии вручную
for key in d:
    if key == p1:
        print(d[key])  # Нужно проверять каждый ключ

Практический пример: когда коллизии хешей замедляют код

import time

# Хороший хеш
class GoodHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return hash(self.value)
    
    def __eq__(self, other):
        return isinstance(other, GoodHash) and self.value == other.value

# Плохой хеш (коллизия)
class BadHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 0  # Все имеют одинаковый хеш!
    
    def __eq__(self, other):
        return isinstance(other, BadHash) and self.value == other.value

# Тест производительности
print("Good hash:")
d = {GoodHash(i): i for i in range(100000)}
start = time.time()
for i in range(10000):
    _ = d[GoodHash(50000)]
print(f"Time: {time.time() - start:.4f}s")  # Быстро

print("\nBad hash:")
d = {BadHash(i): i for i in range(100000)}
start = time.time()
for i in range(10000):
    _ = d[BadHash(50000)]
print(f"Time: {time.time() - start:.4f}s")  # ОЧЕНЬ медленно!

Правильная реализация hash() и ==

from dataclasses import dataclass

@dataclass(frozen=True)  # frozen=True делает hashable
class User:
    id: int
    name: str
    email: str
    
    def __hash__(self):
        # Хешируем только поля, которые не меняются
        return hash((self.id, self.email))
    
    def __eq__(self, other):
        if not isinstance(other, User):
            return False
        # Сравниваем по id и email
        return self.id == other.id and self.email == other.email

# Использование
users = {}
user1 = User(1, "John", "john@example.com")
user2 = User(1, "Jane", "john@example.com")  # Другое имя, но одинаковый id и email
user3 = User(2, "John", "john2@example.com")

users[user1] = "first"
users[user2] = "second"  # Перезапишет user1
users[user3] = "third"

print(len(users))  # 2
print(users[user1])  # "second"

Вывод

Может ли быть коллизия хешей:

• ✓ ДА, два разных ключа могут иметь одинаковый хеш
• Это нормально и expected в некоторых случаях (например, int и float)

Как это работает:

• Если хеши одинаковые, Python проверяет равенство с ==
• Если a == b, они считаются одним ключом
• Если a != b, они считаются разными ключами

Хорошие практики:

• Если переопределяешь __hash__(), переопредели и __eq__()
• Убедись, что если a == b, то hash(a) == hash(b)
• Стремись к распределению хешей, чтобы избежать коллизий (это улучшает производительность)