Hash tables and cache conflicts: benchmarks

Hash Tables: Avoiding Cache Misses in Real-World Projects

Hash tables promise O(1) lookups, but in practice they often lose to linear array scans due to cache misses. In a compiler optimizer's symbol table with 500 entries across 1024 buckets, we saw 1.2 million cache misses over 5 million instructions. Switching to a plain array sped things up 3x. The culprit? Access patterns that evict cache lines.

Basic Implementation and Collisions

A simple direct-mapped hash table doesn't scale due to collisions. Here's the basic code:

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

Insertion and lookup require memory allocation and string comparisons, but without collision handling, the table is useless.

Collision Resolution Strategies

A collision happens when different keys hash to the same index. Two main approaches:

Chaining

A linked list per bucket spreads memory access:

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

Lookup follows pointers, with each step risking a cache miss.

Open Addressing

Linear probing in a contiguous array preserves locality:

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

Sequential access minimizes misses: the first cache line load covers 7–8 elements.

| Strategy | Cache Misses per Lookup | Locality |

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

| Chaining | 3–10 (for chain len 3) | Poor |

| Probing | 1–2 | Good |

Cache Miss Analysis

In chaining, each node requires a separate load: bucket (1 miss), entry (2–3), next pointer (1). Total: up to 10 misses.

Probing loads an entire cache line, so subsequent probes hit the cache. That's 3–5x fewer misses.

Benchmark: 1000 inserts, 10,000 lookups (load factor 0.5, 2048 buckets):

• Chaining: 450k insert cycles, 2.1M lookup cycles, 45k misses
• Probing: 180k insert cycles, 650k lookup cycles, 12k misses

Probing is 3.2x faster overall.

Hash Function Quality

A poor hash like key[0] % size clusters keys by first character, averaging chain length 38.5.

FNV-1a distributes evenly:

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

Specialized hashes:

• For ints: return key;
• For pointers: (uintptr_t >> 3) * 2654435761u

Benchmark: FNV-1a gives average chain length 0.98 vs 38.5 for poor hash.

Load Factor and Resizing

Load factor = entries / buckets.

• Chaining: >1.0 OK but degrades
• Probing: Keep <0.7–0.8

At 0.9: 10.5 probes avg; at 0.95: 20.5.

Resize at 0.7 (double size, amortized O(1)):

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

Cache-Optimized Structure

• Open addressing + power-of-2 size (hash & mask instead of %).
• Tight packing:

typedef struct {
    uint32_t hash;
    uint32_t key;
    uint32_t value;
} entry_t;  // 12 bytes, 5 per cache line

• Separate keys/values for large payloads.
• SIMD probing (AVX2 checks 8 elements at once).

Robin Hood Hashing

Probing variant: During insert, "steal" from elements with lower probe distance.

Example: key4 (hash=1) displaces key2 (dist=1 > 0), balancing probe lengths. Minimizes probe variance.

Key Takeaways

• Open addressing with linear probing is 3–5x more cache-efficient than chaining.
• Quality hash (FNV-1a) cuts collisions 40x.
• Load factor <0.7 + doubling resize = amortized O(1).
• Tight packing + power-of-2 size minimize misses.
• Robin Hood hashing optimizes probe distribution.

— Editorial Team