4 - Colisiones en tablas hash

Por que 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 indice, ocurre una colision. Saber prevenirlas y resolverlas es esencial para mantener el tiempo promedio O(1).

4.1 Que es una colision

Ocurre cuando dos claves distintas producen el mismo valor hash y, al aplicar el modulo del tamano de la tabla, terminan en el mismo bucket. Ninguna funcion hash general puede garantizar ausencia de colisiones porque el espacio de claves suele ser mucho mas grande que la cantidad de buckets.

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

4.2 Por que son inevitables

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

Aun con una funcion de calidad, la cantidad de inserciones puede crecer hasta saturar la tabla y forzar colisiones; de ahi la importancia de monitorear el factor de carga y planificar rehashing.

4.3 Tipos de estrategias para resolver colisiones

Existen dos familias principales de resolucion de colisiones:

• Encadenamiento (separate chaining): cada bucket almacena una lista (o vector) de pares clave-valor. Al llegar una colision 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 esta ocupado, se busca otra posicion en el mismo array siguiendo una secuencia (probing, la exploracion ordenada de celdas vacias), ya sea lineal, cuadratica o con doble hashing. Evita estructuras auxiliares pero necesita marcar celdas libres y borradas.

Reglas practicas:

• 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 mas bajo (por ejemplo, rehash al pasar 0.7).

En ambos casos es clave mantener la funcion hash estable mientras la tabla este en uso; cambiarla sin reinsertar puede volver inaccesibles los elementos guardados.

4.4 Comparacion entre estrategias

Criterio	Encadenamiento	Open addressing
Memoria	Usa nodos extra por colision	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 tipicos	Tablas con muchas eliminaciones o claves de tamano 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 insercion/borrado, memoria disponible y patrones de acceso.