Java面试题之HashMap 的 hash 方法原理是什么
Warning:这是《Java 程序员进阶之路》专栏的第 55 篇。
回来后小二找到了我,于是我就写下了这篇文章丢给他,并严厉地告诉他:再搞不懂就别来找我。听到这句话,心头一阵酸,小二绷不住差点要哭 😭。
PS:本文 GitHub 上已同步,有 GitHub 账号的小伙伴,记得看完后给二哥安排一波 star 呀!冲一波 GitHub 的 trending 榜单,求求各位了。
GitHub 地址:https://github.com/itwanger/toBeBetterJavaer
来看一下 hash 方法的源码(JDK 8 中的 HashMap):
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
这段代码究竟是用来干嘛的呢?
我们都知道,key.hashCode()
是用来获取键位的哈希值的,理论上,哈希值是一个 int 类型,范围从-2147483648 到 2147483648。前后加起来大概 40 亿的映射空间,只要哈希值映射得比较均匀松散,一般是不会出现哈希碰撞的。
但问题是一个 40 亿长度的数组,内存是放不下的。HashMap 扩容之前的数组初始大小只有 16,所以这个哈希值是不能直接拿来用的,用之前要和数组的长度做取模运算,用得到的余数来访问数组下标才行。
取模运算有两处。
取模运算(“Modulo Operation”)和取余运算(“Remainder Operation ”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中,取余则更多是数学概念。
一处是往 HashMap 中 put 的时候(putVal
方法中):
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); }
一处是从 HashMap 中 get 的时候(getNode
方法中):
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {} }
其中的 (n - 1) & hash
正是取模运算,就是把哈希值和(数组长度-1)做了一个“与”运算。
可能大家在疑惑:取模运算难道不该用 %
吗?为什么要用 &
呢?
这是因为 &
运算比 %
更加高效,并且当 b 为 2 的 n 次方时,存在下面这样一个公式。
a % b = a & (b-1)
用 2 n 2^n 2n 替换下 b 就是:
我们来验证一下,假如 a = 14,b = 8,也就是 2 3 2^3 23,n=3。
14%8,14 的二进制为 1110,8 的二进制 1000,8-1 = 7 的二进制为 0111,1110&0111=0110,也就是 0*
2 0 2^0 20+1*
2 1 2^1 21+1*
2 2 2^2 22+0*
2 3 2^3 23=0+2+4+0=6,14%8 刚好也等于 6。
这也正好解释了为什么 HashMap 的数组长度要取 2 的整次方。
因为(数组长度-1)正好相当于一个“低位掩码”——这个掩码的低位最好全是 1,这样 & 操作才有意义,否则结果就肯定是 0,那么 & 操作就没有意义了。
a&b 操作的结果是:a、b 中对应位同时为 1,则对应结果位为 1,否则为 0
2 的整次幂刚好是偶数,偶数-1 是奇数,奇数的二进制最后一位是 1,保证了 hash &(length-1) 的最后一位可能为 0,也可能为 1(这取决于 h 的值),即 & 运算后的结果可能为偶数,也可能为奇数,这样便可以保证哈希值的均匀性。
& 操作的结果就是将哈希值的高位全部归零,只保留低位值,用来做数组下标访问。
假设某哈希值为 10100101 11000100 00100101
,用它来做取模运算,我们来看一下结果。HashMap 的初始长度为 16(内部是数组),16-1=15,二进制是 00000000 00000000 00001111
(高位用 0 来补齐):
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101
因为 15 的高位全部是 0,所以 & 运算后的高位结果肯定是 0,只剩下 4 个低位 0101
,也就是十进制的 5,也就是将哈希值为 10100101 11000100 00100101
的键放在数组的第 5 位。
明白了取模运算后,我们再来看 put 方法的源码:
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
以及 get 方法的源码:
public V get(Object key) { HashMap.Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
它们在调用 putVal 和 getNode 之前,都会先调用 hash 方法:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
那为什么取模运算之前要调用 hash 方法呢?
看下面这个图。
某哈希值为 11111111 11111111 11110000 1110 1010
,将它右移 16 位(h >>> 16),刚好是 00000000 00000000 11111111 11111111
,再进行异或操作(h ^ (h >>> 16)),结果是 11111111 11111111 00001111 00010101
异或(^
)运算是基于二进制的位运算,采用符号 XOR 或者^
来表示,运算规则是:如果是同值取 0、异值取 1
由于混合了原来哈希值的高位和低位,所以低位的随机性加大了(掺杂了部分高位的特征,高位的信息也得到了保留)。
结果再与数组长度-1(00000000 00000000 00000000 00001111
)做取模运算,得到的下标就是 00000000 00000000 00000000 00000101
,也就是 5。
还记得之前我们假设的某哈希值 10100101 11000100 00100101
吗?在没有调用 hash 方法之前,与 15 做取模运算后的结果也是 5,我们不妨来看看调用 hash 之后的取模运算结果是多少。
某哈希值 00000000 10100101 11000100 00100101
(补齐 32 位),将它右移 16 位(h >>> 16),刚好是 00000000 00000000 00000000 10100101
,再进行异或操作(h ^ (h >>> 16)),结果是 00000000 10100101 00111011 10000000
结果再与数组长度-1(00000000 00000000 00000000 00001111
)做取模运算,得到的下标就是 00000000 00000000 00000000 00000000
,也就是 0。
综上所述,hash 方法是用来做哈希值优化的,把哈希值右移 16 位,也就正好是自己长度的一半,之后与原哈希值做异或运算,这样就混合了原哈希值中的高位和低位,增大了随机性。
说白了,hash 方法就是为了增加随机性,让数据元素更加均衡的分布,减少碰撞。
到此这篇关于Java面试题之HashMap 的 hash 方法原理是什么的文章就介绍到这了,更多相关Java HashMap内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/qing_gee/article/details/120260024
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13