Hashing: una etiqueta que halla la casilla

La etiqueta decide el número de casilla

Antes aprendimos que los valores
están en fila por números de casilla.
Para hallar uno había que recorrer casilla a casilla.
¿Y si miramos el valor mismo
y decidimos su casilla a partir de él?
Como elegir casilla por las letras de un nombre.
Ponemos un pequeño cálculo
que toma un valor y da un número de casilla.
A ese cálculo lo llamamos función hash.

Toca un valor. El cálculo decide su número de casilla y cae en esa casilla.

Cada valor tuvo su casilla enseguida.
No hay que pensar dónde ponerlo.
El cálculo dice el sitio.
Mete el mismo valor otra vez
y el resultado es siempre la misma casilla.
Así las casillas no andan sueltas.
Entonces para buscar también,
¿no podemos usar el mismo cálculo?

Calcula y salta directo a la casilla

Al buscar, el secreto es el mismo.
Mete el valor buscado en el mismo cálculo,
obtén el número de casilla,
y ve directo a esa casilla.
No hace falta recorrer casilla a casilla.
El cálculo usado para meter
y el usado para buscar son el mismo,
así la casilla guardada coincide con la buscada.
Así llegas en un paso.

Toca un valor a buscar. El mismo cálculo da el número de casilla y salta allí sin recorrer.

Llegó de una, sin recorrer.
Ya sean cien casillas o diez mil,
el esfuerzo se mantiene parecido.
Un cálculo, un salto, y listo.
Por eso hashing es rápido.
Pero algo inquieta.
¿Qué pasa si dos valores distintos
dan el mismo resultado al calcular?

Dos van a la misma casilla

El cálculo siempre nombra una casilla,
pero valores distintos no implican casillas distintas.
Dos valores diferentes
pueden dar por casualidad el mismo resultado.
Entonces ambos van a la misma casilla.
Dos quieren una sola casilla.
Este choque por la misma casilla
se llama colisión.
Las colisiones son raras pero ocurren.

Toca los dos valores por turno. Dan el mismo resultado, así que ambos van a la misma casilla y colisionan.

Dos chocaron por la misma casilla.
Una casilla suele guardar solo uno,
así que dos a la vez es un problema.
Aun así no podemos dejar hashing.
Una colisión es de vez en cuando,
y el resto sigue siendo rápido en un paso.
Así que solo cuando hay colisión
lo resolvemos un poco aparte.
¿Vemos cómo se resuelve?

Las colisiones se resuelven aparte

Hay dos caminos principales para resolver una colisión.
Uno es juntar dos en una casilla.
Guarda un pequeño grupo en la casilla
y coloca allí los valores chocados, lado a lado.
El otro es empujar a una casilla vecina.
Si la casilla original está llena,
busca una vecina vacía y ponlo ahí.
De cualquier modo no se pierde ningún valor
y se puede hallar otra vez después.

Elige y toca un método. Junta en una casilla, o empuja a la vecina para resolver la colisión.

La colisión se resolvió limpiamente.
Ya sea juntada o empujada a la vecina,
el valor quedó a salvo en un sitio.
Al buscar, sigue la misma regla
y hasta un valor chocado se halla bien.
Las colisiones son ocasionales y el manejo simple,
así que hashing sigue rápido y fiable.
Ahora resumamos todo.

Resumamos

Reunido en una línea, es esto.
Mira el valor, calcula el número de casilla.
Al meter, ponlo en esa casilla;
al buscar, el mismo cálculo va a esa casilla.
Así llega en un paso sin recorrer.
De vez en cuando hay una colisión
cuando otro valor va a la misma casilla, y la resolvemos aparte.
Júntalos, o empuja a la casilla vecina.
Hallar de una por cálculo, eso es hashing.

Toca los puntos clave en orden para repasar. (decide la casilla por cálculo -> halla de una con el mismo cálculo -> colisión en la misma casilla -> resuelve las colisiones aparte)

Ahora conoces una forma lista
de hallar un valor de una por cálculo.
El agobio de recorrer casillas
se despejó con un solo cálculo.
Mañas como esta, que aceleran meter y hallar,
son la fuerza de manejar datos.
La próxima, ¿con qué otra forma
podemos guardar y hallar valores aún mejor?
Sigamos explorando juntos.