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: 测试链表转红黑树以及扩容
正文到此结束
热门推荐
相关文章
广告是为了更好的提供数据服务
