O que é uma colisão de hash e quais métodos existem para resolvê-la?

Uma colisão de hash ocorre quando dois valores de entrada diferentes produzem o mesmo valor de função hash. Isso é inevitável, pois o conjunto de entradas possíveis geralmente é maior que o conjunto de valores hash possíveis.

Métodos para resolver colisões:

1. Endereçamento aberto — em caso de colisão, procura-se a próxima célula livre em uma sequência definida (sondagem linear, quadrática, duplo hashing).
2. Encadeamento — cada célula da tabela hash armazena uma lista ligada de todos os elementos com o mesmo valor hash.
3. Rehashing — em caso de colisão, aplica-se outra função hash.

Exemplo com encadeamento em Python:

tabela_hash = [[] for _ in range(10)]

def inserir(chave, valor):
    indice = hash(chave) % 10
    tabela_hash[indice].append((chave, valor))

inserir('maçã', 1)
inserir('pama', 2)  # possível colisão