哈希表内部：开放寻址、链式、Robin Hood 的三国演义
Go 的 map 用的是什么哈希表？Rust 的 HashMap 呢？Python 的 dict 呢？它们分别选了三条完全不同的路线——链式哈希、Swiss Table、开放寻址。选择背后的 trade-off 远比你想象的深。
hash-table 标签归档
共 3 篇文章 · 返回首页
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++ 哈希表的方案。