Hash 概念

Hash ，一般叫哈希或者散列。它可以把任意长度的输入，通过散列算法，变换成固定长度的输出，输出值我们一般叫散列值。

如果散列值不同，那么输入值也肯定不一样，而两个输入值不同，输出的散列值可能会相同，这种现象叫碰撞，也就是 Hash 冲突。

Hash函数

主要有以下几个

f(k) = k + c

如集合 [5,8,7,6] 对应的关键字 key 为 [5+c,8+c,7+c,6+c]

该散列函数优点就是简单，不会产生冲突，缺点就是占用空间大，需要事先知道关键字的分布情况，一般适合査找表较小且连续的情况。由于这样的限制，在现实应用中，直接定址法虽然简单，但却并不常用。

2. 数字分析法

f(k)=f(d0d1d2…d6d7)=d4d7

f[5,5,5,6,7,3,7,7] -> 63

3. 除留余数法

f( k ) = k % p ( p ≤ m )

实践证明，当P取小于哈希表长m的最大质数时（最好接近m)，产生的哈希函数较好。

如 某散列表的长度为100，散列函数 f( k ) = k % p ( p ≤ m )

最大质数为 97 。则 P 为 97 。

4.  分段叠加法

1  2  3                   1  2   3

6  0  3                   3  0   6

2  4  7                   2  4   7

1  1  2                   2  1   1

0  2  0                   0  2   0

————————          —————————

1  1  0  5                 9  0   7

5. 平法取中法

例如：

6. 伪随机法

采用一个伪随机数当作哈希函数。

f(k)=random(k)。

解决碰撞冲突的方法

计算 key = 37 时，发现 f(37) = 1，此时就与 25 所在的位置冲突。

于是我们应用上面的公式 f(37) = (f(37)+1) mod 12 = 2。于是将 37 存入下标为 2 的位置。 

3. 在哈希法

4. 建立公共溢出区

将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。