Tabla hash — cómo funciona el hashing y la resolución de colisiones

Una tabla hash almacena pares clave-valor aplicando una función hash a cada clave para convertirla en un índice de un arreglo. Eso permite que la tabla salte cerca de la ubicación correcta en lugar de recorrer uno por uno todos los elementos almacenados.

Por eso las tablas hash suelen estar cerca de $O(1)$ para búsqueda, inserción y eliminación en promedio. La condición importa: la función hash debe distribuir las claves razonablemente bien, y la tabla aún necesita una regla para manejar colisiones.

Qué hace una tabla hash

Una tabla hash almacena pares clave-valor como "name" -> "Ada" o 42 -> "blue". Tiene dos partes principales:

• un arreglo de posiciones o cubetas
• una función hash que asigna cada clave a una de esas posiciones

Si el arreglo tiene $m$ posiciones, puedes pensar en la función hash como algo que produce un índice de $0$ a $m-1$.

Para un ejemplo pequeño con enteros, la regla podría ser

$$h(k) = k \bmod 8$$

Entonces la clave $10$ va a la posición $2$ porque $10 \bmod 8 = 2$.

Las funciones hash reales se diseñan con más cuidado, especialmente para cadenas y conjuntos de datos más grandes. Pero la idea central sigue siendo la misma: calcular un índice rápidamente y luego revisar el elemento almacenado allí.

Por qué las colisiones hash son inevitables

Una colisión ocurre cuando dos claves distintas se asignan a la misma posición.

Eso es normal porque la tabla suele tener menos posiciones que la cantidad de claves posibles. Con

$$h(k) = k \bmod 8$$

las claves $10$, $18$ y $26$ se asignan todas a la posición $2$. Así que, aunque la función esté funcionando exactamente como fue definida, la tabla igual tiene un conflicto que resolver.

Por lo tanto, una tabla hash no promete una posición única para cada clave. Promete una forma rápida de acotar la búsqueda, siempre que las colisiones se manejen bien.

Ejemplo resuelto: una tabla, una colisión

Supón que una tabla tiene $8$ posiciones y usa

$$h(k) = k \bmod 8$$

Inserta las claves $10$, $18$ y $7$.

Primero, $10$ va a la posición $2$ porque $10 \bmod 8 = 2$.

Después, $18$ también se asigna a la posición $2$, así que ocurre una colisión.

Luego, $7$ va a la posición $7$, así que esa inserción no colisiona.

El patrón útil es siempre el mismo:

1. Aplica hash a la clave.
2. Ve a la posición sugerida.
3. Si ya hay allí una clave diferente, aplica la regla de colisión.

Una vez que ese patrón queda claro, las dos estrategias principales para colisiones son más fáciles de entender.

Encadenamiento vs. direccionamiento abierto

El encadenamiento mantiene una cubeta en cada posición

En el encadenamiento, cada posición almacena una pequeña colección de entradas en lugar de solo una.

Si $10$ y $18$ se asignan ambos a la posición $2$, la cubeta $2$ podría almacenar

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Para encontrar la clave $18$, la tabla salta a la cubeta $2$ y compara solo las entradas de esa cubeta.

El encadenamiento es conceptualmente simple, y la eliminación suele ser más fácil que en el direccionamiento abierto. La desventaja es que las cubetas largas hacen que las operaciones sean más lentas.

El direccionamiento abierto se mantiene dentro del arreglo

En el direccionamiento abierto, cada posición del arreglo contiene como máximo una entrada. Si la posición inicial está ocupada, la tabla prueba otras posiciones según una regla fija.

Una regla común es el sondeo lineal: si la posición $2$ está ocupada, prueba la $3$, luego la $4$, luego la $5$, volviendo al inicio si hace falta.

Esto evita listas de cubetas separadas, pero las posiciones ocupadas cercanas pueden acumularse en grupos. Otro detalle es que la búsqueda y la eliminación deben respetar la misma regla de sondeo usada durante la inserción.

Cuándo $O(1)$ es una afirmación razonable

Las tablas hash suelen describirse como estructuras con búsqueda, inserción y eliminación en $O(1)$ en promedio. Esa afirmación sobre el caso promedio depende de ciertas condiciones:

• la función hash distribuye las claves razonablemente bien
• el factor de carga se mantiene bajo control
• la estrategia de colisiones está implementada correctamente

El factor de carga es la razón

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Si la tabla se llena demasiado, las colisiones se vuelven más frecuentes y el rendimiento empeora. Por eso muchas implementaciones redimensionan el arreglo a medida que se llena.

El rendimiento en el peor caso aún puede degradarse hacia $O(n)$ si demasiadas claves se acumulan en la misma zona.

Errores comunes con las tablas hash

Suponer que las colisiones significan que la función hash falló

No es así. Las colisiones son esperadas. La verdadera pregunta es si la tabla las maneja de forma eficiente.

Tratar $O(1)$ como si fuera incondicional

$O(1)$ suele ser una afirmación sobre el caso promedio, no una promesa para toda entrada y en todo momento.

Confundir este hashing con el cifrado

Una función hash en el contexto básico de estructuras de datos trata principalmente de indexación rápida, no de secreto. Son objetivos distintos.

Olvidar comparar la clave real

Dos claves pueden compartir el mismo resultado hash. Después de llegar a la cubeta correcta o a la posición de sondeo, la tabla todavía tiene que comprobar si la clave realmente coincide.

Cuándo se usan las tablas hash

Las tablas hash se usan siempre que importa una búsqueda rápida basada en claves. Algunos ejemplos comunes incluyen diccionarios, tablas de símbolos, cachés, indexación y conteo de frecuencias en datos.

Son una muy buena opción cuando la búsqueda exacta por clave es más importante que mantener los elementos en orden. Si necesitas recorrido ordenado, consultas por rango o valores más cercanos, puede ser mejor otra estructura.

Prueba un ejemplo similar de colisiones

Toma un arreglo pequeño con $8$ posiciones y usa $h(k)=k \bmod 8$. Inserta algunas claves como $3$, $11$, $19$ y $27$. Luego resuelve las colisiones una vez con encadenamiento y otra con sondeo lineal.

Ese único ejercicio vuelve concreta la idea principal muy rápido: las colisiones son inevitables, y la regla de colisión cambia cómo se comporta la tabla. Si quieres un siguiente paso útil, prueba tu propia versión con un tamaño de tabla distinto y observa cómo cambian las colisiones.