Какая структура данных лежит в основе dict в Python? Как разрешаются коллизии?

В Python dict реализован на основе хеш-таблицы с открытой адресацией и использованием метода открытой адресации с двойным хешированием (open addressing with probing).

Основные моменты:

• Ключи хешируются, чтобы получить индекс в массиве.
• При коллизии (когда два ключа имеют одинаковый индекс) используется метод пробирования (probing), где ищется следующая свободная ячейка по определённому алгоритму.
• В Python 3.6+ используется упорядоченная реализация словаря, где сохраняется порядок вставки.

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

Это обеспечивает эффективный доступ, вставку и удаление элементов.