Hashtabellen und Cache-Konflikte: Benchmarks

Hash-Tabellen: Cache-Verfehlungen in der Praxis vermeiden

Hash-Tabellen versprechen O(1)-Zugriffe, aber in der Praxis verlieren sie oft gegen einfache lineare Array-Scans wegen Cache-Verfehlungen. In einer Symboltabelle eines Compiler-Optimizers mit 500 Einträgen über 1024 Buckets sahen wir 1,2 Millionen Cache-Verfehlungen bei 5 Millionen Anweisungen. Der Wechsel zu einem einfachen Array beschleunigte alles um den Faktor 3. Der Übeltäter? Zugriffs-Muster, die Cache-Linien verdrängen.

Grundlegende Implementierung und Kollisionen

Eine einfache direkt-abbildende Hash-Tabelle skaliert nicht wegen Kollisionen. Hier der Basiscode:

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;
}

Einfügen und Suchen erfordern Speicherallokation und String-Vergleiche, aber ohne Kollisionsbehandlung ist die Tabelle nutzlos.

Kollisionslösungsstrategien

Eine Kollision tritt auf, wenn unterschiedliche Schlüssel auf denselben Index hashen. Zwei Hauptansätze:

Verkettung (Chaining)

Eine verkettete Liste pro Bucket verteilt den Speicherzugriff:

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;
}

Die Suche folgt Zeigern, wobei jeder Schritt ein Cache-Verfehlen riskiert.

Offene Adressierung

Lineares Probing in einem zusammenhängenden Array erhält die Lokalität:

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;
}

Sequentieller Zugriff minimiert Verfehlungen: Die erste Cache-Linien-Ladung deckt 7–8 Elemente ab.

| Strategie | Cache-Verfehlungen pro Suche | Lokalität |

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

| Verkettung | 3–10 (bei Kette Länge 3) | Schlecht |

| Probing | 1–2 | Gut |

Analyse der Cache-Verfehlungen

Bei Verkettung erfordert jeder Knoten eine separate Ladung: Bucket (1 Verfehlung), Eintrag (2–3), next-Zeiger (1). Insgesamt: bis zu 10 Verfehlungen.

Probing lädt eine gesamte Cache-Linie, sodass nachfolgende Probes den Cache treffen. Das sind 3–5x weniger Verfehlungen.

Benchmark: 1000 Einfügungen, 10.000 Suchen (Auslastung 0,5, 2048 Buckets):

• Verkettung: 450k Einfügezyklen, 2,1 Mio. Suchzyklen, 45k Verfehlungen
• Probing: 180k Einfügezyklen, 650k Suchzyklen, 12k Verfehlungen

Probing ist insgesamt 3,2x schneller.

Qualität der Hash-Funktion

Eine schlechte Hash-Funktion wie key[0] % size gruppiert Schlüssel nach erstem Zeichen, durchschnittliche Kettenlänge 38,5.

FNV-1a verteilt gleichmäßig:

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

Spezialisierte Hashes:

• Für Integers: return key;
• Für Zeiger: (uintptr_t >> 3) * 2654435761u

Benchmark: FNV-1a ergibt durchschnittliche Kettenlänge 0,98 vs. 38,5 bei schlechter Hash.

Auslastungsfaktor und Neustrukturierung

Auslastungsfaktor = Einträge / Buckets.

• Verkettung: >1,0 OK, aber Verschlechterung
• Probing: Unter 0,7–0,8 halten

Bei 0,9: 10,5 Probes im Schnitt; bei 0,95: 20,5.

Neustrukturieren bei 0,7 (Größe verdoppeln, amortisiert O(1)):

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

Cache-optimierte Struktur

• Offene Adressierung + 2er-Potenz-Größe (hash & mask statt %).
• Enge Verpackung:

typedef struct {
    uint32_t hash;
    uint32_t key;
    uint32_t value;
} entry_t;  // 12 Bytes, 5 pro Cache-Linie

• Getrennte Schlüssel/Werte bei großen Payloads.
• SIMD-Probing (AVX2 prüft 8 Elemente auf einmal).

Robin-Hood-Hashing

Probing-Variante: Beim Einfügen „rauben“ von Elementen mit geringerer Probe-Distanz.

Beispiel: key4 (hash=1) verdrängt key2 (dist=1 > 0), balanciert Probe-Längen. Minimiert Probe-Varianz.

Wichtige Erkenntnisse

• Offene Adressierung mit linearem Probing ist 3–5x cache-effizienter als Verkettung.
• Qualitäts-Hash (FNV-1a) reduziert Kollisionen um den Faktor 40.
• Auslastung <0,7 + Verdopplung = amortisiert O(1).
• Enge Verpackung + 2er-Potenz-Größe minimieren Verfehlungen.
• Robin-Hood-Hashing optimiert Probe-Verteilung.

— Editorial Team