Tablas hash y conflictos de caché: benchmarks

# Tablas Hash: Evitando Fallos de Caché en Proyectos Reales

Las tablas hash prometen búsquedas en O(1), pero en la práctica suelen perder contra escaneos lineales de arrays por fallos de caché. En la tabla de símbolos de un optimizador de compiladores con 500 entradas en 1024 cubos, vimos 1,2 millones de fallos de caché en 5 millones de instrucciones. Cambiar a un array simple aceleró todo 3 veces. ¿El culpable? Patrones de acceso que expulsan líneas de caché.

Implementación Básica y Colisiones

Una tabla hash directa simple no escala por las colisiones. Aquí va el código básico:

typedef struct {
    char *key;
    int value;
} entry_t;

#define TABLE_SIZE 1024

entry_t *table[TABLE_SIZE];

int hash(const char *key) {
    unsigned int h = 0;
    while (*key) {
        h = h * 31 + *key++;
    }
    return h % TABLE_SIZE;
}

La inserción y búsqueda requieren asignación de memoria y comparaciones de cadenas, pero sin manejo de colisiones, la tabla es inútil.

Estrategias de Resolución de Colisiones

Una colisión ocurre cuando claves distintas caen en el mismo índice. Dos enfoques principales:

Cadenas (Chaining)

Una lista enlazada por cubo dispersa el acceso a memoria:

typedef struct entry {
    char *key;
    int value;
    struct entry *next;
} entry_t;

void insert(const char *key, int value) {
    int index = hash(key);
    entry_t *entry = malloc(sizeof(entry_t));
    entry->key = strdup(key);
    entry->value = value;
    entry->next = table[index];
    table[index] = entry;
}

La búsqueda sigue punteros, con cada paso arriesgando un fallo de caché.

Dirección Abierta (Open Addressing)

Sondaje lineal en un array contiguo preserva la localidad:

typedef struct {
    char *key;
    int value;
    int occupied;
} entry_t;

entry_t table[TABLE_SIZE];

void insert(const char *key, int value) {
    int index = hash(key);
    while (table[index].occupied) {
        index = (index + 1) % TABLE_SIZE;
    }
    table[index].key = strdup(key);
    table[index].value = value;
    table[index].occupied = 1;
}

El acceso secuencial minimiza fallos: la primera carga de línea de caché cubre 7-8 elementos.

| Estrategia | Fallos de Caché por Búsqueda | Localidad |

|----------------|------------------------------|-----------|

| Cadenas | 3–10 (cadena len 3) | Pobre |

| Sondaje | 1–2 | Buena |

Análisis de Fallos de Caché

En cadenas, cada nodo requiere una carga separada: cubo (1 fallo), entrada (2–3), puntero next (1). Total: hasta 10 fallos.

El sondaje carga una línea completa de caché, por lo que sondajes posteriores aciertan en caché. Eso son 3–5 veces menos fallos.

Benchmark: 1000 inserciones, 10.000 búsquedas (factor de carga 0.5, 2048 cubos):

• Cadenas: 450k ciclos inserción, 2.1M ciclos búsqueda, 45k fallos
• Sondaje: 180k ciclos inserción, 650k ciclos búsqueda, 12k fallos

El sondaje es 3,2 veces más rápido en total.

Calidad de la Función Hash

Un hash pobre como key[0] % size agrupa claves por primer carácter, con longitud media de cadena 38,5.

FNV-1a distribuye uniformemente:

uint32_t fnv1a_hash(const char *key) {
    uint32_t hash = 2166136261u;
    while (*key) {
        hash ^= (uint8_t)*key++;
        hash *= 16777619u;
    }
    return hash;
}

Hashes especializados:

• Para enteros: return key;
• Para punteros: (uintptr_t >> 3) * 2654435761u

Benchmark: FNV-1a da longitud media de cadena 0,98 vs 38,5 para hash pobre.

Factor de Carga y Redimensionamiento

Factor de carga = entradas / cubos.

• Cadenas: >1.0 OK pero degrada
• Sondaje: Mantener <0.7–0.8

A 0.9: 10,5 sondajes avg; a 0.95: 20,5.

Redimensionar a 0.7 (duplicar tamaño, amortizado O(1)):

void insert(const char *key, int value) {
    if (count >= table_size * 0.7) {
        resize_table();
    }
    // insert
}

Estructura Optimizada para Caché

• Dirección abierta + tamaño potencia de 2 (hash & máscara en vez de %).
• Empaquetado ajustado:

typedef struct {
    uint32_t hash;
    uint32_t key;
    uint32_t value;
} entry_t;  // 12 bytes, 5 por línea de caché

• Claves/valores separados para payloads grandes.
• Sondaje SIMD (AVX2 chequea 8 elementos a la vez).

Hashing Robin Hood

Variante de sondaje: Durante inserción, "robar" de elementos con menor distancia de sondaje.

Ejemplo: key4 (hash=1) desplaza key2 (dist=1 > 0), equilibrando longitudes de sondaje. Minimiza varianza de sondajes.

Lecciones Clave

• Dirección abierta con sondaje lineal es 3–5 veces más eficiente en caché que cadenas.
• Hash de calidad (FNV-1a) reduce colisiones 40 veces.
• Factor de carga <0.7 + redimensionamiento duplicado = amortizado O(1).
• Empaquetado ajustado + tamaño potencia de 2 minimiza fallos.
• Hashing Robin Hood optimiza distribución de sondajes.

— Editorial Team