7、开放地址法实现（下）：删除操作的陷阱（惰性删除）、二次探测实现、双重哈希实现

好，咱们接着聊开放地址法。上一节我们把线性探测的代码撸了一遍，你可能会觉得：嗯，好像也没那么复杂嘛。但别急，真正的坑还没踩呢。今天我要讲的这三个东西——惰性删除、二次探测、双重哈希——才是开放地址法里最容易翻车的地方。

7.1 删除操作的陷阱：为什么不能直接删？

先问一个问题：在开放地址法的哈希表里，你找到要删的元素，直接把它置空（比如设成 NULL 或 0），行不行？

我告诉你，绝对不行。我在项目里第一次这么干的时候，差点把线上服务搞崩了。

原因很简单：开放地址法的探测序列是连续的。假设你插入了 A、B、C 三个元素，它们因为哈希冲突，依次占用了位置 3、4、5。现在你把 B 删了，位置 4 变成空。下次你查找 C 的时候，从位置 3 开始线性探测，走到位置 4 发现是空的——按照开放地址法的规则，空位就意味着查找结束，直接返回“没找到”。但 C 明明就在位置 5 啊！

这就是删除操作带来的探测链断裂问题。说白了，你删了一个中间节点，后面的元素就全“失联”了。

7.2 惰性删除：给元素打上“墓碑”标记

那怎么办？业界通用的做法是——惰性删除（Lazy Deletion）。

思路很简单：不真的把元素删掉，而是给它打一个特殊的标记，比如叫 DELETED 或“墓碑”。查找的时候，遇到墓碑不能停，要继续往后找。插入的时候，遇到墓碑可以覆盖。

我个人的习惯是用一个枚举来定义三种状态：

typedef enum {
    EMPTY,      // 空位
    OCCUPIED,   // 已占用
    DELETED     // 已删除（墓碑）
} SlotStatus;

每个槽位除了存数据，还要存一个状态字段。这样查找时遇到 DELETED 就跳过继续往后探测，插入时遇到 EMPTY 或 DELETED 都可以放进去。

我曾经在一个缓存系统里用过惰性删除，结果忘了做重哈希，表里堆了 40% 的墓碑，查找效率直接掉到 O(n)。嗯，那天的排查过程，至今记忆犹新。

7.3 二次探测：解决线性探测的“聚集”问题

线性探测有个毛病——一次聚集。冲突的元素会挤成一团，越挤越大，像个雪球。你想想看，如果位置 3、4、5 都被占了，下一个冲突的元素就得跑到位置 6，然后位置 7……这团“拥堵区”会越来越长。

二次探测就是为了解决这个问题。它的探测步长不是固定的 1，而是 1², 2², 3², … 这样跳着走。

公式是：index = (hash(key) + i²) % table_size，其中 i 从 0 开始递增。

举个例子：假设哈希值是 3，表大小是 11。

• i=0：位置 3
• i=1：位置 4（3+1）
• i=2：位置 7（3+4）
• i=3：位置 1（3+9=12，12%11=1）

你看，探测的位置跳开了，不会挤在一起。这就是二次探测的核心思想——分散探测路径。

我建议表大小选一个4k+3 形式的质数，比如 7、11、19、43。这样二次探测可以保证遍历整个表。

7.4 双重哈希：最灵活的探测策略

如果说二次探测是“跳着走”，那双重哈希就是“随机走”——当然，这个随机是伪随机的，由第二个哈希函数决定。

公式：index = (hash1(key) + i * hash2(key)) % table_size

这里有两个哈希函数：

• hash1(key)：决定初始位置
• hash2(key)：决定探测步长

因为每个 key 的 hash2 值不同，所以即使两个 key 的初始位置相同，它们的探测序列也不一样。这就彻底避免了聚集问题。

举个例子：

hash1(key) = key % 11
hash2(key) = 1 + (key % 9)   // 保证步长不为0

插入 key=15：
  hash1 = 15 % 11 = 4
  hash2 = 1 + (15 % 9) = 7
  探测序列：4, (4+7)%11=0, (4+14)%11=7, ...

插入 key=26：
  hash1 = 26 % 11 = 4（冲突了）
  hash2 = 1 + (26 % 9) = 8
  探测序列：4, (4+8)%11=1, (4+16)%11=9, ...

你看，两个 key 初始位置都是 4，但后续的探测路径完全不同。这就是双重哈希的魅力。

7.5 三种探测策略对比

策略	探测公式	优点	缺点	适用场景
线性探测	i = 1, 2, 3, ...	实现简单，缓存友好	一次聚集严重	表小、负载因子低
二次探测	i = 1², 2², 3², ...	减少聚集	二次聚集，可能无法遍历全表	中等规模，负载因子 < 0.5
双重哈希	i * hash2(key)	无聚集，分布均匀	计算开销稍大	高负载、高性能要求

7.6 知识结构图

下面这张图帮你理清今天讲的核心逻辑：

7.7 代码实现：双重哈希的插入与查找

最后，我贴一段双重哈希的插入和查找代码。你注意看墓碑标记的处理：

#define TABLE_SIZE 11

typedef struct {
    int key;
    int value;
    SlotStatus status;
} HashEntry;

HashEntry table[TABLE_SIZE];

int hash1(int key) {
    return key % TABLE_SIZE;
}

int hash2(int key) {
    return 1 + (key % (TABLE_SIZE - 1));
}

void insert(int key, int value) {
    int i = 0;
    int index;
    int first_deleted = -1;  // 记录第一个遇到的墓碑位置

    while (i < TABLE_SIZE) {
        index = (hash1(key) + i * hash2(key)) % TABLE_SIZE;

        if (table[index].status == EMPTY) {
            // 如果之前遇到过墓碑，优先覆盖墓碑
            if (first_deleted != -1) {
                index = first_deleted;
            }
            table[index].key = key;
            table[index].value = value;
            table[index].status = OCCUPIED;
            return;
        }

        if (table[index].status == DELETED && first_deleted == -1) {
            first_deleted = index;  // 记下第一个墓碑
        }

        if (table[index].status == OCCUPIED && table[index].key == key) {
            table[index].value = value;  // 更新已有值
            return;
        }

        i++;
    }

    // 表满了，需要扩容
    printf("Hash table is full!\n");
}

int search(int key) {
    int i = 0;
    int index;

    while (i < TABLE_SIZE) {
        index = (hash1(key) + i * hash2(key)) % TABLE_SIZE;

        if (table[index].status == EMPTY) {
            return -1;  // 遇到空位，肯定没找到
        }

        if (table[index].status == OCCUPIED && table[index].key == key) {
            return table[index].value;  // 找到了
        }

        // 遇到墓碑继续往后找
        i++;
    }

    return -1;  // 遍历完整个表都没找到
}

这段代码里有个细节：插入时如果遇到墓碑，我不会立刻覆盖，而是先记下第一个墓碑的位置。等真正找到空位或者确定要插入时，再回头覆盖墓碑。这样做的好处是——尽量把墓碑留在后面，减少对查找路径的影响。

嗯，这个小技巧是我在调优一个高并发哈希表时总结出来的。虽然提升不大，但积少成多嘛。

---

好了，今天的内容就到这里。开放地址法的删除、二次探测、双重哈希，这三个点你消化一下。代码最好自己敲一遍，光看是记不住的。