Hash Table
Hash Table构成
1.一个Hash Table提供平均O(1)的时间复杂度和O(n)的空间复杂度。常数对数据库影响非常大。
2.一个Hash Table由Hash Function和Hashing Scheme组成，前者是将给定的对象计算出一个hash值，后者是用来处理如何存hash值和以及发生冲突时的处理方法。Hash Function一般用现成的，最快的是Facebook XXHash3
Static Hashing Schemes
静态hash是假设我们一开始就知道需要hash的元素个数，并且hash table的大小是固定不变的。如果overflow了，就需要对整个hash table进行rebuild。
Linear Probe Hashing
1.这是一种用的比较多而且是最快的hashing scheme。在一个table中存hash值和value的pair。如果现在要插入一个元素，直接计算Hash值然后mod table的大小，如果对应的位置没有被存储，就直接存pair上去。否则遍历这个位置周围的pair，直到找到一个空位或者找到一个pair这个pair的原始hash值和这个要插入的hash值相同，放到这个位置上去。查找也是在相邻的位置处查找。
2.整个table是circular的。首位相连。
3.对于删除操作比较麻烦，最简单的方法是放一个tombstone，即表示table的这个位置被占用了，但是上面的元素已经被删除了，所以要继续遍历它相邻的元素。但是这样会造成空间的浪费，如果只是使用tombstone，就需要在一段时间后对整个hash table进行rebuild。另一种方法是把相邻元素进行move，实现起来比较复杂。
4.如果一个key可以对应到多个value，那么直接把这个key-value对放置多份即可，也就是说放key-value1,key-value2等等，当然也可以让每个key指向一个table，这个table中存所有对应的value。
Robin Hood Hashing
给每个元素附加另外一个distance，即偏离原来应该插入的位置多远。当这个元素要存的位置上已经被占了，就将两个元素的distance进行比较，让distance小的挪走。然而这种distance均衡的策略不一定适合所有情况，并且大量的条件判断对效率影响非常大，几乎不用。
Cuckoo Hashing
对一个值用两个hash函数，建两个hash table。插入的时候如果其中一个hash table是空的就直接插入，如果都是空的就随机选一个，如果都满了就随便找一个被占位置上的元素，让这个元素重新插入到另外一张表中，这样不断重复下去。如果到最后都还剩下一个元素没有插入，就需要对整张hash table进行重建，insert的时间复杂度高，但是查询和删除几乎都是O(1)的。
Dynamic Hashing
Chained Hashing
是最常用的一种hash方式。对table的每个位置建一个链表。缺点是链表可能会很长。
Extendible Hashing
https://zhuanlan.zhihu.com/p/467044503
Linear Hashing
1.一开始设定一个范围n，每插入一个元素就对n取模，映射到0~n-1这个范围区间内，其中每个位置都会存一个指针指向自己管的一个table。有一个split pointer一开始指向映射表的0号位置。
2.如果我们要插入一个元素到一个table中，这个table已经满了，就在这个table后面再建一个table，用链表串起来。然后要进行重排，但是这里不选择这个满的table进行重排，而是专门选择split point指向的table进行重排。重排的方式是将mod 的n变成mod 2n，对要重排的table中的每个元素重新进行一次hash然后放到新的table中。
3.多overflow几次后就会有新的hash函数，我们可以对每个hash函数的使用划定一个分界线（split pointer指定的），如果用第一个hash映射到的值在第一个分界线内（也就是在split pointer之上），说明所在区域进行了重新hash，那么就需要用第二个hash函数。
4.删除操作完全就是逆过来的。