4 - Colisiones en tablas hash

Por qué ocurren

Las tablas hash se apoyan en funciones que comprimen un dominio de claves potencialmente infinito en un conjunto finito de buckets. Cuando dos claves distintas producen el mismo índice, ocurre una colisión. Saber prevenirlas y resolverlas es esencial para mantener el tiempo promedio O(1).

4.1 Qué es una colisión

Ocurre cuando dos claves distintas producen el mismo valor hash y, al aplicar el módulo del tamaño de la tabla, terminan en el mismo bucket. Ninguna función hash general puede garantizar ausencia de colisiones porque el espacio de claves suele ser mucho más grande que la cantidad de buckets.

Ejemplo rápido: con una tabla de 8 buckets y la función hash(x) = x % 8, las claves 10 y 18 devuelven 2, por lo que intentan ocupar el mismo bucket 2.

4.2 Por qué son inevitables

• Principio del palomar: si hay más claves posibles que casillas (buckets), alguna casilla recibirá al menos dos claves.
• Dominio amplio: claves como cadenas o enteros de 32 bits superan ampliamente el tamaño usual de una tabla.
• Dispersión imperfecta: incluso funciones hash buenas pueden agrupar valores cuando el dominio tiene patrones fuertes.

Aún con una función de calidad, la cantidad de inserciones puede crecer hasta saturar la tabla y forzar colisiones; de ahí la importancia de monitorear el factor de carga y planificar rehashing.

4.3 Tipos de estrategias para resolver colisiones

Existen dos familias principales de resolución de colisiones:

• Encadenamiento (separate chaining): cada bucket almacena una lista (o vector) de pares clave-valor. Al llegar una colisión se agrega un nodo a la lista del bucket. Busca en O(k) donde k es la longitud de la lista.
• Open addressing (direccionamiento abierto): si un bucket está ocupado, se busca otra posición en el mismo array siguiendo una secuencia (probing, la exploración ordenada de celdas vacías), ya sea lineal, cuadrática o con doble hashing. Evita estructuras auxiliares pero necesita marcar celdas libres y borradas.

Reglas prácticas:

• Chaining: sencillo de implementar y robusto ante borrados frecuentes; depende de un buen manejo de memoria para las listas.
• Open addressing: mejor localidad de cache, pero sensible al clustering y requiere factor de carga más bajo (por ejemplo, rehash al pasar 0.7).

En ambos casos es clave mantener la función hash estable mientras la tabla esté en uso; cambiarla sin reinsertar puede volver inaccesibles los elementos guardados.

4.4 Comparación entre estrategias

Criterio	Encadenamiento	Open addressing
Memoria	Usa nodos extra por colisión	Todo vive en el array
Rehashing	Reinsertar nodos; costo O(n)	Reinsertar entradas; costo O(n)
Cache locality	Peor (punteros dispersos)	Mejor (array contiguo)
Borrado	Eliminar nodo en la lista del bucket	Marcar celda como borrada; afecta el probing
Complejidad promedio	O(1) con listas cortas (alpha bajo)	O(1) con probing corto (alpha bajo)
Escenarios típicos	Tablas con muchas eliminaciones o claves de tamaño variable	Tablas compactas y de lectura intensiva

Ambas estrategias funcionan bien con factores de carga moderados. Chaining se vuelve costoso si las listas crecen; open addressing sufre clustering si el probing recorre secuencias largas. Elegir una u otra depende del perfil de inserción/borrado, memoria disponible y patrones de acceso.