前言
全篇无代码，讲的都是死思路奥awa。
理解哈希表（HashTable）的原理是关键。
首先要明白，我们用哈希表来干什么？
存储并且查找数据。
哈希函数
假设有(n)个数值最大为(k)的数字，(m)次查询是否存在某个数字。
Round 1
先想一想常规操作。当(n,k,m)都比较小的时候我们会怎么实现？
直接开数组存啊！然后查找直接暴力(for)就好了。
Round 2
这时我们把(n)的范围调大一点，让上面的暴力做法只能够(TLE)，该怎么办呢？
我们就开一个(bool)数组判断每个数是否有出现。
Round 3
但是如果数据不多，但是数值很大呢？比如(1≤n,m≤1000,1≤k≤1e12)。
在这样的条件下，我们不能开出这么大的数组，怎么办呢？可以通过一个(map<long long,bool>)来解决。或者通过离散化也可以达到同样的效果。
Round 4
但是，(3)中的映射读取的时间复杂度为(O(logn))，总时间复杂度达到了(O(mlogn))，数据更强一点会被卡掉。
此时，就需要引入我们的hash表了。
hash表所需要的，是一个足够使用的哈希函数（散列函数），在关键字（(key)）与数值之间建立一个映射（非map），让我们可以进行双向查找。并且这个查找的时间需要尽量的短。
基本思路是：为这(n)个数据开一个(len)大的数组((len≥n))，然后用我们的哈希函数为每个值算出一个下标，并且这个计算过程需要是可逆的。存起来就好了。
哈希函数的实现一般都是通过取模来完成的。比如下面这个例子。
现在有四个数，(13,7,14,11)，假设我们设计的哈希函数为(hash(i)=i%5)。
hash(13)=13%5=3,h[3]=13;
hash(7)=7%5=2,h[2]=7;
hash(14)=14%5=4,h[4]=14;
hash(11)=11%5=1,h[1]=11;
哈希的方便之处，是在查询的时候体现的。这个时候，加入我要查询数字14是否在数组中，不需要循环，只需要算出14对应的关键字为14%5=4，确认h[4]=14，返回即可。查询的理论时间复杂度为(O(1))。
而这里的模数5，在实际问题中可以替换为适当的值，但一定要是质数。
哈希冲突
在具体的例子中，可能会出现哈希冲突。即a[i]!=a[j]但hash(a[i])==hash(b[i])的情况，下面就来讲讲如何解决哈希冲突。
对于上面的例子，很幸运的，没有出现一例哈希冲突。但如果我们再在这个哈希表中加入数字8，经过计算应该把h[3]=8，但是我们发现，这个位置已经被使用了，怎么办？
这个时候我们就需要让这个hash函数不再只会像我一样无脑%%%，需要给它添加上一个尽量避免哈希冲突的功能。
常用的分为两种，分别是链地址法(开链法,拉链法,哈希桶)与开放地址法
链地址法
所谓链地址法，就是当发生hash冲突的时候，将冲突的数据作为链表的形式存储。
举个栗子，就像这样：
这样操作虽然让分散的几次哈希冲突影响不那么大，但如果多次冲突都聚集在同一个位置，链表的位置就会过长，浪费时间。
具体实现类比前向星，就不放代码了。
开放地址法
在这种方法中，如果一个位置发生了哈希冲突，那么就另外寻找一个位置放下。寻找的方式常用的分三种：线性探测法，二次探测散列法，双哈希法。
线性探测法
法如其名，这种方法就是开放地址法中的暴力。它的思想是如果当前位置发生了哈希冲突，那就尝试后一个位置，直到成功为止。这样虽然暴力，但是如果有连续的哈希冲突，会在插入和查询上都花费过多的时间来进行循环。
线性探测的查找：先通过键值定位到数组下标位置，然后将这个位置上数据的值和你要查找数据的值对比，如果相等就直接找到了，如果不相等则继续判断下个元素，所有元素遍历完都没找到的话，则不存在。
这种方法不推荐使用，一旦数据刚好在你设定的模数下在相同位置发生大量冲突，直接(T)上天！
二次探测散列法
这个名字看起来很高级，实际上只是对线性探测法进行了一些优化。
线性探测法把每一步的步长(d[i])都设定为1，而二次探测散列法则是设定(d[]={1^2,-1^2,2^2,-2^2...})，依次类推。
简单来说，就是以发生冲突的位置为中心点，左右横跳直到找到一个合适的位置。这样的话就避免发生一个区间都被占满的情况发生。但是经过研究，数列长度是质数&&剩余空间>50%的时候，新的项一定能被插入，并且一个位置不会被探测两次，所以双倍空间&&质数长度数列就很有用啦。
双哈希法（再哈希法）
虽然二次探测散列法能够很大程度上避免原始聚集问题，但是又不可避免地产生了新的二次聚集问题。问题发生的原因是，不管是线性探测还是二次探测，对于不同的原始值，产生的步长是一定的。
而双哈希法则不同。第一次哈希和原来没有区别，第二次哈希的模数就需要较小，用来生成对应的步长。设一个比列表长度小的质数为(cons)，则比较好的二次哈希函数形式为：step=cons-(ket%cons)。
需要注意的是，输出一定不能为0并且不与第一次哈希相同。上面的形式完全符合。
双哈希法的核心思想是，第二次哈希生成一个随机的步长。
ov.