O que é uma colisão? Como ela era resolvida no mapa antigo e como no novo?

Uma colisão no contexto de tabelas de hash é uma situação em que duas chaves diferentes têm o mesmo valor de hash e tentam ocupar a mesma célula no array.

Na implementação antiga de map em Go, as colisões eram resolvidas usando listas ligadas (encadeamento). Quando ocorria uma colisão, os novos elementos eram adicionados à lista ligada associada à célula do array.

Na nova implementação (a partir do Go 1.8), é utilizado um mecanismo mais complexo: em vez de uma lista ligada simples, emprega-se uma estrutura de arrays com endereçamento aberto e otimizações adicionais, como o uso de múltiplas funções de hash e a transição para árvores em caso de muitas colisões, o que melhora o desempenho e reduz a probabilidade de degradação para O(n).

Exemplo simplificado:

// mapa antigo: bucket -> lista ligada
// mapa novo: bucket -> array + otimizações