Что такое коллизия в хэш-таблицах? Как Python разрешает коллизии?

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

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

Пример упрощённой идеи:

# Допустим, хэш для ключа1 и ключа2 совпал
index = hash(key1) % size
if table[index] is occupied:
    # ищем следующий индекс по формуле
    index = (index + step) % size
# вставляем элемент

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