这个算法由google开源，最早在2017年的c++大会上分享过。
文章概览
效果
hash表的实现，实在是太经典太没什么新意了，但是这个数据结构又是用得太多太基础的组件了，如果有人能够把hashtable做的更快，实在也没理由拒绝。Google实现的这个hash表的性能，请看下图：
(图片引用了Zhihu 流左沙文章内图片)
各种情况下，swisstable比std::unordered_set至少快两倍！！！
对比std::unordered_map
hash表通常号称O(1)的时间复杂度，但是在hash冲突存在的情况下，往往达不到O(1)的时间复杂度。
众所周知(我最喜欢问的面试题)，解决hash冲突有以下经典的三种方式：
- 开放地址法
- 相邻地址法
- 多散列函数法
重点在于，std::unordered_map使用开放地址法来解决hash冲突。
链表最大的问题就在于——在当代的CPU架构下，内存比SSD快100倍，而cpu cache又比内存快100倍，链表对于CPU cache并不友好。因此，cache友好的结构能够提升性能。
关键设计
Swiss table的关键设计就是——通过相邻地址法来解决hash冲突。一个平坦的内存结构，能够提高cpu cache命中率。
因此，具体的设计细节，都是针对相邻地址法解决hash冲突的具体办法。
大致结构
swiss hash的大致结构可以表述如下：
hashcode
通过在key上执行hash函数，得到一个64位的hash值。
把hash值分为高7位和低57位：
- 低57位用于定位桶中slot的位置
- 高7位用于在control byte中解决hash冲突
control byte
hash桶中每个slot对应一个1一个byte的控制字节。
Control byte的高1位用于表示状态，低7位用于存储hashcode的高7位。
状态位分为：
- 未使用：0xFF表示（全为1）
- 已删除：0x80表示（最高位为1，其余位为0）
- 在使用：0x00~0x7F之间的值（最高位为1）
group概念
以128bit对齐的连续8字节的control byte称为一个group。
解决hash冲突通常在slot对应的control byte所在的group内解决。
以128bit对齐的原因是，group内的搜索，可以用四条SIMD指令来解决。
展望
- 搜索了一下，目前还没有golang版本的swiss table，后续准备实现一个
- Flat hashtable不仅仅只是CPU CACHE友好，这样的结构配合原子操作，相信很容易做出一个并发版本的hash table。后续也准备在这里做一些尝试。
- 算法的优化进入深水区了：
- 与当下的CPU架构结合起来，很多经典算法能够老树开新花
- 假设当前使用的是苹果的M1芯片，那么经典算法可能在异构计算的体系里产生更多令人惊异的提升。