内容简介:HashMap 是面试的钉子户了,网上分析的文章也有很多,相信大家对于原理已经烂俗于心了。但最近在看源码时,发现其中一些实现细节其实不太好理解,所以决定以问答的形式在这里记录一下,写的时候尽量把原因说明白。容量并不是指 HashMap 所能存储的键值对数量,而是其内部的 table 数组的大小,而 size 是指目前已存储的键值对的数量。table 是一个 Entry 数组。 table 的每一个节点都连着一个链表或者红黑树。可以,但是 HashMap 内部会你设置的 initialCapacity 转换为
HashMap 是面试的钉子户了,网上分析的文章也有很多,相信大家对于原理已经烂俗于心了。但最近在看源码时,发现其中一些实现细节其实不太好理解,所以决定以问答的形式在这里记录一下,写的时候尽量把原因说明白。
容量和 size 分别指什么?
容量并不是指 HashMap 所能存储的键值对数量,而是其内部的 table 数组的大小,而 size 是指目前已存储的键值对的数量。table 是一个 Entry 数组。 table 的每一个节点都连着一个链表或者红黑树。
初始容量可以随意设置吗?
可以,但是 HashMap 内部会你设置的 initialCapacity 转换为大于等于它的最小的2的n次方。比如 20 转为 32,32 转为 32等。如果不设置,则为默认值16。需要注意的是,在 Java 8的源码中,并没有在构造方法直接新建数组。而是先将处理后的容量值赋给 threshold,在第一次存储键值对时再根据这个值创建数组。
为什么内部要将容量转换为 2 的n次方?
这样可以提高取余的效率。为了防止链表过长,要保证键值对在数组中尽可能均匀分布,所以在计算出 key 的 hash 值之后,需要对数组的容量进行取余,余数即为键值对在 table 中的 index。 对于计算机而言,二进制位运算的效率高于取余(%)操作。而如果容量是 2 的 n 次方的话,hash 值对其取余就等同于 hash 值和容量值减1进行按位与(&)操作:
// capacity 为 2 的 n 次方的话,下面两个操作结果相同 hash & (capacity -1) 等同于 hash % capacity 复制代码
那为什么两种操作等同呢? 我们以2进制的思维想一下,如果一个数是 2 的 n 次方,那它的二进制就是从右往左 n 位都为0,n+1 位为1。比如2的3次方就是 1000。这个数的倍数也满足从右往左 n 位都为0,取余的时候抛弃倍数,就等同于将 n+1 位及其往左的所有位归0,剩下的 n 位就代表余数。 换句话说,一个数对2的 n 次方取余,就是要取这个数二进制的最低 n 位 。 2 的 n 次方减1的结果就是 n 位1,进行与操作后就得到了最低 n 位。
如何将一个值转换为大于等于它的最小的2的 n 次方?
我们先假设一个二进制数 cap,cap 的二进制有 a 位(不算前面高位的0),那么,大于它的最小的2的次方就是2的 a 次方。2 的 a 次方减一的结果就是 n 位1,那我们只要将 cap 的全部 2 进制位变为1,再加1就能得到结果。而为了防止 cap 本身就是2的 n 次方,我们在计算之前先将 cap 自减。
如何将二进制位都变成1呢?下面是源码:
static final int tableSizeFor(int cap) { int n = cap - 1; //这一步是为了避免 cap 刚好为2的 n 次方 n |= n >>> 1; //保证前2位是1 n |= n >>> 2; //保证前4位是1 n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } 复制代码
下面的描述中 n 的位数都不包括前面补位的0。
|= 这个符号不常见,a |= b 就是 a = a|b 的意思。代码中先将 n 无符号右移1位,由于n 的第1位肯定是1,移位后第2位是1, |
操作后前2位就保证是1了。第二步右移了2位再进行 |
操作,保证了前4位是1,后面的计算类似,由于 n 最多有32位,所以一直操作到右移16为止。这样就将 n 的所有2进制位都变成了1,最后自增返回。
hash 值是如何计算的
hash 值并没有直接返回 hashcode 的返回值,而是进行了一些处理。 前面提到过,hash 值算出来后需要进行取余操作,影响取余结果的是 hash 值的低 n 位。如果低 n 位是固定的或者集中在几个值,那么取余的结果容易相同,导致 hash 碰撞的发生。由于 hashcode 函数可以被重写,重写者可能无意识地就写了一个坏的 hash 函数,导致上面这种情况发生。
为了避免这种情况,HashMap 将 hash 值先向右移位,再进行或操作,这样就使高位的值和低位的值融合成一个新的值,保证取余结果受每一个二进制位的影响。Java 7和 Java 8的原理都一样,但源码有细微出入,可能是 因为 Java 经过统计发现移位一次就够了吧。
//Java 7 static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } //Java 8 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 复制代码
扩容后元素如何进行移动
为了防止元素增多后,链表越来越长,HashMap 会在元素个数达到阈值后进行扩容,新的容量为旧容量的2倍。 容量变化后,每个元素用 hash 值取余的结果也会随之变化,需要在数组中重新排列。以前同一条链表上的元素,扩容后可能存在不同的链表上。
在 Java 7 中,重新排列实现得简单粗暴,直接用 hash 根据新容量算出下标,然后设置到新数组中,即相当于将元素重新put 了一次。但在 Java 8中,作者发现没必要重新插入,因为重新计算后,新的下标只可能有两种情况,要么是原来的值,要么是原来的值加旧容量。比如容量为16的数组扩容到32,下标为1的元素重新计算后,下标只可能为1或17。
这个怎么理解呢?重提一下之前的一句话,一个数对2的 n 次方取余,就是要取这个数二进制的最低 n 位。当容量为16时,取余是取最后4位的值,而扩容到32后,取余变成取最后5位的值。这里增加的1位如果为0,那么余数就没变,如果为1,那么余数就增加了16。如何取增加的这一位的值呢?直接和16进行与操作即可。16的二进制是10000,与操作后如果结果为0,即表示高位为0,否则为1。
根据这个原理,我们只需要将原来的链表分成两条新链放到对应的位置即可,下面是具体步骤:
- 遍历旧数组,如果元素的 next 为空,直接取余后放到新数组;
- 如果元素后面连了一个链表,那么新建两条链表,暂且成为 hi 链和 lo 链;
- 遍历链表,计算每个元素的 hash 值和旧容量与操作的结果,结果为0则将其放入 lo 链末端,不为0放入 hi 链末端;
- 将两条链的 head 放到新数组中,其中 loHead 放到原来的位置,hiHead 放到原来的下标加上旧容量处;
- 如果是红黑树,进行和上面类似的操作,只是将两条链表换成两棵树。
理解原理后看代码就很简单了:
if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //红黑树类似 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //新建两条链表 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { //结果为0,表示下标没变,放入 lo 链 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { //结果为0,表示下标要加上旧容量,放入 hi 链 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { //lo 链放在原来的下标处 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { //hi 链放在原来的下标 加旧容量处 hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } 复制代码
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- React 查漏补缺
- Java 查漏补缺之 jvm
- 前端面试查漏补缺--(八) 前端加密
- 前端面试查漏补缺--(一) 防抖和节流
- 前端面试查漏补缺--(九) HTTP与HTTPS
- 前端面试查漏补缺--(七) XSS攻击与CSRF攻击
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
TCP/IP网络管理
亨特 / 电子工业 / 2006年3月1日 / 79.00元
本书是一本架设与维护TCP/IP网络的完整指南,无论你是在职的系统管理员,还是需要访问Internet的家用系统用户,都可从本书获得帮助。本书还讨论了高级路由协议(RIPv2、OSPF、BGP),以及实现这些协议的gated软件。对于各种重要的网络服务,如DNS,Apache,sendmail,Samba,PPP和DHCP,本书都提供了配置范例,以及相关的软件包与工具的语法参考。一起来看看 《TCP/IP网络管理》 这本书的介绍吧!