Tabla hash

Código en:JavaC#PythonJavaScript

En resumen: Una tabla hash (Dictionary en C#) guarda pares clave-valor en cubetas: el hash de la clave dice en qué cubeta está, 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.

var cache = new PriceTable(key => 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.

int[] keys = { 1007, 2043, 3010, 4051 };
int buckets = 8;
foreach (int key in keys)
{
    int hash = key.GetHashCode();
    int index = (hash % buckets + buckets) % buckets;
    Console.WriteLine(key + " -> " + hash + " -> 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. 1007.GetHashCode() 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. Las dos claves están en una misma cubeta: 4051 cuelga detrás de 2043 como una cadena.
6. Se busca 4051: el mismo número, la misma cubeta 3. Equals 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:

static int SkuHash(string key)
{
    int h = 0;
    foreach (char c in key)
    {
        h = 31 * h + c;
    }
    return h & 0x7fffffff;
}

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

class Entry
{
    public readonly string Key;
    public double Price;
    public Entry? Next;

    public Entry(string key, double price, Entry? next)
    {
        Key = key;
        Price = price;
        Next = next;
    }
}

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

class PriceTable
{
    private readonly Func<string, int> hash;
    private Entry?[] buckets = new Entry?[4];
    private int size = 0;
    public long Compares { get; private set; }

    public PriceTable(Func<string, int> hash)
    {
        this.hash = hash;
    }

    public int Capacity => buckets.Length;

    private int Index(string key) => hash(key) % buckets.Length;

    public void Put(string key, double price)
    {
        int i = Index(key);
        for (var e = buckets[i]; e != null; e = e.Next)
        {
            Compares++;
            if (e.Key == key)
            {
                e.Price = price;
                return;
            }
        }
        buckets[i] = new Entry(key, price, buckets[i]);
        size++;
        if (size > buckets.Length * 3 / 4) Resize();
    }

    private void Resize()
    {
        var fresh = new Entry?[buckets.Length * 2];
        foreach (var head in buckets)
        {
            for (var e = head; e != null; e = e.Next)
            {
                int i = hash(e.Key) % fresh.Length;
                fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
            }
        }
        buckets = fresh;
    }

    public double? Get(string key)
    {
        int i = Index(key);
        for (var e = buckets[i]; e != null; e = e.Next)
        {
            Compares++;
            if (e.Key == key) return e.Price;
        }
        return null;
    }
}

• 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:

private int Index(string key) => 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.

private int Index(string key) => hash(key) % buckets.Length;

public void Put(string key, double price)
{
    int i = Index(key);
    for (var e = buckets[i]; e != null; e = e.Next)
    {
        Compares++;
        if (e.Key == key)
        {
            e.Price = price;
            return;
        }
    }
    buckets[i] = new Entry(key, price, buckets[i]);
    size++;
    if (size > buckets.Length * 3 / 4) Resize();
}

private void Resize()
{
    var fresh = new Entry?[buckets.Length * 2];
    foreach (var head in buckets)
    {
        for (var e = head; e != null; e = e.Next)
        {
            int i = hash(e.Key) % fresh.Length;
            fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
        }
    }
    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.

var cache = new PriceTable(SkuHash);
cache.Put("SKU-1003", 24.9);
cache.Put("SKU-1001", 12.5);
cache.Put("SKU-1007", 8.99);
cache.PrintBuckets();
Console.WriteLine("---");
cache.Put("SKU-1005", 45.5);
cache.PrintBuckets();

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:

var cache = new PriceTable(SkuHash);
var caps = new List<int>();
for (int n = 2001; n <= 2007; n++)
{
    cache.Put($"SKU-{n}", 10);
    caps.Add(cache.Capacity);
}
Console.WriteLine(string.Join(" ", caps));

Respuesta

4 8 16 16 16 16 16

4 4 4 8 8 8 16

4 4 4 4 8 8 8

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.

static long Compares(PriceTable cache, int n)
{
    for (int i = 0; i < n; i++) cache.Put($"SKU-{10000 + i}", 1 + i);
    for (int i = 0; i < n; i++) cache.Get($"SKU-{10000 + i}");
    return cache.Compares;
}

Console.WriteLine($"primera letra: {Compares(new PriceTable(key => key[0]), 1000)}");
Console.WriteLine($"SKU completo: {Compares(new PriceTable(SkuHash), 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»:

private void Resize()
{
    var fresh = new Entry?[buckets.Length * 2];
    foreach (var head in buckets)
    {
        for (var e = head; e != null; e = e.Next)
        {
            int i = hash(e.Key) % buckets.Length;
            fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
        }
    }
    buckets = fresh;
}

var cache = new PriceTable(SkuHash);
cache.Put("SKU-1003", 24.9);
cache.Put("SKU-1001", 12.5);
cache.Put("SKU-1007", 8.99);
cache.Put("SKU-1005", 45.5);
Console.WriteLine($"SKU-1003: {cache.Get("SKU-1003")?.ToString() ?? "ninguno"}");
Console.WriteLine($"SKU-1001: {cache.Get("SKU-1001")?.ToString() ?? "ninguno"}");
Console.WriteLine($"SKU-1007: {cache.Get("SKU-1007")?.ToString() ?? "ninguno"}");
Console.WriteLine($"SKU-1005: {cache.Get("SKU-1005")?.ToString() ?? "ninguno"}");

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.

1private void Resize()2{3 var fresh = new Entry?[buckets.Length * 2];4 foreach (var head in buckets)5 {6 for (var e = head; e != null; e = e.Next)7 {8 int i = hash(e.Key) % buckets.Length;9 fresh[i] = new Entry(e.Key, e.Price, fresh[i]);10 }11 }12 buckets = fresh;13}

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