Quais métodos você usa para lidar com colisões em tabelas de hash?

Nas tabelas de hash para lidar com colisões, geralmente utilizam-se dois métodos principais:

1. Encadeamento (Chaining) — quando ocorre uma colisão, todos os elementos com o mesmo hash são armazenados numa lista ligada ou outro contêiner numa mesma célula do array. Ao procurar ou inserir, percorre-se essa lista.

2. Endereçamento aberto (Open Addressing) — em caso de colisão, procura-se a próxima célula livre de acordo com uma sequência definida (sondagem linear, sondagem quadrática, duplo hashing).

Em Go, a implementação padrão de map usa o método de encadeamento com otimizações. Por exemplo, em caso de colisão, os elementos são armazenados em listas ligadas dentro dos buckets.

Exemplo de encadeamento (simplificado):

// Estrutura para um elemento
type entry struct {
    key string
    value int
    next *entry
}

// Inserção com encadeamento
func insert(table []*entry, key string, value int) {
    index := hash(key) % len(table)
    e := &entry{key: key, value: value, next: table[index]}
    table[index] = e
}

Assim, o tratamento de colisões é uma forma de manter a correção e eficiência do funcionamento da tabela de hash em caso de colisões de hashes.