本文对HashMap的学习是基于JDK1.8版本.
本文将解析三个问题 :
- 问题1:为什么 hash函数要 h = key.hashCode() ^ (h >>> 16),而不是直接返回 key.hashCode(),然后直接与数组的长度取模运算?
- 问题2:为什么 (n - 1) & hash(key)计算数组的索引值时,数组的长度(n)需要减一?
- 问题3:为什么 HashMap要保证数组的长度是2的整数次幂?
- 解答过程 : 问题3 ----> 问题2 ----> 问题1
哈希算法
哈希算法的定义 : 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值.
哈希算法需要满足以下条件:
- 1.从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法)。
- 2.对输入数据非常敏感,哪怕原始数据只修改了一个Bit,最后得到的哈希值也大不相同。
- 3.散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。
- 4.哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。
哈希算法的一种应用 --- 散列函数
哈希算法的应用非常非常多,本文讲到的HashMap用的hash函数，就是散列函数.
对于HashMap(散列表)，散列函数的设计是很重要的，而主要需要考虑的是上面的条件3、4 ：
- 条件1 : 散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。
- 条件2 ：HashMap的hash函数是基于hashcode计算的,并且判断是否同一个key对象也要基于hashcode和==、equals函数,所以对于key可变对象的判断,必须重写hashcode函数和equals函数.
- 条件3 : 相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。
- 条件4 ：散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。
// 接下来看看Java中HashMap的hash函数:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key.hashCode()的作用是返回key键值类型自带的一个int类型的散列值.
我们知道,在Java中二进制32位的int表值范围从-2147483648到2147483648,如果直接拿hashCode作为下标访问HashMap主数组的话,需要初始化一个40亿长度的数组,内存是放不下的;既然数组的长度不能初始化这么长,那就给个初始化值,HashMap初始化的默认长度为16,但是hashCode(散列值)这个值很大,肯定不能直接拿来寻找对应的数组索引值,所以就需要跟数组的长度取模运算得到对应的数组索引值.
// n为数组长度
// 通过hash(key)值 与 (n-1) 取模 计算出index(最终存储的数组索引值)
int index = (n - 1) & hash(key);
解决问题2、问题3疑惑
这两问题是有联系的,数组长度减一(n-1)正好相当于一个"低位掩码",以下面为例子:
- 8(8 - 1 = 7) : 2进制表示是 : 0000 0000 0000 0000 0000 0000 0000 0111
- 16(16 - 1 = 15) : 2进制表示是 : 0000 0000 0000 0000 0000 0000 0000 1111
- 64(64 - 1 = 63) : 2进制表示是 : 0000 0000 0000 0000 0000 0000 0011 1111
这三个值和某散列值做"与"操作,结果就是截取了后面的低位值,如下:
// n = 8
hash(key) ：11111111 11011001 00011010 00100110
(n-1)：00000000 00000000 00000000 00000111
-----------------------------------------------
& ：00000000 00000000 00000000 00000110
结果计算出索引值为 : 6
// n = 16
hash(key) ：11111111 11011001 00011010 00100110
(n-1)：00000000 00000000 00000000 00001111
-----------------------------------------------
& ：00000000 00000000 00000000 00000110
结果计算出索引值为 : 6
// n = 64
hash(key) ：11111111 11011001 00011010 00100110
(n-1)：00000000 00000000 00000000 00111111
-----------------------------------------------
& ：00000000 00000000 00000000 00100110
结果计算出索引值为 : 32 + 6 = 38
上面这三个例子你会发现,hash值与(n-1)做与运算的时候,除非数组的长度很长,不然都是高位全部归零,只保留低位.
这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重.hash函数的价值就体现出来了.
解决问题1疑惑
为什么 hash函数要 h = key.hashCode() ^ (h >>> 16),而不是直接返回 key.hashCode(),然后直接与数组的长度取模运算?
上小节中我们知道了(n - 1) & hash(key)的计算总是高位全部归零,只保留低位,也就是说如果能加大hash(key)的低位的随机性,那就更好了,其实这就是hash函数的作用.
hash(key) ： 右移16位,刚好的二进制32位一半,自己的高半区和低半区做异或运算,就是为了混合原始哈希值的高位和低位,来加大低位的随机性.
h = key.hashCode() ：1111 1111 1111 1111 0110 0010 1100 0101
-------------------------------------------------------------
h ：1111 1111 1111 1111 0110 0010 1100 0101
h >>> 16 ：0000 0000 0000 0000 1111 1111 1111 1111
-------------------------------------------------------------
hash = h ^(h>>>16) ：1111 1111 1111 1111 1001 1101 0011 1010
-------------------------------------------------------------
hash : 1111 1111 1111 1111 1001 1101 0011 1010
(n-1): 0000 0000 0000 0000 0000 0000 0000 1111
-------------------------------------------------------------
(n-1) & hash : 0000 0000 0000 0000 0000 0000 0000 1010
-------------------------------------------------------------
1010
结果计算出索引值为 : 9
通过上面的例子,我们可以知道,hash函数混合后的低位掺杂了高位的部分特征,高位的信息也被变相保留下来,而最终的目的是为了提高低位的随机性和数组的长度减一做按位与运算.
总结
- 计算数组的索引值时,数组的长度(n)需要减一,得到一个低位掩码.
- HashMap保证数组的长度是2的整次幂,数组的长度(n-1)和hash值进行 按位与(&) 运算时,高位归零,只保留低位.
- hash函数进行了高位区 和 低位区 的 异或运算,目的就是为了提高低位区的随机性.
- A % B = A & (B - 1),两种都是取余操作,当B是2的指数时(也就是保证了数组长度是2的整数次幂),等式成立.
结束语
哈希算法还有很多其他应用的地方,本文主要说说HashMap使用的散列函数应用.
- 原创不易
- 希望看完这篇文章的你有所收获!