去年看到字节跳动给golang提了issue建议把map的底层实现改成SwissTable的时候，我就有想写这篇博客了，不过因为种种原因一直拖着。
直到最近遇golang官方开始讨论为了是否要接受SwissTable作为map的默认实现，以及实际遇到了一个hashtable有关的问题，促使我重新思考了常见的hashtable算法，并决定写下这篇文章。
友情提示：本文不会从零教你写hashtable或者swisstable，并且需要你对hashtable有一点了解（至少用过且知道常用操作的时间复杂度）；文中给出的示例代码为了简单易懂，放弃了一些实现细节上的优化，所以会和一些现成的实现不一样，还请注意。
接下来我们先简单复习下hashtable，哈希表。
传统的哈希表
哈希表提供了一个key到对应value的映射，通过一个hash函数把key转换成某个“位置“，从这个位置上可以直接拿到我们想要的value，这就是哈希表的能力。
哈希表一般来说空间复杂度为O(n)，查找、插入、删除的平均时间复杂度是O(1)，最坏情况均为O(n)。
可见哈希表在理论上是个性能非常好的数据结构。事实上在大多数情况下也确实是这样。
在更进一步探讨之前，我们先要假设几个前提。
- 假设相同的数据作为key时计算出的hash结果总是一模一样的；而数据不同时（哪怕只有一个bit不同时）计算出的hash结果也会完全不同。
根据鸽巢原理，上述假设在真实世界里是不成立的，不过一般hash函数可产生的hash值的数量很大，通常比较难遇到不同数据产生相同hash的情况，所以这里我们暂且让这条假设成立。
- 对于hash函数产生的hash值，每一个bit都是随机的，且随机概率均等。
这条假设确保了不会有某些bit会有固定值或者某些值的权重比另一些高导致不平衡，工业级强度的hash函数一般都会尽量保证这条假设里提出的要求。
符合以上两条的我们认为它是一个“理想的hash函数”，这样的函数可以最高效的利用hashtable的内存并减少冲突。换句话说，有了这样的函数的话影响传统hashtable性能的就只有数据在内存中的组织方式了。这样也方便我们接下来的讨论。
不过hash函数再完美，把key映射到一个有限大小的内存空间内也还是不可避免得会产生冲突：两个不同的key会被映射到同一个位置。
为了解决这个问题，传统的hashtable有好几个解决方案，我们挑最常见的解决冲突的办法——“链表法”和“线性探测法”简单复习一下。
链表法
链表法是最常见的，它的中心思想在于如果key映射到了相同的位置，那么就把这些key和value存在一张链表里。
查找的时候先用hash函数计算得到位置，然后再从存放在该位置上的链表里一个个遍历找到key相等的条目。
它的结构类似这样：
淡蓝色的表示还没有元素存在。
这个是最原始的实现方式，实际上很多库不会每个位置（以后简称为slot）存一个链表，而是用一张大链表把每个有值存在的slot串联起来，这样可以节约n-1个头结点和n-1个为节点的内存。
还有一些库会在链表过长的时候把它转换成搜索树等时间复杂度更低的结构。所以总体来看拉链法实现的哈希表常用操作的平均时间复杂度都接近于O(1)。
优点：
- 实现很简单，没那么多边界条件要考虑
- 插入数据和删除数据很快，插入用链表的头插法，删除只需要移动部分节点的next指针
- 能采取扩容之外的手段阻止查询性能退化，比如前面提到的把过长链表转换成搜索树
- 保证了指针稳定性，所以可以放心地用指针去引用哈希表内的元素
缺点：
- 链表本身对缓存不够友好，冲突较多的时候缓存命中率较低从而影响性能。
- 不同的slot之间数据在内存里的跨度较大（即使是用大链表串联的情况下），数据结构整体的空间局部性较差
设计上的注意点：
- 为什么不同双链表？因为单链表够用了操作是有点麻烦还需额外的头节点，但双链表每个节点都会比单链表多出一个指针，会浪费比一个头结点更多的内存。
- 为什么不直接用vector？因为删除元素的时候vector需要移动大量元素，性能和指针稳定性上都得不到保证，不实用。
线性探测法
线性探测是另一种常见的哈希表冲突解决方法。
它解决冲突的方式于链表法不同，在遇到hash冲突的时候，它会从冲突的位置开始向后一个个查找，直到找到一个空位，或者没找到然后索引回到了冲突发生的位置，这时会进行扩容然后再重新执行上述插入流程。
查找也是一样的，首先通过hash函数计算得到元素应该在的位置，然后从这个位置开始一个个比较key是否相等，遇到被删除的元素就跳过，遇到空的slot就停止搜索，这表示元素不在这个哈希表中。
可以看到大多数操作都需要从某个位置开始一个个向后比较，这就是它得名线性探测的原因。
这种方法实现的hash表可以是一个数组，它的结构大致如下：
淡蓝色的仍然是没有元素的空位。值得注意的是虚线标记的被删除元素。
元素是不能直接删除后把slot设置为空的，那样会破坏查找的流程，例如上面图里如果把K2删了然后slot设置成空，那你就永远找不到K3了。所以需要把slot设置成“已删除”。
插入的时候可以复用“已删除”的slot，但需要先检查key是否存在，否则还是上面那个例子，删除K2后我们想插入一个K3，实际上K3已经存在，但因为他本身应该在的slot空了出来，如果不提前检查的话插入操作就会把新的K3存进错误的位置，此时一张哈希表里会有两个K3，数据混乱了。这里得批评下github上某本很受欢迎的算法书，它在给出的insert示例里没考虑这种问题，这导致了它给出的代码在一些情况下会导致错误的结果。
这里只是简单复习，更详细的代码实现可以看这篇。
时间复杂度上和链表法差不多，我们来看看优缺点：
优点：
- 对缓存友好，现在可以用数组或者vector之类的可以在内存里紧密排列的结构实现哈希表
- slot的利用率高，因为元素是存在slot里的，不过这也不全是好事，后面细说
- 相对来说更节约内存，当然是和最原始的链表法实现相比，和用大链表串联过的比优势不是很明显，原因在缺点里细说
缺点：
- 实现复杂，一个slot得分有元素、空、元素被删除三种状态
- hash冲突是连锁式的，一处冲突可能会连续影响多处，最终导致插入同样的数据，它扩容的次数会比链表法更多，最终可能会用掉更多的内存
- 因为冲突会造成后续插入和删除的连锁反应，所以查找过程退化到
O(n)的概率更大，而且没法像链表法那样把有大量冲突的地方转换成搜索树之类的结构 - 没有指针稳定性，这倒也不是太大的缺点，只有c++标准强制要求标准库的hashmap要有指针稳定性
因为删除元素麻烦，加上冲突会有连锁影响，所以很多库实现的hashtable都是用的链表法。不过即使有这么多缺点，光缓存友好和内存利用率高在现代计算机上就是非常大的性能优势了，所以像golang和python都会使用线性探测法的近似变种来实现哈希表。
SwissTable简介
我们复习了两种常见的哈希表实现，它们要么浪费内存且对缓存不友好；要么发生冲突后会更容易导致查找、插入、删除操作性能下降。这还是在有“完美哈希函数”的情况下，如果你用了个不那么好的哈希函数，那会导致key冲突的概率大大上升，性能