Una tabla hash encuentra una clave sin buscar
Una tabla hash es una estructura de datos que guarda parejas de clave y valor y encuentra una clave casi al instante. Es lo que hay detrás de un diccionario de Python, y de muchas búsquedas en bases de datos y cachés.
Piensa en el fichero de una biblioteca: no lees todas las fichas, vas al cajón que corresponde a la letra.
Al final de esta lección
Nota
Puedo explicar cómo una tabla hash encuentra una clave rápidamente.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Clave y valor | el nombre con que se busca y el dato que se guarda | "ana": 8 |
| Función hash | una cuenta que convierte una clave en un número | |
| Cajón | una posición de la tabla, que guarda cero, una o varias parejas | |
| Colisión | cuando dos claves distintas dan el mismo cajón | |
| Encadenamiento | guardar en cada cajón una lista de las parejas que chocan |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La función hash convierte la clave en número
Buscar una clave en una lista obliga a mirar los elementos uno por uno. Una tabla hash evita eso: calcula un número a partir de la clave y va directa a esa posición.
La función hash de abajo suma los códigos de las letras y toma el resto de dividir por el tamaño de la tabla. Siempre da el mismo cajón para la misma clave.
Calcular el cajón de cuatro claves
# Una función hash didáctica: suma los códigos de las letras.
def hash_of(key, size):
total = 0
for letter in key:
total = total + ord(letter)
return total % size
for name in ["ana", "luis", "marta", "pablo"]:
print(name, "va al cajón", hash_of(name, 7))
# Cambia 7 por 11: ¿siguen chocando marta y pablo?
Cajón de cada clave con tamaño 7
| Clave | Suma de letras | Resto de dividir por 7 |
|---|---|---|
| ana | 304 | 3 |
| luis | 445 | 4 |
| marta | 533 | 1 |
| pablo | 526 | 1 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una función hash real
python3 -c "import hashlib; print(hashlib.sha256(b'ana').hexdigest()[:8])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un cambio de una letra
python3 -c "import hashlib; print(hashlib.sha256(b'anb').hexdigest()[:8])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que una función hash da un número al azar cada vez. No es así. La misma clave da siempre el mismo número, o no se podría volver a encontrar. Lo que se parece al azar es el reparto de claves distintas.
Dos claves distintas pueden compartir cajón
La tabla tiene pocos cajones y puede haber muchas claves, así que a veces dos claves dan el mismo número. Es una colisión. En la tabla de arriba, marta y pablo chocan en el cajón 1.
No es un fallo: es normal y hay que tratarla. La forma más sencilla es el encadenamiento: cada cajón guarda una lista con todas las parejas que le tocan.
Cajones con listas de claves
size = 7
table = []
for i in range(size):
table.append([]) # un cajón vacío por posición
def hash_of(key, size):
total = 0
for letter in key:
total = total + ord(letter)
return total % size
for name in ["ana", "marta", "pablo"]:
table[hash_of(name, size)].append(name)
print(table)
# Busca "pablo": solo hay que mirar el cajón 1.
print("pablo" in table[hash_of("pablo", size)])
Buscar es calcular el cajón y mirarlo
Para buscar una clave se calcula su cajón y se compara solo con las claves de ese cajón. Si hay pocas colisiones, la lista es de uno o dos elementos y la búsqueda cuesta casi un paso.
Si la tabla se llena demasiado, los cajones tienen listas largas y la búsqueda se vuelve lenta. Por eso las tablas reales crecen y reparten las claves en más cajones.
Para ir más lejos
Cuenta cuántas claves tiene cada cajón al guardar diez nombres con tamaño 7 y con tamaño 31. ¿Con cuál son más cortas las listas?
Después piensa por qué una función que devuelve siempre 0 sería correcta pero inútil.