上一篇文章分析了get()和put()，这篇接着分析put中的resize()，顺带也看一下treeifyBin()中还有一个树化条件。
一、resize()
resize()方法的作用是用来初始化或者扩容数组的，这个方法很长，其中的逻辑需要慢慢的弄清楚，核心内容就是扩容部分，要理解为什么能够使用高低位链表。
final Node<K,V>[] resize() {
// table: 成员变量，是存放元素的数组，这里赋值给局部变量
Node<K,V>[] oldTab = table;
// oldCap存储数组长度，未初始化时为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// threshold: 成员变量，可表示两种含义
// 1. 当未初始化，但是传入了初始容量，则表示需要初始化的大小,这里可以再去看一下构造方法
// 2. 初始化之后表示后续数组的扩容阈值
int oldThr = threshold;
// newCap: 新数组长度，newThr: 新数组扩容阈值
int newCap, newThr = 0;
// oldCap大于0则表示应该走扩容的逻辑
if (oldCap > 0) {
// MAXIMUM_CAPACITY: 数组最大可达长度，一般不会这么长
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 条件1: 首先让新数组长度=旧数组长度*2，再判断是否小于最大长度，这个条件一般为true
// 条件2: 只有当旧数组长度大于默认初始化长度16时才会让新数组的扩容阈值翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// -----------------------后面全部为初始化的步骤-----------------------
// 前置条件: oldCap = 0,在这里说明数组未初始化
// 所以oldThr > 0表示构造方法中传入了初始化大小，所以直接赋值给newCap作为新数组长度
else if (oldThr > 0)
newCap = oldThr;
// 这里的条件是 oldThr = 0，表示构造方法中未传入初始化大小，数组也没有初始化
else {
// 使用默认数组长度16
newCap = DEFAULT_INITIAL_CAPACITY;
// 初始化数组的扩容阈值 = 默认负载因子0.75 * 默认数组长度16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr == 0说明上面走的是初始化逻辑并且构造方法中传入了初始化大小
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY一般为true
// newThr在这里赋值为初始化后的扩容阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 新的扩容阈值赋值给成员变量threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的数组并赋值给成员变量table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 这里是扩容逻辑，当oldTab为null时说明是初始化，这里就可以直接跳过
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
// e用来表示当前的元素
Node<K,V> e;
// 首先判断该旧数组上的第一个元素是否为null
if ((e = oldTab[j]) != null) {
// 把旧数组这里置空，其实是为了帮助gc进行垃圾回收
oldTab[j] = null;
// e在这里旧代替了旧数组该位置上的第一个元素
if (e.next == null)
// 当头元素之后的元素为null时,则可以直接计算出新数组对应的下标然后迁移过去
newTab[e.hash & (newCap - 1)] = e;
// 前置条件: 头元素之后还有元素
// e如果是红黑树的节点则走红黑树的扩容逻辑，这里就不细讲红黑树了
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 走到这里说明头元素之后还有元素并且是链表
else {
/**
* 这部分逻辑要看懂首先得明白数据存放位置是如何得来的，下面我画了一张图可以看看
* 图中以1号桶位举例，转移后的数据只可能映射到新数组的1号桶位或者17号桶位
* 我们把1号桶位称为低位，17号桶位称为高位
* loHead: 低位链表的头元素 loTail: 低位链表的尾元素
* hiHead: 高位链表的头元素 hiTail: 高位链表的尾元素
*/
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
// 指向下一个元素
Node<K,V> next;
do {
next = e.next;
/**
* 这里就是在计算下图中X的值
* 还记得前面说过数组的容量一定是2的整数次幂吗，也就是二进制中只有一个1
* 假设旧数组容量为16 -> 0001 0000
* 经过e.hash & oldCap运算之后，要么为0000 0000要么为0001 0000
* X=0时放入低位链表中，X=1时放入高位链表
* 这里可以知道数据迁移使用的是尾插法
*/
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;
}
// do while一直把这个桶位的链表遍历完毕
} while ((e = next) != null);
// 这部分就是纯赋值了，把上面高低位链表的元素放入新数组中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
数据迁移
二、treeifyBin()
这个方法主要是用于转换红黑树，内部还有replacementTreeNode()和treeify()，这些都属于红黑树部分了，在HashMap中我就不展开细聊了，以后分析红黑树源码时再来看吧，这里了解一下转换红黑树的另一个条件即可。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY = 64，这里如果数组长度小于64则会进入resize()方法
// 进入resize()后就会执行扩容逻辑，所以这里可以得出结论
// 链表树化的条件是链表元素 >= 8 并且数组长度 >= 64，如果只是链表元素到达8则会扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 树化逻辑
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 把链表节点替换为红黑树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 全部转为红黑树节点之后进行树化
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
从这里可以得知结论
- 链表树化条件：桶位链表元素个数 大于等于 8 并且 数组长度 大于等于 64
- 数组扩容条件：数组元素大于扩容阈值(数组长度*0.75) 或者 单个桶位链表元素 大于等于 8
网友评论