Complejidad de Inserción y Búsqueda en Hashing con Tamaño de Tabla Inicial Variable

Resumen

El desempeño de diferentes estrategias para resolver colisiones en tablas hash sondeo lineal, sondeo cuadrático y listas enlazadas fue evaluado, junto con tres funciones hash no criptográficas de alto rendimiento: Fowler-Noll-Vo versión 1a de 32 y 64 bits, y xxHash de 64 bits, bajo criterios de eficiencia temporal y consumo de memoria. La metodología adoptó un enfoque aplicado y experimental que consideró múltiples configuraciones, variando tamaños de tabla y cargas de trabajo, para simular escenarios reales y complejos. Tras superar las fases iniciales de redimensionamiento, que causan picos temporales disruptivos, tanto el direccionamiento abierto como las listas enlazadas lograron niveles estables y comparables de rendimiento en inserción y búsqueda. Se resalta que las listas enlazadas, debido a la gestión de referencias adicionales, presentan un consumo de memoria ligeramente mayor, mientras que el direccionamiento abierto mantiene una mayor eficiencia espacial. En cuanto a las funciones hash, xxHash-64 requiere más tiempo de procesamiento, pero proporciona excelente dispersión de claves, reduciendo colisiones. Estas técnicas son viables y su elección debe basarse en un equilibrio estratégico entre velocidad, uso de memoria y estabilidad, alineándose con las prioridades y restricciones específicas de cada aplicación para optimizar el rendimiento en entornos dinámicos y exigentes.