Algorithms_算法专项_Hash算法的原理&哈希冲突的解决办法

引导案例

案例一

问题: 有n个(1

假设有5个自然数： 4 ，50， 87，99，100

判断100， 在不在这5个数中

分析：

自然 —> 非负整数 ( 0 , 1 , 2 , 3 , 4 , … )

可以想到的几种方式 ： 排序（没必要）遍历、 数组（利用数组下标）…

遍历： 循环，判断每个数是否和目标数值相等，相等则退出循环，存在。

数组下标： 初始化一个能够容纳最大数据的int数组，数组中的值默认为0 ，然后把出现的这n个数的下标置为1，判断某个数是否存在—>直接判断这个数在数组中对应的下标是0还是1即可，1则存在，0 则不存在，那么查询的时间复杂度 O(1)，也不需要遍历。

很显然遍历的效率不如利用数组下标

解答：

拿上面的例子为例，

假设有5个自然数： 4 ，50， 87，99，100
判断100， 在不在这5个数中

初始化一个长度为100的int数组 (每个自然数的范围是1~100，100个数）

int[] arr = new int[100];

a[4]-->1 
a[50]-->1 
a[87]-->1 
a[99]-->1 
a[100]-->1 
其余的数组中的值为默认值 0 

判断a[100]是否存在，直接看下 a[100] 为 0 还是 1 即可。 （不用较真，数组下标从0开始，查看100，应该查看a[99], 重要的是思路）

案例二

思考： 案例一中的这种方式有什么弊端吗？

先来看下另外一个例子

问题: 有n个(1

假设这5个数为 999999,999999999,9999999999,9989898989

这个时候 ，你初始化一个 100亿的一个数组吗? 就为了存上面的5个数，显然是不合理的。

int 最多存21亿多，这100亿肯定存不下，当然了 你换成可以long型 , 但是这个空间浪费的是不是太多了… 肯定接收不了。

数据太大存不下，并且空间浪费太多 ，那该如何解决呢？ --------------> hash 就要登场了。

hash表（散列表）

散列表 , 英文 hash table .

hash table 就是利用数组支持按照下标随机访问数据的特性，对数组的一种扩展，从数组演化而来。 所以hash table 本质上就是一个数组。

数组支持下标随机访问特性，**查询时间复杂度是O(1)**这一个特性，就可以实现快速哦按段元素是否存在序列当中。

哈希函数(散列函数）

上面的例子我们也看到了，数据量巨大的时候，数组是放不下的，那就需要一种压缩方法，把这种数据压缩到一个可接收的范围内。

比如把 0~199 （largeNum）的压缩为 0到9(smallNum) ， 0到9 有10个数，所以smallRange = 10 ，

用个公式来表示的话就是

smallNum = largeNum % smallRange

上面这种取余的操作，就可以理解为是hash化,是hash函数的一种。

细看一下

假设N=10 （压到0到9的值）， 有下面几个数

11 ， 52 ，33 ，64 ，75 ，26 ，199…

对应上面的公式的话， smallRange = 10 ， 上面的这几个数字就是largeNum

我们来通过取余来计算下smallRange

11 % 10 = 1， 
52 % 10 = 2，
33 % 10 = 3 ，
64 % 10 = 4，
75 % 10 = 5，
26% 10 = 6 ，
199 % 10 = 9

我们是不是可以把 0 到 9 理解为数组下标 ？ 对的。

11 % 10 = 1，   =========> a[1]======>   代表 11 
52 % 10 = 2，  =========> a[2]======>  代表 52
33 % 10 = 3 ， =========> a[3]======>  代表 33
64 % 10 = 4，  =========> a[4]======>  代表 64
75 % 10 = 5，  =========> a[5]======>  代表 75
26% 10 = 6 ，  =========> a[6]======>  代表 26
199 % 10 = 9  =========> a[9]======>  代表 199

判断 199 是不是在 这几个数中，是不是就可以这样操作？

199 % 10 = 9 =======> a[9] ===⇒ 比对下a[9] = 199 ？ =====> 等于则存在，不等于则不存在。

哈希碰撞( 哈希冲突 )

到了这里，你可能已经发现问题了，这组数据当然是故意制作的，

11 ， 52 ，33 ，64 ，75 ，26 ，199......

数组下标没有冲突的…

如果是下面这组数字呢？

11 ， 52 ，22 ，42，75 ，26 ，199......

hash化处理一下如下：

11 % 10 = 1， 
52 % 10 = 2，
22 % 10 = 2 ，
42 % 10 = 2，
75 % 10 = 5，
26% 10 = 6 ，
199 % 10 = 9

可以知道 52 ， 22 ， 42 取余后 都是 2 ，那问题来了 a[2] 有多个值了，到底代表哪一个呢？

这种情况就称之为 哈希碰撞 或者 哈希冲突

如何解决hash冲突（hash碰撞）

开放寻址

核心思想： 在开放寻址法中，如果数据不能直接放在由hash函数计算出来的数组下标所指的单元时，就要寻找数组的其他位置。

根据在找下一个空白单元时使用的方法不同，又可以分为

• 线性探
• 二次探
• 二次哈希

线性探测(LP)

LP : LINEAR PROBING

我们以线性探测为例来看下 是如何实现开放寻址的

线性探测：在线性探测中，线性的查找空白单元，比如 数组下标 666 为要插入数据的位置，如果它已经被占用了，则继续探测667，依次类推，直到找到一个空位，这个就叫线性探测，因为它沿着数组的下标一步步的寻找空白单元

线性探测 示意图：

二次探测 （平方探测 QP）

QP：QUADRATIC PROBING

线性探测会发生聚集，如果hash化后的数据落到了聚集范围内的数据项，就要一步步的移动。

已填入hash表中的数据和表长的比率叫做装填因子，比如1万个单元的哈希表填入了3334个数据，那么它的装填因子就是1/3.

当装填因子不是很大的时候，聚集分布的比较连贯。 hash表的某部分可能包含大量的聚集，而另一部分还很稀疏。 聚集降低了hash表的性能。

二次探测主要是为了防止聚集的产生。核心思想：探测相隔较远的单元，而不是和原始位置相邻的单元。

步骤是步数的平方

举个例子：

在线性探测中，如果哈希函数计算出来的原始下标是x, 线性探测就是 x+1 , x+2 ,x+3 ,x+4,x+5…依次类推。

而在二次探测中，探测的过程则是 x+1 , x+4 ,x+9 x+16,x+25… 到原始位置的距离是步数的平方： x+1^2x+2^2x+3^2x+4^2x+5^2 …

当二次探测的搜索边长的时候，它好像变得很绝望。

• 第一次操作相邻单元
• 如果这个单元被占用，它认为这里可能有一个小的聚集，所以它尝试距离为4的单元
• 如果这里也被占用，它变得有些焦虑，它认为这里有个大的聚集，然后就尝试距离为9的单元
• 如果这里还是被占用了，它感到了一丝恐慌，跳到距离为16的单元，很快，它就会歇斯底里的飞跃整个数组空间 。
• 当hash表快满的时候，就会出现这种情况

二次探测消除了线性探测中产生的聚集问题，这种聚集被称为原始聚集，但是也产生了更细的聚集 ，被称为二次聚集。 二次聚集不是一个很严重的问题，因为不常用 。 有更好的解决方案------> rehash

再哈希法（DH）

DH： DOUBLE HASHING

为了消除原始聚集和二次聚集，可以使用 二次哈希 。

其实而此举既产生的原因是二次探测的算法产生的探测序列步长总是固定的： 1，4,9，16…依次类推。

核心思想： 需要产生一种依赖关键字的探测序列，而不是每个关键字都一样，那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。把关键字用不同的哈希函数再做一遍哈希化，用这个结果作为步长。对于指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长。

第二个哈希函数必须具备如下特点：

• 和第一个哈希函数不同
• 不能输出0（否则，将没有步长，每次探测都是原地踏步，算法将陷入死循环）。

使用如下的哈希函数工作的非常好：

stepSize = constant - key % constant;

其中constant是质数，且小于数组容量。

再哈希法要求表的容量是一个质数.

举个例子： 假如表长度为15(0-14)，非质数，有一个特定关键字映射到0，步长为5，则探测序列是0,5,10,0,5,10,以此类推一直循环下去。算法只尝试这三个单元，所以不可能找到某些空白单元，最终算法导致崩溃。

如果数组容量为13, 质数，探测序列最终会访问所有单元。即0,5,10,2,7,12,4,9,1,6,11,3,一直下去，只要表中有一个空位，就可以探测到它。

Q: 如果中间有个数据被删除了怎么办呢？

标记为 -1，否则的话就会出现数据缺失。 因为查找的时候，找到一个空位，就不找了，认为已经结束了，所以需要给删除的数据单元打标 。

链地址法

核心思想： 某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中。 其他同样映射到这个位置的数据项只需要加到链表中，不需要在原始的数组中寻找空位。

上述的这个模型就是JDK1.7 HashMap的原型。

再来看个极端的情况

Q: 如果中间有个数据被删除了怎么办呢？

可以删除，因为链表仅仅是个指针指向它而已。

算法可视化网站

https://visualgo.net/zh

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html