Cuckoo Hash

常规哈希性能局限

传统哈希表处理碰撞时存在以下限制：

  • 线性探测通过步长遍历连续槽位寻找空位，但容易产生聚集现象，使探测序列随负载因子升高而变长，查找可能退化为线性扫描。
  • 双重哈希用第二哈希函数计算步长，可缓解聚集，但仍难以提供最坏情况查询上界。
  • 链式哈希用链表挂载碰撞元素。负载升高时链表变长，且非连续内存布局容易产生缓存未命中。

基本思想

为满足缓存系统对稳定查询时间的要求，Cuckoo Hash 引入多位置候选和元素置换机制。它通常包含两个等长哈希数组和两个独立哈希函数。

设两个哈希函数分别为 h1 与 h2。对于键 k，其候选位置为 h1(k) 和 h2(k)。在稳定状态下，键 k 只能存放在这两个槽位之一，且只出现一次。

Cuckoo Hash 处理冲突时采用置换逻辑：当新元素的目标槽位已被占用，新元素会占据该槽位并驱逐原元素；被驱逐元素再尝试迁移到自己的另一个候选槽位。

元素的查找/插入/踢出

在 cuckoo hash 中，因为一个键仅可能出现在 table 中的 h1(k) 位置或者 h2(k) 位置，所以查找时仅需要探测这两个位置。

在 Cuckoo Hash 的插入过程中，踢出行为可能引发链式的级联反应。假设哈希表中已经存储了元素 A、B 与 D。当系统试图插入新元素 C 时，计算得出其首选槽位与 A 的首选槽位重叠。系统将元素 A 剔除，并将 C 存入该位置。

元素 A 被驱逐后，系统计算其备用槽位，发现该槽位已被元素 D 占据。遵循踢出逻辑，A 将替换 D 的位置，使得 D 处于游离状态。最后，系统计算 D 的备用槽位，确认该位置当前处于空闲状态，遂将 D 存入此位置，整个驱逐链条至此终止。

若踢出过程形成环，工程实现通常设置最大踢出次数作为阻断阈值。当连续踢出次数达到阈值时，系统判定当前哈希函数组合无法完成插入，终止常规置换并触发重哈希：重新选择哈希函数，申请新表空间，并将旧表数据重新映射插入。

Cuckoo Hash 的查找快，是因为每个键只有两个合法住处；插入复杂，也是因为每个键只有两个合法住处。踢出链条本质上是在为当前键腾位置：新键占一个槽，被赶走的旧键去它的另一个槽。如果这条“搬家链”最后遇到空位，插入成功；如果反复回到已经访问过的局部结构，就说明当前哈希函数组合无法容纳这批键，需要重哈希。

键值分离存储

实现键值映射时，内存布局会影响性能。若将键和值打包后直接存入哈希槽，可能出现两个问题：值结构体较大时会增加哈希表数组体积；级联踢出时需要频繁拷贝较大结构体，增加内存带宽消耗。

因此，常采用键值分离存储。哈希表槽位只存放键和对应值的地址指针，实际值集中存储在外部内存池或预分配数组中。发生驱逐和位置互换时，只需交换键和指针，减少大对象迁移。

数据结构

基于上述理论，可以使用连续数组结构实现哈希空间。以下代码展示了 Cuckoo Hash 系统的核心结构声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 原子槽位支持并发读写场景下的无锁读取。
#include <atomic>
// 写入路径需要互斥，避免多条踢出链互相破坏。
#include <mutex>

// 示例中键类型使用 int；0 被保留为空槽哨兵。
typedef int KeyType;
// Cuckoo 哈希表类。
class Cuckoo {
protected:
    // 写操作互斥锁；读操作可直接读取原子槽位。
    std::mutex mtx;
    // 示例容量；实际工程中通常随负载动态扩容。
    static const int SIZE = 1024;
    // 最大踢出深度；超过该阈值即认为出现环路并需要重哈希。
    static const int MAX_EVICTIONS = SIZE;
    // 哈希槽数组；0 表示空槽。
    std::atomic<KeyType> T[SIZE];
    // 第一哈希函数，返回第一候选槽。
    int hash1 (const KeyType &key);
    // 第二哈希函数，返回第二候选槽。
    int hash2 (const KeyType &key);
    // 只检查第一候选槽，命中返回 key，否则返回 0。
    KeyType get1 (const KeyType &key);
    // 只检查第二候选槽，命中返回 key，否则返回 0。
    KeyType get2 (const KeyType &key);
    // 回溯式踢出；which 表示当前尝试的哈希函数，pre_pos 表示来源槽位。
    bool bt_evict (const KeyType &key, int which, int pre_pos, int depth = 0);
public:
    // 构造函数初始化所有槽为空。
    Cuckoo ();
    // ~Cuckoo ();
    // 查找 key。
    KeyType get (const KeyType &key);
    // 插入 key。
    void put (const KeyType &key);
};

系统内部维护原子槽位数组 T 作为存储载体，互斥量 mtx 用于并发写入控制。公有接口提供插入与检索，私有接口封装哈希函数和数据迁移逻辑。

串行查找

在没有并发写入干扰时，Cuckoo Hash 查找只需检查两个候选位置，因此时间复杂度稳定。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 引入类声明。
#include "cuckoo.h"
namespace cuckoo {
// 构造函数：把所有槽位初始化为空槽哨兵 0。
Cuckoo::Cuckoo () {
    for (int i = 0; i < SIZE; ++i) {
        T[i].store(0);
    }
}

// 第一哈希函数映射到前半张表。
int Cuckoo::hash1 (const KeyType &key) {
    // 防止除数为 0。
    assert (SIZE != 0);
    // 前半区间长度。
    int half_siz = SIZE / 2;
    // 第一张表位于 [0, half_siz)。
    return key % half_siz;
}

// 第二哈希函数映射到后半张表。
int Cuckoo::hash2 (const KeyType &key) {
    // 防止除数为 0。
    assert (SIZE != 0);
    // 后半区间长度。
    int half_siz = SIZE / 2;
    // 第二张表位于 [half_siz, SIZE)。
    return key / half_siz % half_siz + half_siz;
}

// 检查 key 的第一候选槽。
KeyType Cuckoo::get1 (const KeyType &key) {
    // 计算第一候选位置。
    int pos = hash1(key);
    // 原子读取槽位；命中返回 key，未命中返回空值 0。
    return (T[pos].load() == key) ? key : 0;
}

// 检查 key 的第二候选槽。
KeyType Cuckoo::get2 (const KeyType &key) {
    // 计算第二候选位置。
    int pos = hash2(key);
    // 原子读取槽位；命中返回 key，未命中返回 0。
    return (T[pos].load() == key) ? key : 0;
}

// 查找 key，只需要检查两个候选槽。
KeyType Cuckoo::get (const KeyType &key) {
    // 0 被保留为空槽哨兵，因此不能作为合法 key。
    if (key == 0) {
        printf("invalid key\n");
        return 0;
    }
    // 先检查第一候选槽。
    KeyType result = get1 (key);
    if (result == 0) {
        // 第一候选槽未命中时再检查第二候选槽。
        result = get2 (key);
    }
    // 命中返回 key，未命中返回 0。
    return result;
}
}

代码先处理空值边界，并预留 0 表示无效或空槽。查询只执行两次数组寻址与判断，指令数量有固定上界。

并行查找

内存缓存常面对大量并发读取。读取不会改变数据状态，在排除并发写入干扰后，可以避免互斥锁，减少线程竞争和上下文切换开销。

利用线程管理机制，能够以无锁架构实施高吞吐量查询。以下为主程序的测试模型实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 并行查询测试程序。
#include <vector>
#include "cuckoo.cpp"
using namespace cuckoo;
// 测试插入和查询的键数量。
static const int TOTAL = 10;
int main(int argc, char* argv) {
    // 创建 Cuckoo 哈希表。
    Cuckoo test;
    // 先用单线程插入，避免测试阶段混入并发写入。
    for(int i=1; i<=TOTAL; ++i) {
        test.put(i);
    }
    // 创建多个线程并发查询。
    std::vector<std::thread> threads;
    // 清空线程容器，确保初始状态为空。
    threads.clear();
    // 每个线程查询一个 key。
    for(int i=1; i<=TOTAL; ++i) {
        // lambda 按引用捕获 test，并通过参数传入线程编号。
        threads.emplace_back([&] (int thread_id) {
            // 查询 thread_id 对应的 key，并输出结果。
            printf("thread: %d get %d\n", thread_id, test.get(thread_id));
        }, i);
    }
    // 等待所有查询线程结束。
    for(int i=0; i < TOTAL; ++i) {
        threads[i].join();
    }
    return 0;
}

示例为每个查询创建一个线程，并在各线程中调用查找函数。由于底层数组在此阶段保持只读，缓存行可被多个核心读取，适合扩展并发查询。

插入与踢出

引入写入后，需要处理位置碰撞。基本逻辑是一个带暂存变量的循环：新元素若写入首选槽失败，就替换槽内旧元素；被替换元素进入暂存变量，再计算自己的备用位置，继续判定和互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 交换两个普通对象的值；原子槽位版本不直接使用该函数。
template <typename T>
inline void swap (T* a, T* b) {
    // 参数必须指向有效对象。
    assert (a!= NULL && b!= NULL);
    // 临时变量保存 a 原值。
    T tmp = *a;
    // 把 b 写入 a。
    *a = *b;
    // 把 a 原值写入 b。
    *b = tmp;
}

// 基础踢出版插入。
void Cuckoo::put (const KeyType &key) {
    // 0 是空槽哨兵，拒绝插入。
    if(key == 0) {
        printf("invalid key\n");
        return;
    }
    // 已存在的 key 不重复插入。
    if (get (key) != 0) {
        printf("duplicate key, put fail\n");
        return;
    }
    // 优先尝试第一候选槽。
    if (T[hash1(key)].load() == 0) {
        T[hash1(key)].store(key);
    // 第一候选槽占用时，尝试第二候选槽。
    }else if (T[hash2(key)].load() == 0) {
        T[hash2(key)].store(key);
    }else{
        // 两个候选槽都占用时，启动踢出链。
        KeyType evicted = key;
        // which 在 0 和 1 之间切换，表示下一次使用哪个哈希函数。
        int which = 0;
        // idx 是当前要尝试写入的位置。
        int idx = hash1 (evicted);
        // pre_pos 记录当前元素来自哪个槽位，仅用于调试输出。
        int pre_pos = -1;
        // 持续踢出，直到找到空槽。
        while (T[idx].load() != 0) {
            printf("evicted key %d from %d to %d\n", evicted, pre_pos, idx);
            // 保存当前槽位旧元素。
            KeyType old = T[idx].load();
            // 将待放入元素写入当前位置。
            T[idx].store(evicted);
            // 被踢出的旧元素成为下一轮待放入元素。
            evicted = old;
            // 更新来源位置。
            pre_pos = idx;
            // 切换到另一个哈希函数对应的位置。
            which = 1 - which;
            idx = (which == 0)? hash1 (evicted) : hash2 (evicted);
        }
        // 最终找到空槽，把最后一个被踢出的元素写入。
        printf("evicted key %d from %d to %d\n", evicted, pre_pos, idx);
        T[idx].store(evicted);
    }
}

上述控制流维护游标变量 which，使其在两个哈希函数之间切换。循环不断执行槽位覆盖，直到目标位置为 0，即找到空槽。该基础版本用于说明踢出机制；若驱逐路径形成闭环，实际实现需要配合最大踢出次数、回滚/重哈希或回溯式写入策略。

常规驱逐算法在读写混合负载下存在并发安全问题。当系统用 swap 或“读出再覆写”方式把槽内值移入局部变量时，该值会在短时间内不位于底层数组中。若并发读线程此时检查该值的两个候选位置，可能得到空值并返回假性未命中。

一种处理方式是使用全局读写锁保护相关内存区域。但在读负载较高时，这会造成读操作阻塞，降低整体响应性能。

基于回溯插入

回溯重构技术提供了避免写周期锁定的替代方案。该方案放弃了按时间顺序的前向置换，转而探索替换链条直至空槽位，并逆向倒退实施数据拷贝。可以将其逻辑类比为基于回溯的递归算法，当输入参数未触及基础条件时，函数持续分配栈帧进行深度下潜；一旦到达底层的终止条件，控制流开始返回计算结果并收束每一层级的栈状态。

在 Cuckoo Hash 的链式踢出中，系统首先追踪一个潜在的完整踢出序列而不进行内存写入操作。例如检测出序列 A 将替换 B，B 将替换 C，C 将替换 D，而 D 具备可用的空位置。系统随即将数据移入空位置，并将各个前置元素逐级拉入新的槽位中。由于所有赋值操作均不产生数据离开哈希表的空窗期，所有键在全局时钟下的任一微观切片内均存在于数组中。

理论研究中采用随机游走模型分析了该机制。将哈希表抽象为二分有向图后，回溯过程等价于执行一段带延迟的图上游走任务。研究证明，在包含无环路径约束的条件下，回溯引发的时间损耗仅相当于原随机游走时间常数级别的乘数扩展。在 C++ 实现中，这一无锁读取配合递归倒推写入的过程定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 回溯式踢出：先递归为被踢出的元素寻找位置，再回填当前 key。
bool Cuckoo::bt_evict(const KeyType &key, int which, int pre_pos, int depth) {
    // 递归深度过大通常意味着踢出路径成环，需要重哈希。
    if (depth >= MAX_EVICTIONS) {
        printf("cycle detected, rehash required\n");
        return false;
    }

    // which 为 0 时使用第一候选槽，为 1 时使用第二候选槽。
    int idx = (which == 0)? hash1 (key) : hash2 (key);
    // 递归基：当前位置为空，可直接放入 key。
    if (T[idx].load() == 0) {
        printf("evicted key %d from %d to %d\n", key, pre_pos, idx);
        T[idx].store(key);
        return true;
    }
    // 当前槽已有元素，需要先为槽内元素寻找备用位置。
    printf("evicted key %d from %d to %d\n", key, pre_pos, idx);
    // 读取当前槽位中即将被递归安置的元素。
    KeyType cur = T[idx].load();
    // 先递归处理被踢出的 cur；成功后再把 key 写入当前槽位。
    if (!bt_evict (cur, 1 - which, idx, depth + 1)) {
        return false;
    }
    // 下层已经成功腾挪，当前 key 可以写入 idx。
    T[idx].store(key);
    return true;
}

// 使用回溯踢出的插入接口。
void Cuckoo::put (const KeyType &key) {
    // 0 是空槽哨兵，不能插入。
    if (key == 0) {
        printf("invalid key\n");
        return;
    }
    // 重复 key 不插入。
    if (get (key)!= 0) {
        printf("duplicate key, put fail\n");
        return;
    }
    // 第一候选槽为空时直接写入。
    if (T[hash1 (key)].load() == 0) {
        T[hash1 (key)].store(key);
    // 第二候选槽为空时直接写入。
    }else if (T[hash2 (key)].load() == 0) {
        T[hash2 (key)].store(key);
    }else{
        // 两个候选槽均被占用时，使用回溯式踢出。
        if (!bt_evict (key, 0, -1)) {
            // 此处应触发重哈希；示例保留接口位置而不展开实现细节
            printf("put fail, rehash required\n");
        }
    }
}

递归的最深处完成了元素向底层空单元的写入，并在每次函数调用返回时通过赋值指令将上层元素转移至当前槽位。在 C++ 实现中，若要允许查询线程与写线程真正并发执行，槽位读写必须使用 std::atomic 或等价的原子存储语义；在此前提下，并发探测可以读取到有效数据体，从而避免针对查询线程加锁。

回溯式插入的关键优势是避免“某个键被暂时拿在手里、表里两个位置都查不到”的窗口。它先找到链尾空槽，再从后往前搬运，所以每一步写入后，相关键仍然留在表中的某个合法位置。这样并发读线程即使看到中间状态，也更不容易得到错误的未命中结果。

并行插入

并发读取的无锁化依赖于数据在任何时刻不会被移除哈希表，但并发写入引发的物理内存状态竞争依然构成威胁。如果系统内多个独立线程试图对同一个物理内存地址进行写覆写操作，会导致替换链条的断裂甚至游标异常。为确保系统状态机的确定性转换，写操作进入替换循环前必须声明互斥所有权。

通过 C++ 的资源获取即初始化机制，写线程请求持有作用域锁以垄断写权限。如下文代码展示，当控制流脱离加锁作用域边界，锁对象将自动释放其资源，降低了死锁风险：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 写线程互斥版本的插入接口。
void Cuckoo::put (const KeyType &key) {
    // 0 是空槽哨兵，不能插入。
    if (key == 0) {
        printf("invalid key\n");
        return;
    }
    // 写操作互斥，避免多条踢出链同时修改同一批槽位。
    std::unique_lock<std::mutex> lck (mtx);
    // 持锁后再次检查重复 key，避免与其他写线程竞争。
    if (get (key)!= 0) {
        printf("duplicate key, put fail\n");
        return;
    }
    // 第一候选槽为空时直接写入。
    if (T[hash1 (key)].load() == 0) {
        T[hash1 (key)].store(key);
    // 第二候选槽为空时直接写入。
    }else if (T[hash2 (key)].load() == 0) {
        T[hash2 (key)].store(key);
    }else{
        // 写线程之间互斥；读线程仍可通过原子槽位并发执行get。
        if (!bt_evict (key, 0, -1)) {
            printf("put fail, rehash required\n");
        }
    }
}

循环路径检测与重哈希

随着底层数组内元素的持续填充，系统承载能力逐渐饱和。在极端场景下，数据的级联置换将在少数几个节点之间生成死锁环状路径，导致程序陷于无限循环。将哈希映射空间抽象为二分图后，若图中包含一个使得部分元素无处可放的闭合回路，该过程即无法自然终止。

分析上述追踪数据，键 28 在槽位 25 和槽位 26 之间形成了相互包含的死锁结构。无论元素如何移动，其后续的探测链路均指向上一次刚发生驱逐的位置，最终造成整体驱逐动作在这几个孤立顶点中无限往复。并非所有具备环状结构的图都会造成无限循环。存在一类结构为可终止环。在该类结构下，尽管部分踢出过程呈现出前驱顶点的二次访问，但只要尾部置换链路能够通过另一次散列计算寻获一个处于边缘且未被占用的空顶点，该踢出过程依然会正常完结。

环检测不要简单理解成“出现重复槽位就一定失败”。真正失败的是重复之后再也无法走向空槽的封闭结构；如果重复路径之外还有分支能抵达空位，踢出过程仍可能终止。工程实现用最大踢出次数作为近似判定，是在性能和判定精度之间做折中。

针对不可终止循环，需要设置阻断逻辑。通常将最大踢出次数设为阈值；当循环次数达到上限，系统判定当前置换无法完成并中止常规流程。随后触发重哈希，选择新的哈希函数，申请更大的数组，并将历史数据重新映射到新表。

性能评估

工程性能需要通过实验验证。将 Cuckoo Hash 与链式哈希进行负载测试，可以观察二者在负载升高时的性能差异。

设定不同的样本集容量，分别记录在两套机制内检索指定数据集合的平均键值比较次数，对比数据呈现于下表：

查找键总数 系统负载因子 Cuckoo Hash 操作消耗 链式 Hash 操作消耗
50 0.10 1.00 1.00
250 0.50 1.00 3.00
375 0.75 1.33 4.67
500 1.00 1.50 5.50

数据表明，当数据量较少（负载因子为 0.10）时，冲突概率较低，两类结构通常一次比对即可定位。随着数据量增加，链式哈希在负载达到 1.00 时由于链表节点堆积，平均扫描深度上升至 5.50。相比之下，Cuckoo Hash 的单元素探测范围受双候选位置约束，因此满载时的平均开销维持在 1.50。

在多类型混合负荷测试下，线性探测凭借连续内存的高速缓存行预读能力维持了单次查询周期的领先。然而，一旦考虑系统扩展导致的数据结构超出二级缓存容量边界，不同算法均承受了缓存未命中的时间惩罚。根据计算时间模型：

时间=基础开销+缺失惩罚⋅存取次数⋅(1−缓存容量哈希表容量)\text{时间} = \text{基础开销} + \text{缺失惩罚} \cdot \text{存取次数} \cdot \left(1 - \frac{\text{缓存容量}}{\text{哈希表容量}}\right)

在内存访问深度成为性能瓶颈的大规模配置下，尽管 Cuckoo Hash 的基础时间略高，但其探测次数更稳定，访问频率增长较慢，因此能够降低随机访问延迟对整体性能的影响。在 QPS（每秒查询率）刻画中，系统运行于 50% 至 95% 的负载区间时，无状态命中与全部命中指标保持连续变化，没有出现指数级性能下降。

Cuckoo Filter

在处理超大规模任务时，全量存储原始数据会带来较高的内存开销。传统方案部署 Bloom Filter，通过位映射集合叠加输入项散列值，达到数据压缩目的。然而 Bloom Filter 不支持删除语义，任何单比特状态的重置操作都会影响共享同一比特的其余数据。

相比之下，Cuckoo Filter 不保存完整的原始数据键，而是在槽位内部嵌入较短的数据特征哈希签名，即指纹。指纹通常占用几个到几十个比特位，支持直接置入底层的原子整数数组内实现无锁内存屏障更新。利用紧凑的存储结构，该模型在维持相近假阳性率的前提下，可以降低总体内存占用。

在发生哈希位置被占用而需执行重定位操作时，由于系统缺失对原始数据的调用权限，它无法利用基础计算公式获取对端的候选哈希地址。Cuckoo Filter 通过异或位运算，构建首尾两端哈希地址的映射：次级哈希地址=初级哈希地址⊕哈希函数(元素指纹)次级哈希地址 = 初级哈希地址 ⊕ 哈希函数 (元素指纹)。基于逻辑异或操作的自反特质，系统提取当前槽位索引与自身留存的特征指纹，即可倒推重建出初始哈希偏移量。这一架构打破了驱逐链路中对原数据体强关联约束的限制。

异或公式的好处是“从任意一端都能算到另一端”。若当前桶索引是 ii，指纹是 ff，另一个候选桶就是 i⊕hash(f)i \oplus \text{hash}(f)。由于同一个值异或两次会抵消，系统不需要完整键，也能在驱逐过程中来回切换候选桶。

在高并发删改场景中，传统移除可能影响读操作。Cuckoo Filter 可引入缓存驱逐记录机制：遇到满载踢出时，先将预判的置换路径暂存，找到空槽后再按路径写入物理槽位。这样可以减少中间状态导致的读错误。相比 Bloom Filter，Cuckoo Filter 还支持删除，并在相近假阳性率下提供更紧凑的存储形式。