Tablas hash en la práctica: colisiones, factor de carga y hashing con semilla

Qué es

Una tabla hash asigna una clave a un índice de cubo calculando hash(key) mod capacity. Dos claves que caen en el mismo cubo colisionan; la tabla resuelve esto mediante encadenamiento (una lista pequeña por cubo) o mediante direccionamiento abierto (sondeando otras posiciones). El factor de carga es el número de entradas dividido entre la capacidad. La documentación de HashMap de Java describe el factor de carga como la medida de lo llena que puede llegar a estar la tabla antes de que se aumente su capacidad, con un valor predeterminado de 0,75; cuando las entradas superan el factor de carga multiplicado por la capacidad, la tabla se rehashea, lo que toca cada entrada. El modelo de datos de Python indica que los valores hash de str y bytes se salan con un valor impredecible por proceso (aleatorización del hash, activada por defecto desde la 3.3), y la especificación de Go indica que el orden de iteración sobre los mapas no está especificado.

Por qué importa

Las búsquedas en O(1) en promedio dependen de que las claves se distribuyan de forma uniforme. Un atacante que pueda elegir las claves (nombres de parámetros de consulta, nombres de campos JSON, campos de formulario) y conozca la función hash puede hacer que miles de claves colisionen, convirtiendo cada inserción en un recorrido lineal y una sola solicitud en trabajo cuadrático; esto es la inundación de hash (hash flooding), y la siembra por proceso es la defensa estándar. El rehashing es O(n) y ocurre en umbrales, así que un bucle que inserta n elementos paga por varias rondas de rehashing: el coste amortizado sigue siendo O(1), pero las inserciones individuales presentan picos.

Cómo aplicarlo

• Nunca persistir, transmitir ni comparar entre procesos ningún valor hash a nivel de lenguaje; cambia con la semilla, la versión y la compilación. Ordenar la salida que deba ser estable en lugar de depender del orden del mapa.
• Predimensionar cuando se conoce el recuento (HashMap(initialCapacity), make(map[K]V, n)) para evitar rondas de rehashing en bucles críticos.
• Las claves no deben cambiar mientras están en la tabla; mutar una clave tras insertarla hace que la entrada quede inencontrable. Los objetos iguales deben tener el mismo hash: definir la igualdad y el hash juntos.
• Al implementar una tabla (código embebido, asignador de memoria personalizado): usar un hash con buen efecto avalancha, sembrarlo por proceso, limitar el factor de carga, y probar la cadena de sondeo más larga con claves adversarias.
• Para pruebas reproducibles, fijar la semilla de forma explícita (PYTHONHASHSEED) en lugar de depender del azar, y ejecutar también la batería de pruebas con una semilla aleatoria.

Trampas

Una prueba que pasa con una semilla y falla con otra revela una dependencia del orden en el código, no una prueba inestable. Claves de coma flotante: 0.0 y -0.0 se comparan como iguales y deben tener el mismo hash; NaN no es igual a sí mismo. Una tabla usada como caché sin límite de tamaño es una fuga de memoria. Los resúmenes criptográficos como SHA-256 son innecesarios para tablas y lentos; las funciones hash con clave rápidas diseñadas para tablas son la norma.