哈希算法教程

一、哈希函数

哈希函数的实质，就是把一个键值空间为$K$的映射到哈希表的空间$T$中。
哈希函数的设计有两个主要的要去：
(1)哈希函数计算要快，效率要高，即哈希的计算公式要比较简单，不要太复杂。
(2)哈希函数的冲突率要低。
哈希冲突指的是两个不同键值$k_1$和$k_2$，但是$h(k_1)=h(k_2)$，这就造成了冲突。
这里我们定义一个负载因子（装填因子）：$l=t/h$，其中$t$是代表哈希表中已经被填好的槽，$h$是哈希表的总槽数。很明显，当$l$接近于$1$的时候，冲突是不可避免的。
为了避免冲突，有三种解决方案：
1.把哈希表的大小开的足够大，比键值空间$K$的范围大得多
2.采用拉链法.
3.选择一个完美哈希函数，是一一对应的。
补充了解：哈希冲突有$4$种解决方法，大概了解一下名称即可。
(1)开放定址法
(2)再哈希法(多个哈希函数，嵌套使用)
(3)链地址法(即上面说的拉链法，竞赛主要用这种)
(4)建立公共溢出区
回到之前说的$3$种解决方法：
方法1：设哈希表中实际被填满的槽为$A$，$A$是$K$的子集，则有$|A|<c|T|$，实验效果发现，$c$取$1/2$到$3/4$
之间比较好。
方法2：拉链法(链式前向星)，如有冲突，直接连接即可
方法3：所谓的完美一一对应的哈希函数，其实主要是由目标数据和可用内存空间两个一起决定的
举个简单例子，$h(k)=k$肯定是一个完美哈希函数，不过你的内存是不是能够把它们都保存下来就不一定了。

二、哈希表的大小为何是素数(通俗版)

1.选取数列
数列的选取很重要，之前看到有些文章将验证的数列间隔选为1，发现素数与合数并没有什么区别，这是因为素数与合数最大的区别不是间隔为$1$，我们首先看一下素数与合数的关键点：
素数只有两个因子，$1$和本身。
合数至少有$3$个因子，$1$，本身，其他因子。
素数与合数有公因子$1$。
​ 看到这里，我们可以做这样的一个假设，取模运算的冲突与因子相关，但是具体是如何相关呢，我们后面来实际验证一下，首先验证一下与因子相关；

数列1（因子2）：  
​ 1，3，5，7，9，11，13，15，17  
数列2（因子2）：  
​ 2，4，6，8，10，12，14，16，18  
数列3（因子3）：  
​ 1，4，7，10，13，16，19，22，25，28  
数列4（因子6）：  
​ 1，7，13，19，25，31，37，43，49  
数列5（因子7）：  
​ 1，8，15，22，29，36，43，50，57  

上面我们根据6，7的因子，取了5个数列，数列1与数列2取因子2，分别用奇偶数表示，用来验证因子与取模运算是否是相关的；
​ 然后再取后面的3个数列，验证另一个假设，数列的分布以因子为间隔。
2.检验
数列1(1，3，5，7，9，11，13，15，17)=> 取模6

2是6的因子，数列1产生了冲突  
​ 上面我们通过取模运算，发现如果待存数据如果是以2为间隔的话，那么取模6就会有很多冲突，分布不均匀，0，2，4都没有存储，1，3，5冲突很多；  

数列1(1，3，5，7，9，11，13，15，17)=> 取模7

2不是7的因子，数列1分布均匀  
​ 然后通过将模取为7，发现同样的数列1，这时候冲突减少，并且分布均匀，因为我们取的是奇数列，再使用偶数列验证是否是这样；  

数列2(2，4，6，8，10，12，14，16，18)=> 取模6

2为6的因子，分布不均匀  

数列2(2，4，6，8，10，12，14，16，18)=> 取模7

2不是7的因子，分布均匀  

​ 通过上面的取模运算，我们发现，因子确实会影响数列的冲突，并且冲突的间隔就是因子大小，下面再通过其他数列，看一下是否是这样；
数列3(1，4，7，10，13，16，19，22，25，28)=> 取模6

3是6的因子，分布不均匀  

数列3(1，4，7，10，13，16，19，22，25，28)=> 取模7

3不是7的因子，分布均匀  

数列4(1，7，13，19，25，31，37，43，49)=> 取模6

6是6的因子，分布不均匀，分部间隔为6  

数列4(1，7，13，19，25，31，37，43，49)=> 取模7

6不是7的因子，分布均匀  

数列5( 1，8，15，22，29，36，43，50，57)=> 取模6

7不是6的因子，分布均匀  

数列5( 1，8，15，22，29，36，43，50，57)=> 取模7

7是7的因子，分布不均匀，分布间隔为7  

3.结论
根据上面的结果，我们来分析一般性结论：
​ 哈希表中的分布按照数列的间隔进行分隔，如果数列的间隔恰好整除模，也就是模的因子，那么就会哈希表的分布就会产生间隔，恰好是数列的间隔。
​ 由此得到下面的结论：
如果有一个数列$s$，间隔为$1$，那么不管模数为几，都是均匀分布的，因为间隔为$1$是最小单位
如果一个数列$s$，间隔为模本身，那么在哈希表中的分布仅占有其中的一列，也就是处处冲突
数列的冲突分布间隔为因子大小，同样的随机数列，因子越多，冲突的可能性就越大
通过上面的分析，现在就很明确了，如果给我们随机的数列放到哈希表中，如何保障它能尽量减少冲突呢，就需要模的因子最少，而因子最少的就是素数了，这就是为什么哈希表取模为素数的原因了。

三、哈希表的大小为何是素数(数学证明)

假设需要放入长为$m$的$hash$表的数是$n$，取模函数是：$f(n)=n\mathrm{\%}m$，$f(n)$为需要放置在$hash$表中的位置的下标。取$m$为质数的目的是：让$m$和$n$的最大公约数为$1$，也就是：$gcd(m,n)=1$ 。因为在$m$为质数时，除非$n$恰好是$m$的倍数，否则他们的最大公约数都为$1$。为什么要$gcd(m,n)=1$ ?
$f(n)=n\mathrm{\%}m$
$=>a\ast m+f(n)=n(a=0,1,2,3,...)$
$=>f(n)=n-a\ast m$
$=>f(n)=gcd(m,n)\ast (\frac{n}{gcd(m,n)}-\frac{a\ast m}{gcd(m,n)})$
也就是我们算出来的$hash$值只可能是为$gcd(m,n)$ 的倍数的那些值，这显然不满足于我们希望$hash$值可以取$[0,m-1]$ 任意数的愿望。当数目过多时，这些$gcd(m,n)$ 倍数的$hash$值被用的多，其它数少，这就让分布不均匀，冲突次数增加。

四、链式前向星实现拉链法的一个模板

struct hash_map {  // 哈希表模板  
  struct data {  
    long long u;  
    int v, nex;  
  };                // 前向星结构  
  data e[SZ << 1];  // SZ 是 const int 表示大小, SZ为质数  
  int h[SZ], cnt;  
  int hash(long long u) { return u % SZ; }  //哈希函数  
  int& operator[](long long u) {  
    int hu = hash(u);  // 获取头指针  
    for (int i = h[hu]; i; i = e[i].nex)  
      if (e[i].u == u) return e[i].v;  
    return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;  
  }  
  hash_map() {  
    cnt = 0;  
    memset(h, 0, sizeof(h));  
  }  
};