快五倍，和F1一样快！3354散列表N步起飞(2)

什么数据结构可以起到hashmap的作用？【答案】STD 3360: unordered _ map in STL
用STL和它的过度谨慎来回答，STL库当然很强大，功能很全面，代码写起来也很方便。
# include # include STD :3360 unordered _ map映射；但是，我们测试过，和真正的O(1)相差甚远。除了不可避免的不连续内存访问，它还能做什么？仔细看看unordered_map提供的API。除了常规的插入和删除，它还提供了一种bucket接口：buckets bucket _ count返回桶数(公共成员函数)。Max _ bucket _ count返回最大桶数(公共成员函数)bucket _ size返回桶大小(公共成员类型)bucket locate元素的桶(公共成员函数)这些接口提供了关于键的哈希信息。它显示该键被分配给了存储桶。如果多个键哈希值相同，那么它们返回的接口就是同一个桶。它以下列形式存储在存储桶中：
这样做的好处是添加和删除相对简单。一般检查后只需要从链表中删除一个元素或者在末尾添加一个元素，不会影响表的其余部分。这属于解决哈希冲突的【封闭寻址】。但缺点也很明显。即使bucket中基本没有碰撞，也需要遍历两个节点。少去一次，效果立竿见影。此外，转储头和链表的下一个节点都是间接寻址的，因此CPU缓存无法加载其后续数据节点以方便查询。优化这个，效果也是立竿见影的。所以——
既然swiss_table的开放答案需要更好的缓存亲和力，那不妨激进一点，改成【开放寻址】。同时，如果我们每次都进行eq运算来判断哈希值是否与现在存储的键的哈希值一致，那么哈希值可能就不需要存储了。3354重点一，情商操作。在swiss_table设计的talk中，作者详细分享了每种简化的利弊。下图是最终的简化形式：
我们去掉了所有的间接寻址，将这个值直接存储在链表中。此时，哈希表变成了线性探测序列。即使有哈希冲突，也可以一起加载到CPU缓存中，然后快速遍历。然而，要使它可用，我们仍然需要解决一些问题：
Bit:需要标记这个元素中是否有值，是否被删除，是否是同一个哈希值的范围。swiss_table给出的设计是一个字节的元数据：它用一个比特来表示状态，key的哈希值的后七个比特存储在最后几个比特，以减少哈希比较中3360的计算。
控制字节=(ctrl_t 7) | H2(哈希)
接下来是如何使用它：
截图中的代码描述了一个查找过程。对于一个键，先根据前57位计算它在链表中的位置，然后和ctrl中存储的掩码进行比较。如果两者相等，并且键和槽的存储位置相等，则意味着已经找到了这个值；如果哈希值不相等，则意味着与前一个哈希冲突的数字占据了这个位置。在线探针列表中，它总是占据第一个非空的位置，所以我们一直遍历。如果我们遇到空位置，说明这个键不存在；至此，hash_map的主体部分完成。
还有其他小技巧…使用SSE2指令集SSE2指令集可以用三条指令处理16个节点的内容。
减少临时变量的拷贝，构造上面两个图，是stl中常见的导致性能下降的写方法。因为键的类型和模板不一致，导致额外的复制和拷贝操作。这些可以在模板定义中进行优化。
通过首先寻址前57位(H1)，然后用后7位过滤(H2)来搜索强散列函数。如果哈希函数的前57位是倾斜的，会引起很多H1碰撞，如果后7位是倾斜的，会引起很多H2碰撞。不均匀的散列可能导致30倍的耗时。所以swiss_table重新实现了hashint和string的；其他类型使用哈希；std的；Swiss_table还试图将用户定义的哈希转换为强哈希。