Quais métodos existem para reduzir a probabilidade de colisões ao usar tabelas hash?

Para reduzir a probabilidade de colisões em tabelas de hash, são utilizados os seguintes métodos:

• Escolha de uma boa função de hash — a função deve distribuir uniformemente as chaves na tabela.
• Uso de métodos de resolução de colisões:
  • Endereçamento aberto (sondagem linear, sondagem quadrática, hashing duplo) — procura pela próxima célula livre.
  • Encadeamento — armazenar todos os elementos com o mesmo hash numa lista ligada ou outro contêiner.
• Aumento do tamanho da tabela — ao atingir uma certa carga, realiza-se um rehash com um tamanho maior.

Exemplo de encadeamento em C++:

std::unordered_map<int, std::string> map;
map[1] = "one";
map[2] = "two";
// Usa encadeamento para colisões