Tabla hash

Código en:JavaC#PythonJavaScript

En resumen: Una tabla hash (dict en Python) encuentra una clave por su hash: el hash dice en qué lugar de la tabla mirar, así que buscar e insertar son O(1) en promedio.

Problema

El caché de precios se vuelve lento

La página del producto lee el precio de un caché: una tabla SKU → precio que el programa guarda en memoria. Alguien escribió su propia PriceTable, con una función hash que es «rápida»: solo la primera letra del SKU.

cache = PriceTable(lambda key: ord(key[0]))

Con 20 productos en la prueba todo vuela. Con el catálogo real la página va a paso de tortuga, y el profiler señala get. Con 1000 productos, cada uno escrito y leído una vez, la tabla hace 1.000.000 comparaciones de claves: mil por producto. Una tabla hash debería hacer una o dos.

Todos los SKU empiezan por «S». ¿Qué pasa por dentro?

La idea

Cubetas, hash y número de cubeta

En la lección «Códigos hash y funciones hash» viste la tabla desde fuera. Por dentro son tres cosas:

• un arreglo de cubetas;
• una función hash que convierte la clave en un entero;
• el número de cubeta = hash % número de cubetas. Así cada clave tiene exactamente un lugar donde se busca.

Dos claves con el mismo número de cubeta son una colisión. Aquí las colisiones viven en una cadena: cada cubeta es el comienzo de una lista enlazada de pares clave-valor.

keys = [1007, 2043, 3010, 4051]
buckets = 8
for key in keys:
    h = hash(key)
    index = h % buckets
    print(f"{key} -> {h} -> cubeta {index}")

Paso a paso, en palabras

1. Cuatro claves (números de pedido) y ocho cubetas vacías, numeradas del 0 al 7.
2. hash(1007) es el propio número, 1007. El resto de dividir entre 8 es 7: esa es la cubeta.
3. 2043 da la cubeta 3.
4. 3010 da la cubeta 2.
5. 4051 también cae en la cubeta 3: una colisión. Aquí se dibuja como una cadena, igual que en Java. Un dict de CPython, en cambio, busca otro lugar libre.
6. Se busca 4051: el mismo número, la misma cubeta 3. == con 2043: no. Con 4051: sí.

get calcula la cubeta y recorre solo su cadena. Si las cadenas son cortas, eso es O(1), sin importar cuántas claves haya.

Míralo

Tu propia tabla

La función hash de un SKU es la misma que el hashCode de un string en Java: 31 · h + char por cada carácter. Al final se quita el signo, para que el número no sea negativo:

def sku_hash(key):
    h = 0
    for c in key:
        h = (31 * h + ord(c)) & 0xFFFFFFFF
    return h & 0x7FFFFFFF

Un entero de Python no tiene límite superior, por eso & 0xFFFFFFFF lo mantiene en 32 bits en cada paso, como hace el desbordamiento en Java. Así el hash es el mismo que en los otros lenguajes.

Un par es un nodo con una clave, un precio y una flecha al siguiente de la cadena:

class Entry:
    def __init__(self, key, price, next_entry):
        self.key = key
        self.price = price
        self.next = next_entry

La tabla recibe su función hash desde fuera, para que puedas comparar dos. compares cuenta las comparaciones de claves:

class PriceTable:
    def __init__(self, hash_fn):
        self.hash = hash_fn
        self.buckets = [None] * 4
        self.size = 0
        self.compares = 0

    def index(self, key):
        return self.hash(key) % len(self.buckets)

    def put(self, key, price):
        i = self.index(key)
        e = self.buckets[i]
        while e is not None:
            self.compares += 1
            if e.key == key:
                e.price = price
                return
            e = e.next
        self.buckets[i] = Entry(key, price, self.buckets[i])
        self.size += 1
        if self.size > len(self.buckets) * 3 // 4:
            self.resize()

    def resize(self):
        fresh = [None] * (len(self.buckets) * 2)
        for head in self.buckets:
            e = head
            while e is not None:
                i = self.hash(e.key) % len(fresh)
                fresh[i] = Entry(e.key, e.price, fresh[i])
                e = e.next
        self.buckets = fresh

    def get(self, key):
        e = self.buckets[self.index(key)]
        while e is not None:
            self.compares += 1
            if e.key == key:
                return e.price
            e = e.next
        return None

• put recorre la cadena de la cubeta. Si la clave está ahí, cambia el precio. Si no, pone un par nuevo al principio de la cadena: eso no necesita recorrido.
• get recorre la misma cadena y se detiene en la clave.

Pruébalo

Completa

El número de cubeta:

return self.hash(key) % 

Comprobar

La idea

Factor de carga y crecimiento

Cuantos más pares, más largas las cadenas. La proporción pares / cubetas se llama factor de carga. Aquí, cuando pasa de 3/4, la tabla crea el doble de cubetas.

Las cubetas no se copian una a una. El número de cubeta es hash % número de cubetas, y ese número ha cambiado. Por eso resize recorre cada par y calcula su cubeta de nuevo: eso es rehash. Al duplicar de 4 a 8, una clave de la cubeta b va a b o a b + 4, y las cadenas se dividen.

def index(self, key):
    return self.hash(key) % len(self.buckets)

def put(self, key, price):
    i = self.index(key)
    e = self.buckets[i]
    while e is not None:
        self.compares += 1
        if e.key == key:
            e.price = price
            return
        e = e.next
    self.buckets[i] = Entry(key, price, self.buckets[i])
    self.size += 1
    if self.size > len(self.buckets) * 3 // 4:
        self.resize()

def resize(self):
    fresh = [None] * (len(self.buckets) * 2)
    for head in self.buckets:
        e = head
        while e is not None:
            i = self.hash(e.key) % len(fresh)
            fresh[i] = Entry(e.key, e.price, fresh[i])
            e = e.next
    self.buckets = fresh

Paso a paso, en palabras

1. Un caché de precios con 4 cubetas. La cubeta de una clave es su hash % 4.
2. SKU-1003: 1091696434 % 4 = 2. SKU-1001: % 4 = 0. Cubetas vacías: sin comparaciones.
3. SKU-1007 también cae en la cubeta 2: una colisión. put lo compara con SKU-1003 (no es la misma clave) y lo pone al principio de la cadena.
4. SKU-1005 se une a SKU-1001 en la cubeta 0. Ahora hay 4 pares, más de 3/4 de 4 cubetas: las cadenas empiezan a crecer.
5. resize crea 8 cubetas. Cada clave se calcula de nuevo con % 8: se queda en su número o sube 4.
6. La tabla nueva: cada cadena tiene un par, así que un get hace una comparación. Crecer cuesta n, pero ocurre pocas veces.

cache = PriceTable(sku_hash)
cache.put("SKU-1003", 24.9)
cache.put("SKU-1001", 12.5)
cache.put("SKU-1007", 8.99)
cache.print_buckets()
print("---")
cache.put("SKU-1005", 45.5)
cache.print_buckets()

Salida

0: SKU-1001
1:
2: SKU-1007 SKU-1003
3:
---
0: SKU-1001
1:
2: SKU-1003
3:
4: SKU-1005
5:
6: SKU-1007
7:

Crecer cuesta tanto como el número de pares. Pero ocurre pocas veces: con 4, 8, 16… pares, como el crecimiento del arreglo en Complejidad amortizada. En promedio put sigue siendo O(1).

Pruébalo

¿Cuántas cubetas?

La tabla empieza con 4 cubetas. Entran siete productos uno tras otro:

cache = PriceTable(sku_hash)
caps = []
for n in range(2001, 2008):
    cache.put(f"SKU-{n}", 10)
    caps.append(len(cache.buckets))
print(" ".join(str(c) for c in caps))

Respuesta

4 8 16 16 16 16 16

4 4 4 4 8 8 8

4 4 4 8 8 8 16

Comprobar

La idea

Un mal hash: la tabla se convierte en lista

Volvamos al caché. El hash «primera letra» da 83 (el código de «S») para todos los SKU. 83 % 4, 83 % 8, 83 % 1024: con cualquier número de cubetas el número es el mismo. Todos los pares están en una cadena, y la tabla es una lista enlazada donde cada put y cada get la recorren entera.

Crecer no ayuda: solo divide cadenas cuando las claves tienen hashes distintos. Una función hash debe depender de la clave entera y dispersar claves cercanas (SKU-10000, SKU-10001) lejos unas de otras.

def compares(cache, n):
    for i in range(n):
        cache.put(f"SKU-{10000 + i}", 1 + i)
    for i in range(n):
        cache.get(f"SKU-{10000 + i}")
    return cache.compares

print(f"primera letra: {compares(PriceTable(lambda key: ord(key[0])), 1000)}")
print(f"SKU completo: {compares(PriceTable(sku_hash), 1000)}")

Salida

primera letra: 1000000
SKU completo: 2593

Ejecuta las dos tablas en el navegador:

• Hash de todo el SKU O(n)
• Hash de la primera letra O(n²)

Algoritmo	n = 10	n = 1000	n = 100.000
Hash de todo el SKU	10	2593	211.990
Hash de la primera letra	100	1.000.000	≈ 10.000.000.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

Con 1000 productos el hash perezoso hace 1 000 000 de comparaciones, y el hash del SKU completo hace 2593: menos de tres por producto. El perezoso es O(n) por operación y O(n²) en total: n productos, cada uno escrito y leído una vez, hacen exactamente n² comparaciones.

Más precisamente, para curiosos

Direccionamiento abierto (linear probing). En vez de cadenas, cada par vive en el propio arreglo. Si el lugar hash % n está ocupado, pruebas el siguiente, luego el que sigue, hasta encontrar un lugar libre o la clave. get sigue el mismo camino y se detiene en un lugar vacío. La ventaja es que todo está en un solo arreglo y el procesador lo lee en orden. Las desventajas: los lugares ocupados se juntan en montones y cada montón crece cada vez más rápido, por eso la tabla debe estar más vacía (crece ya hacia la mitad o hacia 2/3). Al borrar no se puede simplemente vaciar el lugar, porque se cortaría el camino a las claves que vienen después: se deja una marca de «borrado».

Qué hacen los lenguajes:

• Java HashMap: cadenas. El número de cubetas es una potencia de 2 (al principio 16), el factor de carga es 0,75. Al hash se le mezclan los bits altos (h ^ (h >>> 16)), porque con una máscara de potencia de 2 solo contarían los bits bajos. Una cadena con más de 8 pares se convierte en un árbol rojo-negro si hay al menos 64 cubetas (si no, primero crece la tabla). Así, incluso con muchas colisiones, la búsqueda es O(log n) y no O(n).
• C# Dictionary<TKey, TValue>: también cadenas, pero en arreglos: _buckets guarda el número del primer par, y los pares en _entries tienen un índice next. El número de cubetas es un número primo (3, 7, 17, 37, 89…), y la tabla crece cuando el arreglo de pares se llena. No hay un árbol como en Java. Contra las colisiones provocadas ayuda que el hash de un texto es distinto en cada ejecución.
• Python dict: direccionamiento abierto, pero no con linear probing: el siguiente lugar se calcula con una fórmula en la que también entran los bits altos del hash. La tabla es una potencia de 2 y crece cuando está llena a más de 2/3. Los pares viven en un arreglo denso aparte en orden de inserción, y la tabla guarda solo índices hacia él. Por eso dict conserva el orden de inserción (garantizado desde Python 3.7).
• JavaScript Map: la especificación exige iterar en orden de inserción y búsquedas que en promedio sean mejores que lineales, pero no dice cómo. V8 usa una tabla hash ordenada: cubetas con cadenas, y los pares viven en un arreglo en orden de inserción. JavaScript no da un hash propio para los objetos: una clave que es un objeto se compara por referencia.

Pruébalo

Encuentra el error

Alguien reescribió resize. Los cuatro productos entran, pero dos de ellos después «desaparecen»:

def resize(self):
    fresh = [None] * (len(self.buckets) * 2)
    for head in self.buckets:
        e = head
        while e is not None:
            i = self.hash(e.key) % len(self.buckets)
            fresh[i] = Entry(e.key, e.price, fresh[i])
            e = e.next
    self.buckets = fresh

cache = PriceTable(sku_hash)
cache.put("SKU-1003", 24.9)
cache.put("SKU-1001", 12.5)
cache.put("SKU-1007", 8.99)
cache.put("SKU-1005", 45.5)
p = cache.get("SKU-1003")
print(f"SKU-1003: {'ninguno' if p is None else p}")
p = cache.get("SKU-1001")
print(f"SKU-1001: {'ninguno' if p is None else p}")
p = cache.get("SKU-1007")
print(f"SKU-1007: {'ninguno' if p is None else p}")
p = cache.get("SKU-1005")
print(f"SKU-1005: {'ninguno' if p is None else p}")

Salida

SKU-1003: 24.9
SKU-1001: 12.5
SKU-1007: ninguno
SKU-1005: ninguno

¿En qué línea está el error?

Elige la línea con el error.

1def resize(self):2 fresh = [None] * (len(self.buckets) * 2)3 for head in self.buckets:4 e = head5 while e is not None:6 i = self.hash(e.key) % len(self.buckets)7 fresh[i] = Entry(e.key, e.price, fresh[i])8 e = e.next9 self.buckets = fresh

Comprobar

Ejercicio

Un producto deja de venderse

Resuelve esta tarea en tu propio editor.

Borrar del caché. Añade a PriceTable un método remove(key) que quite el par y devuelva si había uno. Ten cuidado: el par puede ser el primero de la cadena (entonces la cubeta apunta al siguiente) o estar en medio (entonces el par anterior apunta al siguiente). Pon SKU-1001, SKU-1005, SKU-1009 y SKU-1012 con precios de 10,5, 11,5, 12,5 y 13,5 €; tras crecer a 8 cubetas tres de ellos están en la cubeta 0, y SKU-1009 está en medio de la cadena. Quita SKU-1009 y lee los cuatro:

Salida

SKU-1001: 10.5
SKU-1005: 11.5
SKU-1009: ninguno
SKU-1012: 13.5
productos: 3

Más tareas

• Linear probing. Escribe una ProbeTable sin cadenas: si un lugar está ocupado, prueba el siguiente. Crece cuando la tabla esté medio llena. ¿Cuántas comparaciones hace con 1000 SKU?
• Encoger. Tras una liquidación el caché se queda con 10 productos y 4096 cubetas. ¿Cuándo encogerías la tabla?
• Un hash perezoso mejor. El hash «suma de los códigos de los caracteres» mira la clave entera. Pruébalo con SKU-10000 hasta SKU-10999. ¿Por qué sigue habiendo muchas colisiones? (Pista: SKU-10019 y SKU-10091.)

Test

Ponte a prueba

1. La tabla tiene 8 cubetas. Una clave tiene el hash 1091696436. ¿En qué cubeta está?

Cubeta 4Cubeta 6Cubeta 0

2. ¿Por qué al crecer la tabla se calcula de nuevo cada clave, en vez de copiar las cubetas sin más?

No se calcula de nuevo: se copian las cubetasPorque el hash de la clave cambiaPorque el número de cubeta es hash % número de cubetas, y el número de cubetas ha cambiado

3. La función hash devuelve la primera letra del SKU, y todos los SKU empiezan por «S». ¿Cuánto cuesta get con n productos?

O(n): todos están en una cubeta y get recorre toda la cadenaO(log n)O(1): es una tabla hash

4. ¿Qué es verdad sobre el dict de Python?

Ordena las claves alfabéticamenteBusca otro lugar libre en el mismo arreglo (direccionamiento abierto) y conserva el orden de inserciónGuarda las colisiones en cadenas como HashMap

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Complejidad amortizada · El arreglo dinámico por dentro · Lista enlazada · Pila y cola
• Continúa en: Árbol binario de búsqueda · Dos punteros · Ventana deslizante · Sumas prefijas
• Ejercicios sobre el tema: Estructuras de datos