Qual estrutura de dados está na base do dict em Python? Como são resolvidas as colisões?

No Python, dict é implementado com base numa tabela de dispersão com endereçamento aberto e usando o método de endereçamento aberto com hashing duplo (open addressing with probing).

Pontos principais:

• As chaves são hashadas para obter um índice na matriz.
• Quando ocorre uma colisão (quando duas chaves têm o mesmo índice), é utilizado o método de probing, onde a próxima célula livre é procurada de acordo com um algoritmo definido.
• A partir do Python 3.6+, é usada uma implementação ordenada do dicionário, que mantém a ordem de inserção.

Um exemplo de resolução de colisões é o probing linear ou o hashing duplo, mas no CPython é usado um algoritmo com passo variável para o probing, a fim de reduzir a aglomeração.

Isso garante acesso, inserção e remoção eficientes de elementos.