Cuckoo Hashing:最坏 O(1) 查找的优雅设计

传统哈希表的 O(1) 查找是'期望'——运气不好时,线性探测可能走 50 步。Cuckoo Hashing 给出了'确定性' O(1):最多查 2 次(或 d 次)就知道元素在不在。这个保证对网络设备中的精确匹配至关重要。

Swiss Table:Google 的 SIMD 加速哈希表

std::unordered_map 慢在哪里?每次查找跟着指针跳来跳去,缓存全部打飞。Google 的 Swiss Table 用 SSE2 一条指令并行比较 16 个槽位,把哈希表的探测从'逐个比较'变成了'批量筛选'。这篇文章从控制字节的位级设计讲到完整 C 实现,拆解这个替换了 Google 全部 C++ 哈希表的方案。

完美哈希:从理论到 gperf 实践

编译器怎么在 O(1) 时间内判断一个标识符是不是关键字?用哈希表?但普通哈希表有冲突,最坏情况退化成链表。完美哈希给出了确定性答案:对已知的 n 个键,构造一个完全无冲突的哈希函数,查找时间严格 O(1),空间 O(n)。这是静态字典问题的终极解法。