Как работают коллизии в словарях и хэш-таблицах?

Question

Коллизии возникают, когда разные ключи имеют одинаковый хэш. Python использует открытую адресацию для разрешения коллизий — при конфликте ищется следующая свободная ячейка в таблице. Это обеспечивает эффективный поиск даже при коллизиях.

YeaHub · Accepted Answer

Хэш-таблицы в Python используют алгоритм открытой адресации для разрешения коллизий, когда несколько ключей претендуют на одну ячейку.Механизм разрешения коллизий:При коллизии вычисляется следующая ячейка с помощью пробингаИспользуется формула: perturb = perturb >> 5; j = (5*j) + 1 + perturbПроцесс повторяется до нахождения свободной ячейкиПример коллизии:# Два разных объекта с одинаковым хэшом
class CustomKey:
    def __init__(self, hash_value):
        self.hash_value = hash_value
    
    def __hash__(self):
        return self.hash_value
    
    def __eq__(self, other):
        return isinstance(other, CustomKey)

key1 = CustomKey(42)
key2 = CustomKey(42)  # Тот же хэш

d = {}
d[key1] = "value1"
d[key2] = "value2"  # Коллизия - будет найдена другая ячейкаПоследствия коллизий:Увеличивается время поиска (в худшем случае O(n))Увеличивается использование памятиСнижается производительность при большом количестве коллизий