¿Qué métodos existen para reducir la probabilidad de colisiones al usar tablas hash?

Para reducir la probabilidad de colisiones en las tablas hash se utilizan los siguientes métodos:

• Elegir una buena función hash — la función debe distribuir uniformemente las claves en la tabla.
• Uso de métodos para resolver colisiones:
  • Dirección abierta (sondeo lineal, sondeo cuadrático, doble hashing) — búsqueda de la siguiente celda libre.
  • Encadenamiento — almacenar todos los elementos con el mismo hash en una lista enlazada u otro contenedor.
• Aumentar el tamaño de la tabla — cuando se alcanza cierta carga, se realiza un rehash con un tamaño mayor.

Ejemplo de encadenamiento en C++:

std::unordered_map<int, std::string> map;
map[1] = "one";
map[2] = "two";
// Internamente se usa encadenamiento para colisiones