JDK1.8 HashMap源码解析(三) 扩容机制和resize源码详解
- JDK1.8 HashMap源码解析 目录
扩容机制核心方法 Node[] resize()
HashMap扩容可以分为三种情况:
- 第一种:使用默认构造方法初始化HashMap(
HashMap()
)。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table,并且thershold未赋值所以为0。
此时oldCap=0, oldThr=thershold=0, 因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
源代码部分
} else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
// 默认 16 * 0.75 = 12
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
- 第二种:指定初始容量的构造方法初始化HashMap(
HashMap(int initialCapacity)
以及HashMap(int initialCapacity, float loadFactor)
)。那么从下面源码可以看到初始容量会等于threshold,接着 threshold = 当前的容量(threshold)*DEFAULT_LOAD_FACTOR。此时oldCap=0, oldThr=thershold>0。
源代码执行部分
else if (oldThr > 0) // initial capacity was placed in threshold
{
newCap = oldThr;
} else {
- 第三种:HashMap不是第一次扩容。如果HashMap已经扩容过的话,那么每次table的容量以及threshold量为原有的两倍。此时入参为Map测构造方法也可以出发扩容动作(
HashMap(Map<? extends K, ? extends V> m)
).
源代码执行部分
if (oldCap > 0) {
......
}
HashMap是先插入数据再进行扩容的,但是如果是刚刚初始化容器的时候是先扩容再插入数据。
构造HashMap表时,如果不指明初始大小,默认大小为16(即Node数组大小16),如果Node[]数组中的元素达到(填充比0.75*Node.length)时,进行扩容操作,重新调整HashMap大小变为原来2倍大小。扩容很耗时。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
/**
* 对table进行初始化或者扩容。
* 如果table为null,则对table进行初始化
* 如果对table扩容,因为每次扩容都是翻倍,与原来计算(n-1)&hash的结果相比,
* 节点要么就在原来的位置,要么就被分配到“原位置+旧容量”这个位置。
*
* resize的步骤总结为:
* 1.计算扩容后的容量,临界值。
* 2.将hashMap的临界值修改为扩容后的临界值
* 3.根据扩容后的容量新建数组,然后将hashMap的table的引用指向新数组。
* 4.将旧数组的元素复制到table中。
*
* @return the table
*/
final Node<K, V>[] resize() {
//新建oldTab数组保存扩容前的数组table
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//默认构造器的情况下为0
int oldThr = threshold;
int newCap, newThr = 0;
//如果旧表的长度不是空, 扩容肯定执行这个分支
if (oldCap > 0) {
//当前table容量大于最大值得时候返回当前table. 此时loadfactor很大,冲突量比较大,查询不再是O(1)
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
// 把新表的长度设置为旧表长度的两倍,newCap=2*oldCap
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {
//扩容容量为2倍,临界值为2倍
newThr = oldThr << 1; // double threshold
}
// 如果旧表的长度的是0,就是说第一次初始化表
} else if (oldThr > 0) // initial capacity was placed in threshold
{
//使用带有初始容量的构造器时,table容量为初始化得到的threshold
newCap = oldThr;
} else { // zero initial threshold signifies using defaults
//默认构造器下进行扩容
newCap = DEFAULT_INITIAL_CAPACITY;
// 默认 16 * 0.75 = 12
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//使用带有初始容量的构造器在此处进行扩容
if (newThr == 0) {
//新表长度乘以加载因子
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//将新的临界值赋值赋值给threshold
threshold = newThr;
@SuppressWarnings({"rawtypes", "unchecked"})
// 开始构造新表, 按newCap创建新的数组,初始化表中的数据
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
//新的数组赋值给table
table = newTab;
//扩容后,对新扩容后的table赋值,重新计算元素新的位置。 原表不是空要把原表中数据移动到新表中
if (oldTab != null) { // oldCap 原数组
//遍历原来的旧表
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
//判断当前遍历下的该node是否为空,将j位置上的节点保存到e, 然后将oldTab[j]置为空。
if ((e = oldTab[j]) != null) {
// 为什么要置为空,有什么好处?? TODO
oldTab[j] = null;
///普通节点, 位置是hash求余。 如果为null 说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
if (e.next == null) {
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) {
// 树形结构修剪. 当扩容时,
// 如果当前桶中元素结构是红黑树,并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD (默认为 6),就会把桶中的树形结构缩小或者直接还原(切分)为链表结构
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
// 如果e后边有链表,到这里表示e后面带着个单链表,需要遍历单链表,将每个结点重新计算在新表的位置,并进行搬运
} else { // preserve order 保证顺序
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
/*
这里如果判断成立,那么该元素的地址在新的数组中就不会改变。
因为oldCap的最高位的1,在e.hash对应的位上为0,所以扩容后得到的地址是一样的,位置不会改变 ,在后面的代码的执行中会放到loHead中去,最后赋值给newTab[j];
如果判断不成立,那么该元素的地址变为 原下标位置+oldCap,也就是lodCap最高位的1,在e.hash对应的位置上也为1,所以扩容后的地址改变了,在后面的代码中会放到hiHead中,最后赋值给newTab[j + oldCap]
举个例子来说一下上面的两种情况:
设:oldCap=16 二进制为:0001 0000
oldCap-1=15 二进制为:0000 1111
e1.hash=10 二进制为:0000 1010
e2.hash=26 二进制为:0101 1010
e1在扩容前的位置为:e1.hash & oldCap-1 结果为:0000 1010
e2在扩容前的位置为:e2.hash & oldCap-1 结果为:0000 1010
结果相同,所以e1和e2在扩容前在同一个链表上,这是扩容之前的状态。
现在扩容后,需要重新计算元素的位置,在扩容前的链表中计算地址的方式为e.hash & oldCap-1
那么在扩容后应该也这么计算,扩容后的容量为oldCap*2=32,2^5, 二进制为:0010 0000。 所以 newCap=32,
新的计算方式应该为
e1.hash & newCap-1
即:0000 1010 & 0001 1111
结果为0000 1010与扩容前的位置完全一样。
e2.hash & newCap-1 即:0101 1010 & 0001 1111
结果为0001 1010,为扩容前位置+oldCap。
而这里却没有e.hash & newCap-1 而是 e.hash & oldCap,其实这两个是等效的,都是判断倒数第五位是0,还是1。
如果是0,则位置不变,是1则位置改变为扩容前位置+oldCap。
再来分析下loTail, loHead这两个的执行过程(假设(e.hash & oldCap) == 0成立):
第一次执行:
e指向oldTab[j]所指向的node对象,即e指向该位置上链表的第一个元素.
loTail为空,所以loHead指向与e相同的node对象(loHead = e;),然后loTail也指向了同一个node对象(loTail = e;)。
最后,在判断条件e指向next,就是指向oldTab链表中的第二个元素
第二次执行:
lotail不为null,所以lotail.next指向e,这里其实是lotail指向的node对象的next指向e,
也可以说是,loHead的next指向了e,就是指向了oldTab链表中第二个元素。此时loHead指向
的node变成了一个长度为2的链表。然后lotail=e也就是指向了链表中第二个元素的地址。
第三次执行:
与第二次执行类似,loHead上的链表长度变为3,又增加了一个node,loTail指向新增的node......
hiTail与hiHead的执行过程与以上相同。
由此可以看出,loHead是用来保存新链表上的头元素的,loTail是用来保存尾元素的,直到遍历完链表。
这是(e.hash & oldCap) == 0成立的时候。
(e.hash & oldCap) == 0不成立的情况也相同,其实就是把oldCap遍历成两个新的链表,
通过loHead和hiHead来保存链表的头结点,然后将两个头结点放到newTab[j]与newTab[j+oldCap]上面去。
*/
do {
//记录下一个结点
next = e.next;
// 新表是旧表的两倍容量,实例上就把单链表拆分为两队, e.hash&oldCap==0为偶数一队,反之为奇数一对
if ((e.hash & oldCap) == 0) {
if (loTail == null) {
loHead = e;
} else {
loTail.next = e;
}
loTail = e;
} else {
if (hiTail == null) {
hiHead = e;
} else {
hiTail.next = e;
}
hiTail = e;
}
} while ((e = next) != null);
//lo队不为null,放在新表原位置
if (loTail != null) {
//尾节点的next设置为空
loTail.next = null;
newTab[j] = loHead;
}
//hi队不为null,放在新表j+oldCap位置
if (hiTail != null) {
//尾节点的next设置为空
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结
resize(扩容) 的上限
resize 不是无限的,当到达resize 的上限,也就是230 之后,不再扩容
resize 方法只有三种情况下调用
- 第一种 是在**首次插入元素的时候完成数组的初始化**
- 第二种 是在元素插入**完成后**判断是否需要数组扩容,如果是的话则调用
- 第三种 是在元素插入链表尾部之后,进入树化方法之后,如果不树化则进行resize
resize 的返回值
- 第一种情况下 返回老的数组也就是没有resize 因为已经达到resize 的上限了
- 第二种情况下 返回一个空的数组 也就是第一次调用resize方法
- 第三种情况下 返回一个扩容后的数组 完成了数据迁移后的数组
key 的判断
- 第一次判断是当前位置有元素的时候,如果两个key 相等则准备覆盖值
- 第二次判断是遍历链表的时候,决定能否覆盖链表中间key 相等的值而不是链表的尾部
你觉得Hashmap 还有什么可以改进的地方吗,欢迎讨论
虽然java 源代码的山很高,如果你想跨越,至少你得有登山的勇气,这里我给出自己的一点点愚见,希望各位不吝指教
相关链接:
源码
最后,附源代码如下:
JDK1.8 HashMap源码解析
Demo: 测试链表转红黑树以及扩容
正文到此结束
热门推荐
相关文章
广告是为了更好的提供数据服务