cuckoo_hash::insert 反复踢出元素是其核心机制：每个键有k个候选槽位，冲突时踢出旧元素并重安置，可能引发连锁反应；需设踢出上限、用独立哈希函数、预分配空间防realloc、扩容时全量重建。
为什么 cuckoo_hash::insert 会反复踢出已有元素？
这不是 bug，是布谷鸟哈希的核心机制：每个键有 k 个候选槽位（通常 k = 2），插入时若所有槽位都被占，就随机“踢出”其中一个已有元素，让它去它另一个候选槽位“重安置”。这个过程可能连锁发生，形成踢出链。
容易踩的坑：
- 未设最大踢出次数限制，导致死循环（比如所有槽位被同一组键反复抢占）
- 只用线性探测式回退逻辑，误以为“踢一次没位置就失败”，实际应递归/迭代尝试重安置
- 哈希函数不独立——两个哈希函数
h1(key)和h2(key)若强相关（如仅差常数），会导致候选槽位聚集，冲突率陡增
实操建议：设置踢出上限（如 500 次），超限则触发扩容；两个哈希函数必须使用不同种子或不同算法（例如 std::hash + MurmurHash3 的变体）。
如何避免 std::vector 动态扩容破坏槽位地址稳定性？
布谷鸟哈希要求槽位地址固定——因为键的候选位置由哈希值直接映射为数组下标。若底层容器在插入中 realloc，所有已存键的下标计算结果失效。
常见错误现象：find() 突然找不到刚 insert() 进去的键，或插入后出现断言失败（如 assert(pos == h1(k) || pos == h2(k)) 不成立）。
解决方案只有两种：
- 预分配足够空间：构造时传入期望容量
n，并按负载因子（如 0.4–0.5）向上取整到最近 2 的幂，再调用reserve() - 改用定长容器：如
std::array（编译期确定大小）或自定义 slab 分配器管理的连续内存块，禁止运行时 resize
注意：std::vector::resize() 和 shrink_to_fit() 同样危险，只要触发了内存重分配，就破坏哈希一致性。
cuckoo_hash 的空间开销比 std::unordered_map 高多少？
不是“高多少”，而是“结构决定无法省”：布谷鸟哈希必须预留大量空槽位维持低冲突率。理论最优负载因子上限约 0.49（双表）或 0.90（多表但实现复杂），而 std::unordered_map 通常可跑到 0.7–1.0。
举例：存 10000 个元素，std::unordered_map 可能用 14300 个桶；同等条件下，双表布谷鸟哈希需至少 2 × (10000 / 0.49) ≈ 40800 个槽位（两张表各 ~20400）。
关键差异点：
-
std::unordered_map每个桶存链表/动态数组，指针或长度字段带来额外 8–16 字节/桶 -
cuckoo_hash每个槽位只存一个value_type，无指针、无元数据，但总槽数翻倍甚至更多 - 若开启
sizeof(value_type) 的紧凑存储（如int），布谷鸟的空间劣势更明显；若存大对象（如std::string），指针开销占比下降，差距收窄
插入失败时该扩容还是该 fallback 到其他结构？
布谷鸟哈希没有“软失败”——插入返回 false 只代表当前布局已无法容纳新键（无论是否达到负载上限），此时必须打破僵局。
实操中只推荐一种做法：强制扩容 + 重建。原因很实在：
- fallback 到红黑树或链地址法，会破坏接口一致性（用户期望 O(1) 查找，却突然降级为 O(log n) 或 O(n)）
- 混合结构极大增加代码复杂度：需维护多套查找路径、删除逻辑、迭代器行为，调试成本飙升
- 现代 CPU 缓存友好性优先于绝对空间节省：一次 2× 扩容带来的局部性提升，往往比维持高密度但引发多次 cache miss 更快
真正容易被忽略的是：扩容后必须重新哈希全部键，不能复用旧表数据——因为新表大小变了，h1(key) % new_size 和 h2(key) % new_size 结果全不同。这意味着插入失败的代价是 O(n)，必须在文档和接口中明确警示。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
