这一章大概是一个 hash tables 的科普。因为刚上课不久 andy 就说我们自己不会去实现一个这玩意儿。现在有非常优秀的方案，你应该去使用那个最好的方案，那个方案把其他方案都给碾碎了。我们当然就应该使用它。
xxhash 是之前搞 zstd 的 facebook 哥们搞的。这俩玩意儿一个是最好的压缩算法之一，一个是最好的 hash 算法。
这里 hash 算法谈论好，我们暂时忽略加密性能，单纯从我们一个 input 到输出一个固定长度，最少碰撞的角度去说
可以看到 xxhash 在 > 64byte key 的情况下约比 google 的 cityhash 快约 3倍。。
STATIC HASHING SCHEMES
首先所有静态冲突检测都基于一个原则，如果我们发现不过怎么检测都无法再插入值的时候，我们可以扩大哈希表本身，比如 *2 ，先将之前的值拷贝过去，然后再重新为之前造成死循环的值寻找新的位置。
1. 线性 hash 表，解决冲突的模式还比较好理解。我们使用 hash 函数对值进行计算，然后找到对应的槽放置数据。如果有冲突了需要继续沿着槽顺序检查下一个槽是否有数据，
如果没有就放置。
那么这种方案如果遇到中间被删除了一个元素，顺序查找被打断又该如何，有两种方案
1. 全部重新算一次，将对应的数据重新放置回对应的问题。
2. 使用墓碑标记，标记被删除掉的位置。这样在扫描的时候就知道这里的不连续十因为数据删除，那么可以继续向下查找对应值。
2. 线性 hash 表变种 robin hood hashing 它改进了冲突检查的机制。
简单的来说它尝试让发生冲突的 key 不要距离原始冲突位置太远，以此来避免一些极端情况。比如某个 key 因为周围 slot 都满的情况下被调配得距离原始冲突位置过于远。
3. cuckoo hashing 使用两个不同的哈希函数来避免冲突。在一个线程中，先做第一个 hash ，如果无冲突就放进去。如果有冲突就做第二个 hash，如果无冲突就放进去，如果还是有冲突就盗取该位置，并且将该位置的值重新拿去计算 hash 直到找到一个第二个 hash 计算位置的值并放入右边。拿冲突位置的 key 去看是第一个 hash 函数产生的还是 第二个 hash 函数参数产生的。如果最后死循环了，就得扩大 hash 表重新计算
DYNAMICS HASHING SCHEMES
1. 链 hashing，如果发生冲突我们会借助一个链表来存储重复位置的 key。
2. 扩展 hashing，基于链 hashing 的一个变种。
3. 线性 hashing，基于链 hashing 的一个变种。
Reference:
https://www.bilibili.com/video/BV1xa41137S4?p=7&vd_source=d05baeb2783257f3e6b27121e7a796a0
https://github.com/facebook/zstd
https://github.com/Cyan4973/xxHash
标签：hash,memo,位置,tabels,冲突,key,如果,Hash,hashing From： https://www.cnblogs.com/piperck/p/16887864.html