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

Хэш-таблицы в 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))

• Увеличивается использование памяти

• Снижается производительность при большом количестве коллизий