10 - Comparacion entre encadenamiento y open addressing

Como elegir la estrategia

Encadenamiento y direccionamiento abierto resuelven colisiones de manera diferente. La eleccion depende del perfil de inserciones, borrados, uso de memoria y tolerancia al peor caso.

10.1 Rendimiento promedio

• Encadenamiento: O(1) amortizado si alpha se mantiene cercano a 1; el costo real se acota por la longitud media de las listas.
• Open addressing: O(1) amortizado con alpha bajo (0.6-0.75) y una funcion de probing adecuada; excelente localidad de cache en lecturas.
• Observacion: las lecturas repetidas en los mismos buckets benefician mas a open addressing; las escrituras con muchas colisiones penalizan ambos.

10.2 Peor caso posible

• Encadenamiento: O(n) si todas las claves caen en un bucket (lista completa) o si alpha se dispara sin rehash.
• Open addressing: O(n) si el probing recorre gran parte de la tabla por clustering; sondas largas afectan tanto busqueda como insercion y borrado.
• Mitigacion: elegir buena funcion hash y rehash preventivo antes de llegar a este escenario.

10.3 Uso de memoria

• Encadenamiento: requiere nodos por colision; suma punteros y posibles fragmentaciones, pero puede almacenar muchos elementos sin crecer el array de buckets.
• Open addressing: todo vive en el array; sin overhead por nodo, pero necesita mantener celdas marcadas (vacia/borrada/ocupada) y rehash mas frecuente.
• Clave grande: si las claves son cadenas largas copiadas, ambas estrategias cargan mas memoria; en ese caso conviene guardar punteros compartidos.

10.4 Implementacion

• Encadenamiento: logica directa; borrado simple ajustando punteros; exige gestionar malloc/free y posibles fugas.
• Open addressing: requiere estados de celda y una politica de probing (lineal, cuadratico, doble hashing); los borrados marcan celdas y necesitan rehash eventual para compactar.
• Testing: open addressing demanda pruebas de sondas y rehash; encadenamiento debe validar liberacion correcta y manejo de claves duplicadas.

10.5 Rendimiento con diferentes load factors

• Encadenamiento: tolera alpha cercano o superior a 1.0 con listas cortas; rehash recomendado cuando las listas empiezan a crecer perceptiblemente.
• Open addressing: sensible; rehash en 0.65-0.75 mantiene sondas cortas. Por encima de 0.8 el rendimiento suele degradar rapido.
• Rehash: en open addressing implica reinsercion de todos los elementos; en encadenamiento, opcional pero mejora la dispersion y acorta listas.

10.6 Tabla comparativa

Criterio	Encadenamiento	Open addressing
Complejidad promedio	O(1) con listas cortas (alpha ≈ 1)	O(1) con alpha < 0.75 y buen probing
Memoria	Overhead de nodos/punteros	Array contiguo, sin nodos extra
Borrados	Eliminar nodo de la lista	Marcar borrada y mantener cadena de sondas
Rehash	Menos frecuente; tolera alpha alto	Mas frecuente; umbral bajo
Localidad de cache	Baja (punteros dispersos)	Alta (array contiguo)
Peor caso	Lista larga en un bucket (O(n))	Sonda larga hasta cubrir la tabla (O(n))

10.7 Ejemplos de uso real

• Compiladores/intérpretes: los diccionarios de símbolos priorizan lecturas rápidas y buena locality; open addressing con doble hashing es común mientras el alpha se mantiene bajo.
• Mapas concurrentes sencillos: encadenamiento permite locks por bucket y borrados frecuentes sin romper sondas ni requerir rehash inmediato.
• Routers o tablas de rutas embebidas: open addressing reduce saltos de puntero y ofrece lecturas predecibles bajo carga moderada, ideal con capacidad fija y alpha controlado.
• Servicios con alto churn (altas/bajas constantes): encadenamiento evita celdas borradas y simplifica la reutilización de espacio, reduciendo el costo de mantenimiento.
• Tablas de configuración estáticas: open addressing con alpha muy bajo (0.3–0.5) y sin rehash brinda el máximo rendimiento en setups de solo lectura o pocos cambios.