Style：Mac
Series：Java
Since：2018-09-10
End：2018-09-10
Total Hours：1
Degree Of Diffculty：5
Degree Of Mastery：5
Practical Level：5
Desired Goal：5
Archieve Goal：3
Gerneral Evaluation：3
Writer:kingdelee
Related Links：
http://www.cnblogs.com/kingdelee/
1.resize()
源码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 节点的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 容量值
int oldThr = threshold;
// 新容量值，新节点长度
int newCap, newThr = 0;
// 节点的长度
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab; //返回该节点
}
// 容量 > 16 且 < 最大容量的情况下，容量 扩充 1倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //当节点长度为空时，赋容量值默认值16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 指定扩容阀值为16*0.75=12
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建一个节点数组，容量为16
logger.info("创建 Node<K,V>[] newTab, 赋予table，newCap：" + newCap);
table = newTab;
logger.info("threshold:" + threshold + ",newCap:" + newCap + ",newThr:" + newThr);
logger.info("oldTab isNull:" + (oldTab != null) );
if (oldTab != null) {
logger.info("因为阀值溢出，需要扩容阀值进来的，oldTab != null, oldTab.length:" + oldCap);
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
logger.info("开始对oldTab进行横向遍历");
if ((e = oldTab[j]) != null) {
logger.info("1.1 遍历发现oldTab["+j+"]" + "非空");
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
logger.info("1.1.1 且该节点存在next节点");
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
logger.info("1.1.1.1 进行该节点的纵向遍历");
next = e.next;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
logger.info("return newTab");
return newTab;
}
1.1 触发条件
1.1.1 触发条件(1) 当第一次put的时候，会因为[]tab还未创建时，会触发
因为第1次put，贯穿整体的横向数组Node[] tab会在这里首次创建
初始长度为 newCap=16
扩容阀值 newThr=0.75*16=12
if ((tab = table) == null || (n = tab.length) == 0) {
logger.info("table为null");
n = (tab = resize()).length; // 1.当未指定初始容量时，进行resize, 得到容量值赋给n=16; 获得新的节点给tab；已经存在节点时不再进来
logger.info("tab renTab");
}
1.1.2
触发条件(2) 当成功put入的元素（包含子节点）>=阀值时，会进行横向扩容
++modCount; //执行put操作的次数
logger.info("modCount:" + modCount);
if (++size > threshold) //已经存放元素的容量+1 与 扩容阀值进行对比
{
logger.info("++size > threshold, size:" + size + ", threshold:" + threshold);
resize();
}
重点看这段
此时扩容，会创建Node[] newTab, 容量为oldTab的2倍
然后开始对oldTab进行横向遍历，找到有节点的坑位。
如果该坑位没有子节点，直接将本节点放到newTab的坑位中
如果该坑位是树，进行树的处理
只能是链表结构了，对子节点进行纵向遍历
此时处理分两种情况；如果该节点的hash与oldCap相等，则将该节点丢到newTab的
if (oldTab != null) {
logger.info("因为阀值溢出，需要扩容阀值进来的，oldTab != null, oldTab.length:" + oldCap);
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
logger.info("开始对oldTab进行横向遍历");
if ((e = oldTab[j]) != null) {
logger.info("1.1 遍历发现oldTab["+j+"]" + "非空");
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
logger.info("1.1.1 且该节点存在next节点");
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
logger.info("1.1.1.1 进行该节点的纵向遍历");
next = e.next;
if ((e.hash & oldCap) == 0) {
// 因为：当且仅当a=b => a&b =1；否则为0.所以大概率进来
// 进入条件：a!=b
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 进入条件：a=b
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 会放在新的右半边容量中，更加松散
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
1.1.3 触发条件(3)
put子节点时，触发进化二叉树时，会立即进行扩容
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
logger.info("n = tab.length:" + tab.length);
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //小于最小默认树结构容量64时进行扩容
{
logger.info("小于树最小容量阀值64，进行扩容");
resize();
}