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

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

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

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

Пример за решаване на колизии е линейното пробиране или двойното хеширане, но в CPython се използва алгоритъм с променлив стъпка за пробиране, за да се намали клъстеризацията.

Това осигурява ефективен достъп, вмъкване и изтриване на елементи.