Когда сложность операций со словарем может ухудшиться?

Словарь (dict) в Python — это реализация хеш-таблицы. В идеальном случае, когда хеш-функция распределяет ключи равномерно, основные операции (get, set, delete) выполняются за константное время O(1). Однако есть ситуации, когда производительность резко падает.

Причины ухудшения сложности

• Коллизии хешей: Если разные ключи имеют одинаковый хеш, они помещаются в одну ячейку (бакет). Внутри бакета поиск становится линейным (O(n) для этого бакета). При большом количестве коллизий общая сложность стремится к O(n).
• Плохая хеш-функция: Для пользовательских классов, если метод __hash__ написан плохо и возвращает одинаковые значения для разных объектов.
• Атака hashDoS: Злоумышленник может передать множество специально подобранных ключей, вызывающих коллизии, что приведёт к отказу в обслуживании.
• Изменение размера (resize/rehash): При добавлении элементов, когда заполненность превышает порог, внутренний массив увеличивается, и все существующие пары ключ-значение должны быть перехешированы и перемещены. Это операция O(n), но она происходит нечасто и амортизируется до O(1).

Пример кода, демонстрирующий коллизии

# Пользовательский класс с плохой хеш-функцией
class BadKey:
    def __init__(self, value):
        self.value = value
    def __hash__(self):
        return 1  # Все объекты имеют одинаковый хеш!
    def __eq__(self, other):
        return self.value == other.value

# Создание словаря с такими ключами
bad_dict = {}
for i in range(1000):
    key = BadKey(i)
    bad_dict[key] = i  # Каждая вставка будет вызывать линейный поиск в цепочке коллизий.
# Операции с этим словарём будут иметь сложность O(n).

В современных версиях Python (с 3.3+) используется рандомизация хешей для строк и некоторых типов, что затрудняет проведение hashDoS-атак. Также для разрешения коллизий используется открытая адресация (начиная с CPython 3.6), что в целом улучшает производительность.

Вывод: Сложность операций со словарём ухудшается при высоком уровне коллизий хешей, что может быть вызвано плохой хеш-функцией или злонамеренным вводом. Для предотвращения важно использовать в качестве ключей стандартные хешируемые типы (строки, числа, кортежи) и обновлять Python до актуальной версии с защитой от hashDoS.