主流的hash算法概述及在JDK Map中的应用

r囧r小猫 2022-05-24 05:14 230阅读 0赞

#### hash算法的应用场景 ####

Java中的Map实际是一个“散列表”的数据结构，散列表是逻辑上由一系列可存放词条(或其引用)的单元组成，故这些单元也称作桶(bucket) —— 一般都使用线性表来实现。

一组词条在散列表内部的具体分布，取决于所谓的散列(hashing)方案：事先在词条与桶地址之间约定的某种映射关系，可描述为从关键码空间到桶数组地址空间的函数: hash() 。

这里的hash()称作散列函数(hash function)。反过来，hash(key)也称作key的散列地  
址(hashing address)，亦即与关键码key相对应的桶在散列表中的位置。

所有散列函数都有如下一个基本特性：**根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。**对于java而言即如果 hashcode方法返回相同，equals方法不一样返回相同。但equals方法返回相同，则hashcode必须相同。

最佳的情况是充分利用有限的散列表空间，即散列函数最好是满射(定义域R与散列表的单元一一对应)。

当然，因定义域规模R远远大于散列表空间规模，散列函数不可能是单射。这就意味着，关键码不同的词条被映射到同一散列地址的情况称作散列冲突(collision)。

#### 主流的hash算法有如下： ####

> **除余法：**   
> 将散列表长度M取作为素数(只有为素数才能让其分布更加均匀[http://zhaox.github.io/algorithm/2015/06/29/hash][http_zhaox.github.io_algorithm_2015_06_29_hash])，并将关键码key映射至key关于M整除的余数: hash(key) = key % M

--------------------

> **MAD法：**  
> 除余法的劣势：残留有某种连续性。相邻关键码所对应的散列地址，总是彼此 相邻;极小的关键码，通常都被集中映射到散列表的起始区段。而0其散列地址总是0，而与散列表长度无关为弥补这一不足，可采用所谓的MAD法将关键码key映射为:  
> (a \*key + b ) % M，其中M仍为素数，a > 0，b > 0，且a mod M != 0  
> 尽管运算量略有增加，但只要常数a和b选取得当，MAD法可以很好地克服除余法原有的连续 性缺陷。除余法，也可以看做是MAD法取a = 1和b = 0的特殊情况。

--------------------

> **数字分析法(selecting digits)：**  
> 从关键码key特定进制的展开中抽取出特定的若干位，构成一个整型地址。比如，若取十进制展开中的奇数位： hash(123456789) = 13579  
> 又比如：关键码的二进制展开分割成等宽的若干段，经异或运算得到散列地址  
> 当然，为保证上述函数取值落在合法的散列地址空间以内，通常都还需要对散列表长度M再  
> 做一次取余运算。

--------------------

> **(伪)随机数法：**   
> 直接采用一个伪随机数当作哈希函数。

#### hash碰撞的解决方案 ####

衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及发生碰撞的解决方案。无论散列函数设计得如何巧妙，也不可能保证不同的关键码之间互不冲突。常见的解决碰撞的方法有以下几种：

**封闭定址/开散列**

> **独立链(separate chaining)法/独立链法 :**   
> 最直截了当的一种对策是，将彼此冲突的每一组词条组织为一个线性表，分别存放于它们共同对应的桶单元中。  
> 各桶内相互冲突的词条串接成一个列表，故命名为separate chaining

--------------------

> **公共溢出区法：**  
> 在原散列表之外另设一个词典结构Doverflow，一旦在插入词条时发生冲突就将该词条转存至Doverflow中。  
> Doverflow相当于一个存放冲突词条的公共缓冲池，该方法也因此得名。此时的散列表也可理解为是一种递归形式的散列表。

尽管就逻辑结构而言，独立链等策略便捷而紧凑，但绝非上策。比如，因需要引入次级关联 结构，实现相关算法的代码自身的复杂程度和出错概率都将加大大增加。反过来，因不能保证物 理上的关联性，对于稍大规模的词条集，查找过程中将需做更多的I/O操作。

**开放定址/闭散列**

实际上，仅仅依靠基本的散列表结构，且就地排解冲突，反而是更好的选择。也就是说，若 新词条与已有词条冲突，则只允许在散列表内部为其寻找另一空桶。如此，各桶并非注定只能存 放特定的一组词条;从理论上讲，每个桶单元都有可能存放任一词条。**因为散列地址空间对所有词条开放，故这一新的策略亦称作开放定址(open addressing);同时，因可用的散列地址仅限于散列表所覆盖的范围之内，故亦称作闭散列(closed hashing)。**

> **线性试探(linear probing)法：**  
> 开放定址策略最基本的一种形式是:在插 入关键码key时，若发现桶单元ht\[hash(key)\]已被占用，则 转而试探桶单元ht\[hash(key) + 1\];若ht\[hash(key) + 1\] 也被占用，则继续试探ht\[hash(key) + 2\];…;如此不断， 直到发现一个可用空桶。当然，为确保桶地址的合法，最后还 需统一对M取模。因此准确地，第i次试探的桶单元应为:  
> 如此，被试探的桶单元在物理空间上依次连贯，其地址构成等差数列，该方法由此得名。

--------------------

> **平方试探(quadratic probing)法：**  
> 线性试探法虽然简明紧凑，但各查找链均由物理地址连续的桶单元组成，因而会加剧关键码的聚集趋势。  
> MAD法，可在一定程度上缓解上述聚集现象。而平方试探法，则是更为有效的一种方法。  
> 具体地，在试探过程中若连续发生冲突，则按如下规则确定第j次试探的桶地址: (hash(key) + j2) mod M, j = 0, 1, 2, …  
> 各次试探的位置到起始位置的距离，以平方速率增长，该方法因此得名。

#### JDK Map中的Hash算法 ####

**HashMap**

hash方法的功能是根据Key来定位这个K-V在链表数组中的位置的。也就是hash方法的输入应该是个Object类型的Key，输出应该是个int类型的数组下标。  
调用Object对象的hashCode()方法，该方法会返回一个整数，然后用这个数对HashMap或者HashTable的容量进行取模就行了。没错，其实基本原理就是这个，只不过，在具体实现上，由两个方法`int hash(Object k)`和`int indexFor(int h, int length)`来实现。但是考虑到效率等问题，HashMap的实现会稍微复杂一点。

hash(Object k) ：该方法主要是将Object转换成一个整型，该方法有一些列复杂的位运算即对hashCode进行扰动计算。目的是防止不同hashCode的高位不同但低位相同导致的hash冲突。  
indexFor(int h, int length) ：该方法主要是将hash生成的整型转换成链表数组中的下标。

`indexFor(int h, int length)`方法使用了一个巧妙的性能提升点：  
`X % 2^n = X & (2^n – 1)`

位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。以及解决负数的问题 2^n – 1 的最高位一定是0，得到的结果一定是个正数

所以HashMap.indexFor 使用了 & 。并且默认长度(一定是个偶数)为2^4 = 16 ，每次扩容\*2后也一定是个偶数。

**HashTable**

HashTable的默认长度是 11 与HashMap默认为偶数不一样。HashTable每次扩容后也一定是奇数：2n+1。

hashTable的定址，在解决的key的负数问题后直接对长度取模。对奇数取模使得其分布更加均匀(详见：[http://zhaox.github.io/algorithm/2015/06/29/hash][http_zhaox.github.io_algorithm_2015_06_29_hash])。

ConcurrentHashMap与HashMap区别不大，都是通过位运算代替取模，然后再对hashcode进行扰动（防止不同hashCode的高位不同但低位相同导致的hash冲突。）。区别在于，ConcurrentHashMap 使用了一种变种的Wang/Jenkins 哈希算法，其主要母的也是为了把高位和低位组合在一起，避免发生冲突。

**JDK8 中的变化**

HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。**在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时hashmap性能降低的问题，Java 8中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。**

如果恶意程序知道我们用的是Hash算法，则在纯链表情况下，它能够发送大量请求导致哈希碰撞，然后不停访问这些key导致HashMap忙于进行线性查找，最终陷入瘫痪，即形成了拒绝服务攻击（DoS）。

DK1.8中的HashMap 除了将hash冲突的元素再达到8时，将该长度为8的链表转为红黑树之外，还优化了高位运算的算法(即前面提到的扰动计算)

而JDK1.8 中的ConcurrentHashMap 并未在哈希值的计算上做过多设计，只是将Key的hashCode值与其高16位作异或并保证最高位为0(一定保证为正数值)。作者认为红黑树的效率足够高了，没必要太在意hash碰撞的问题了。

[http_zhaox.github.io_algorithm_2015_06_29_hash]: http://zhaox.github.io/algorithm/2015/06/29/hash