Qué es un hash

La etiqueta decide el número de casilla

En la lección anterior, para encontrar un valor en una fila había que recorrerla una a una o usar un índice ordenado. Pero ¿y si pudieras decidir el número de casilla a partir del propio valor, como cuando eliges una casilla por las letras de un nombre?
Se trata de fijar un pequeño cálculo que convierte un valor en un número de casilla. Ese cálculo se llama función hash. El diccionario de la primera lección, si miras por dentro, también funciona así.

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

Cada valor recibió su casilla al instante. No hace falta pensar dónde ponerlo, porque el cálculo te dice el lugar.
Si vuelves a meter el mismo valor, el cálculo siempre da la misma casilla, así que los lugares no cambian de un momento a otro. Entonces, ¿no se podría usar el mismo cálculo también para buscar?

Calcular e ir directo a la casilla

Para buscar, el secreto es el mismo. Pasas el valor que buscas por el mismo cálculo para obtener su número de casilla y vas directo a ella. No hace falta recorrer las casillas una por una.
Como el cálculo que usaste al guardar y el que usas al buscar son el mismo, la casilla donde lo guardaste y la casilla donde miras coinciden exactamente. Por eso llegas de una vez.

Toca un valor que buscar. El mismo cálculo da el número de casilla y saltas directo a ella sin recorrer nada.

Llegaste directo, sin recorrer nada. Haya cien casillas o diez mil, el esfuerzo es casi el mismo, porque basta con un cálculo y un salto.
Por eso el hash es rápido. Donde un índice ordenado necesitaba unas veinte miradas, el hash suele terminar en una. Pero hay un detalle. ¿Qué pasa si dos valores distintos dan el mismo resultado?

Dos valores van a la misma casilla

El cálculo siempre da la misma casilla para el mismo valor, pero valores distintos no siempre reciben casillas distintas. El número de casillas es fijo, mientras que puede haber muchísimos más valores.
Así que a veces dos valores distintos reciben por casualidad la misma casilla, y los dos intentan entrar en ella. Que dos valores choquen así por la misma casilla se llama colisión.

Toca los dos valores por turno. Sus resultados son iguales, así que los dos van a la misma casilla y chocan.

Los dos valores chocaron por la misma casilla. Normalmente una casilla guarda un solo valor, así que dos a la vez son un problema.
Pero eso no es motivo para abandonar el hash. Con un cálculo bien elegido, las colisiones son raras, y todo lo demás sigue siendo rápido y se hace de una vez. Así que basta con atender aparte las colisiones cuando ocurren. Veamos cómo.

Las colisiones se resuelven aparte

Hay dos maneras principales de resolver una colisión. Una es guardar varios valores juntos en una casilla: cada casilla tiene una pequeña lista y los valores que chocaron entran en ella uno al lado de otro.
La otra es pasar el valor a una casilla vecina: si la casilla original está ocupada, buscas la siguiente casilla libre y lo pones allí. De cualquiera de las dos maneras, ningún valor se pierde y luego puedes volver a encontrarlo.

Elige un método y tócalo. Resuelve la colisión juntando los dos en una casilla o pasando uno a la casilla vecina.

La colisión se resolvió limpiamente. Ya sea juntos o en la casilla vecina, cada valor encontró su lugar con seguridad.
Si al buscar sigues la misma regla, también encuentras los valores que chocaron. Pero cuando las casillas están casi llenas, las colisiones se vuelven frecuentes, así que antes de que se llenen se aumentan las casillas y se vuelve a colocar todo. Las colisiones son ocasionales y fáciles de resolver, así que el hash sigue siendo rápido y fiable.

En resumen

En pocas palabras: el hash decide un número de casilla con un cálculo sobre el valor. Al guardar, metes el valor en esa casilla; al buscar, el mismo cálculo te lleva a ella. Así llegas de una vez sin recorrer nada.
Cuando de vez en cuando ocurre una colisión, porque valores distintos van a la misma casilla, se resuelve aparte: juntándolos en una casilla o pasando uno a la vecina. Encontrar las cosas directamente con un cálculo: eso es el hash.

Toca en orden los puntos clave 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 ya sabes cómo encontrar un valor directamente con un cálculo. La frustración de recorrer lugares se resolvió con un solo cálculo.
Pero hay cosas que el hash no puede hacer. Como las casillas están repartidas sin relación con el tamaño de los valores, no sirve para buscar por rangos, como todo lo que va de la A a la C, ni para listar las cosas en orden. La próxima lección presenta un recipiente que encuentra rápido sin perder el orden: el árbol.