HashMap与HashTable的哈希算法——JDK1.9源码阅读总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HashMap与HashTable的哈希算法——JDK1.9源码阅读总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1602字,纯文字阅读大概需要3分钟。
内容图文
下面是HashTable源码中的put方法:
注意上面注释标注的地方:
HashTable对于元素在哈希表中的坐标算法是:
- 将对象自身的哈希值key.hashCode()变为正数:hash & 0x7FFFFFFF
- 将上面得到的哈希值对表长取余,映射到哈希表中去。
HashMap中哈希算法比HashTable中的稍微复杂一点。总体可以分为两步:
一、重新计算key本身的哈希值
上面代码中,首先是一个三目运算符,判断key是不是等于null,等于null,则返回0作为哈希值。否则,运算(h=key.hashCode()) ^ (h >>> 16),将key的哈希值的高位与低位异或的结果作为低位,改为不变。
‘>>>’是无符号右移操作,高位补0.
为什么要这么做呢?下面这一点讲了过后我们就明白了
二、哈希坐标的计算
同样以put方法为例
从最后一行我们可以看出,HashMap的哈希坐标计算方法是: (n - 1) & hash,其中hash就是我们第一点讲的改进哈希码。
HashMap为什么要使用改进的hash码?
举例分析如下,假设key的原始哈希值是’1111 1111 1111 1111 1111 0000 1110 1010’
(ps:图片来自:https://blog.csdn.net/john_520/article/details/57415084)
我们注意到,在上面这种哈希表长度较小的情况下,哈希码只有低4位与表的长度进行了关联性计算。这会造成哈希码的不充分使用,从而更容易引起哈希冲突。为了充分利用哈希码的高位,HashMap通过(h=key.hashCode()) ^ (h >>> 16)运算,将高位与低位异或,使得即使在表长较小的情况下,高位也能参与计算,使得冲突的概率减小了。
HashMap为什么要使用 (n - 1) & hash ,而不是HashTable中求模的方式来计算哈希坐标呢?
我在Stack Overflow上找到了一个解答:
意思是说:“规范的解决方法是将哈希值与表长取模,而这个方式((n - 1) & hash
)武汉英语学校充分利用了HashMap的表长是2的整数次幂的事实,使用效率较高的位与运算(取模的高度优化)来替代昂贵的取模运算。”
实际上这两种方式的实质是一样的,它只是利用了这样一个事实:在n是2的幂的情况下,(n - 1) & hash 等同于 hash%h。
在n是2的幂的情况下,为什么 (n - 1) & hash等同于 hash%h?
我们以10为例,演示如下:
可以看到,两种方式的计算结果是相同的(这不是巧合),这实际上是一个数学规律。
HashMap是怎么使得表长始终为2的整数次幂的?
在源码中有这样一个方法:
这个方法的作用如注释所说,是求大于cap的最小2的整数次幂。在用户指定的初始容量不是2的幂时,HashMap会调用该方法将其变得符合要求。此后,每次扩容时是这样的:
直接使用oldCap<<1来将容量扩大为原来的2倍,即乘以21。
- 对数学规律的恰当应用可以优化代码的运行效率
- 位运算在JDK中运用的十分广泛,如上面讲解的使用位“与”运算替代求模。这种替代的内在原因是位运算比数学运算快很多。优化都在细节处。
我对JDK源码的阅读和中文注释都已经同步到Github,欢迎英语阅读困难户前往查看:)
链接是:https://github.com/Dodozhou/JDK,喜欢的话别忘了star哦。
原文:https://www.cnblogs.com/zhangyiqinga/p/9753642.html
内容总结
以上是互联网集市为您收集整理的HashMap与HashTable的哈希算法——JDK1.9源码阅读总结全部内容,希望文章能够帮你解决HashMap与HashTable的哈希算法——JDK1.9源码阅读总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。