Что произойдёт, если у двух элементов будет одинаковый хеш?

Это называется коллизия хешей. При использовании хеш-таблиц (например, словарей в Python), если два ключа имеют одинаковый хеш, они не могут быть помещены в одну и ту же "корзину" (bucket) напрямую. Вместо этого применяется стратегия разрешения коллизий.

Одна из распространенных стратегий — метод цепочек (chaining). В этом случае в каждой корзине хранится не один элемент, а список или другая структура данных (например, связанный список), содержащая все элементы, хеши которых совпадают и указывают на эту корзину.

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

Другая стратегия — открытая адресация (open addressing). В этом случае при коллизии алгоритм ищет следующую свободную корзину по определенному правилу (например, линейное или квадратичное зондирование), чтобы разместить элемент. При поиске также используется зондирование до нахождения элемента с совпадающим ключом или пустой корзины.

В Python словари используют комбинацию этих подходов, оптимизированную для производительности.

# Пример коллизии хешей в словаре
class CollidingKey:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        # Имитация одинакового хеша для разных объектов
        return 42

    def __eq__(self, other):
        if isinstance(other, CollidingKey):
            return self.value == other.value
        return False

key1 = CollidingKey("A")
key2 = CollidingKey("B")

# Хотя хеши равны, __eq__ определяет их как разные ключи
print(f"Хеш key1: {hash(key1)}")
print(f"Хеш key2: {hash(key2)}")
print(f"key1 == key2: {key1 == key2}")

my_dict = {key1: 10, key2: 20}

# При доступе по ключу, несмотря на одинаковый хеш, Python
# использует метод __eq__ для разрешения коллизии
print(f"Значение по key1: {my_dict[key1]}")
print(f"Значение по key2: {my_dict[key2]}")

# При добавлении нового элемента с тем же хешем, но другим значением,
# он будет помещен в ту же "корзину", но считаться отдельным элементом
key3 = CollidingKey("A") # Равен key1 по значению
my_dict[key3] = 30

# Теперь key1 и key3 указывают на одно и то же место в словаре из-за __eq__
print(f"Значение по key1 после добавления key3: {my_dict[key1]}")

Коллизии хешей — это нормальное явление в хеш-таблицах. Хорошая хеш-функция минимизирует их вероятность. Однако при большом количестве коллизий производительность операций вставки, удаления и поиска в хеш-таблице может ухудшаться, приближаясь к O(n) в наихудшем случае.