哈希表和缓存冲突：基准测试

哈希表：如何避免真实项目中的缓存失效

哈希表理论上提供 O(1) 查找速度，但在实际应用中往往输给线性数组扫描，因为缓存失效。在编译器优化器的符号表中，500 个条目分布在 1024 个桶中，执行 500 万条指令时产生了 120 万次缓存失效。切换到普通数组后，速度提升了 3 倍。罪魁祸首？就是访问模式导致的缓存行驱逐。

基础实现与冲突处理

简单直接映射的哈希表因冲突而无法扩展。这是基础代码：

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

插入和查找需要内存分配和字符串比较，但没有冲突处理，哈希表就毫无用处。

冲突解决策略

冲突发生在不同键哈希到同一索引时。主要有两种方法：

链地址法

每个桶用链表分散内存访问：

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

查找需跟随指针，每步都可能引发缓存失效。

开放寻址法

线性探测使用连续数组保持局部性：

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

顺序访问最小化失效：首次缓存行加载覆盖 7–8 个元素。

| 策略 | 每次查找缓存失效次数 | 局部性 |

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

| 链地址法 | 3–10（链长 3 时） | 差 |

| 线性探测 | 1–2 | 好 |

缓存失效分析

链地址法中，每个节点需单独加载：桶（1 次失效）、条目（2–3 次）、next 指针（1 次）。总计高达 10 次失效。

线性探测加载整条缓存行，后续探测命中缓存。失效次数减少 3–5 倍。

基准测试：1000 次插入，10,000 次查找（负载因子 0.5，2048 个桶）：

• 链地址法：插入 45 万周期，查找 210 万周期，4.5 万次失效
• 线性探测：插入 18 万周期，查找 65 万周期，1.2 万次失效

线性探测整体快 3.2 倍。

哈希函数质量

差劲的哈希如 key[0] % size 会按首字符聚类，平均链长 38.5。

FNV-1a 分布均匀：

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

专用哈希：

• 整数：return key;
• 指针：(uintptr_t >> 3) * 2654435761u

基准测试：FNV-1a 平均链长 0.98，差哈希为 38.5。

负载因子与扩容

负载因子 = 条目数 / 桶数。

• 链地址法：>1.0 可接受但性能下降
• 线性探测：保持 <0.7–0.8

负载 0.9 时平均 10.5 次探测；0.95 时 20.5 次。

负载 0.7 时扩容（桶数翻倍，均摊 O(1)）：

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

缓存优化的数据结构

• 开放寻址 + 2 的幂大小（用 & 掩码代替 %）。
• 紧凑打包：

typedef struct {
    uint32_t hash;
    uint32_t key;
    uint32_t value;
} entry_t;  // 12 字节，每缓存行 5 个

• 大负载时分离键/值。
• SIMD 探测（AVX2 一次检查 8 个元素）。

Robin Hood 哈希

探测变体：插入时，从探测距离小的元素“抢”位置。

示例：key4（哈希=1）替换 key2（距离=1 > 0），平衡探测长度。最小化探测方差。

关键要点

• 线性探测的开放寻址比链地址法缓存效率高 3–5 倍。
• 优质哈希（FNV-1a）减少 40 倍冲突。
• 负载 <0.7 + 翻倍扩容 = 均摊 O(1)。
• 紧凑打包 + 2 的幂大小最小化失效。
• Robin Hood 哈希优化探测分布。

— Editorial Team