有什么数据结构可以发挥hashmap的功能呢？

$\color{blue}{【回答】} $STL里的std::unordered_map

用STL的回答和它的过分谨慎

STL库当然很强大，实现的功能也很全面，代码写起来也很方便。

#include <stdio.h>
#include <unordered_map>

std::unordered_map<int, int> map;

但是，我们测试过了，它离真正的O(1)还差很远。除了不可避免的不连续内存访问之外，它还做了什么？

仔细看看unordered_map提供的API，除了常规的插入和删除之外，它还提供了一类bucket接口：

Buckets

bucket_countReturn number of buckets (public member function)

max_bucket_countReturn maximum number of buckets (public member> function)

bucket_sizeReturn bucket size (public member type)

bucketLocate element’s bucket (public member function)

这些接口提供了关于key的hash信息。它表明，key是分到bucket里的。如果多个key hash值相同，那么它们返回的接口是同一个bucket。

它在bucket里存储的形式如下：

这样的优点在于增删都比较简单。一般情况下，查到以后，只需要从链表里删除一个元素，或者在末尾添加一个元素即可，不会影响表的其他部分。这属于解决hash冲突的$\color{blue}{【封闭式寻址】}$。

但是缺点也很明显。哪怕bucket里基本没什么碰撞，也需要遍历两个节点。如果去掉一次访问，效果必然立竿见影。此外，dump-head和链表的下一个节点都是间接寻址，CPU缓存无法载入它后续的数据节点方便查询。能优化这一点，效果同样立竿见影。

所以 ——

swiss_table的开放式回答

既然需要更好的缓存亲和性，那么不妨激进一些，改为$\color{blue}{【开放式寻址】}，同时，如果我们每次都执行eq操作来判断hash值和现在存储的key的hash是否一致，那hash值也可以不必存储。

在swiss_table设计的talk中，作者详细分享了每个简化能带来什么收益，会带来什么损耗。下图就是最终简化出来的形态：

我们去掉了所有的间接寻址，直接在链表里存储这个值。这时hash表就变成了$\color{blue}{【线性探测表(probing sequence)】}$。

这样即使有hash冲突，它们也可以一起被加载进CPU的缓存中，然后被快速地遍历。

不过要让它变为可用的东西，我们还需要解决一些问题：

• 标记位：需要标记这个element中是否有值，是否被删除，是否是同一个hash值的范围。

swiss_table给出的设计是1个byte的meta-data：

它用一个bit表示状态，后几位则存储了key的hash值的后7个bit，以减少hash比较时的计算:

control_byte = (ctrl_t << 7) | H2(hash)

接下来就到了如何使用了：

截图中的代码描述了一个find的过程。对一个key，先根据前57个bit算出在链表中的位置，然后和ctrl里存储的mask比较，如果二者相等，且key和slots存储的位置相等，那说明找到了这个值；如果hash值不相等，那说明前面hash冲突的数字占据了这个位置。在线性探查表里，它总会占据第一个非空的位置，所以我们一直遍历下去，如果遇到空的位置，就说明这个key确实不存在；

至此，hash_map原理上的部分就完成了。

还有其他的机锋

使用SSE2指令集

SSE2指令集可以在三条指令中处理16个node的内容。

减少临时变量的拷贝和构造

以上两图都是stl中常见的导致性能下降的写法。因为key的类型与模板不一致，导致了额外的拷贝和复制操作。这些可以在模板定义中优化。

强hash函数

因为查找的方式是一开始根据前57个bit寻址（H1)，然后用后7个bit加以过滤(H2)。如果hash函数的前57bit有倾斜，会造成大量的H1-冲突，如果后7位有倾斜，则会造成大量的H2-冲突。不均匀的hash可能导致30倍的耗时。

因此swiss_table重新实现了int和string的hash；其他的类型则使用std的hash；对用户自定义的hash，swiss_table也尝试把它变成强hash。