扩容是什么
一开始很难理解，其实就是不知道数据大小的情况，设计HashMap不可能把size设置无限大，毕竟哪有那么大内存嘛，也不可能设计的太小，这样新数据添加就会需要不断修改当前大小带来性能不佳对吧
这里修改大小其实最麻烦的是索引是根据Hash值取模运算得出，之前是16，现在是32，之前取模现在可能不一定有用了。所以这里把HashMap扩容看一下
扩容，需要将老数据迁移吗
怎么迁移，取模运算还可以继续用吗，索引会变吗？
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;
}
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;
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 = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
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
//低位链表头 尾节点 也就是index不会变的
Node<K,V> loHead = null, loTail = null;
//低位链表头 尾节点 也就是index=index+oldSize的
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//链表就是这里啦，仔细看一下好了，知道是怎么回事
do {
next = e.next;
//==0 means what
if ((e.hash & oldCap) == 0) {
// 为什么等于0就是不变啊
// 首先分析一下之前是16，现在是32，
// 之前取模是与1111 现在与11111
// 所以最关键就是与10000分析那一个byte如果是1，则之前不计较这一位，现在
//这一位要算在内，那么为0则还是以前的index，如果为1则要index=index+size
if (loTail == null)//第一个时候为空
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e; //依次为next添加链表
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;//高位加上此链表
}
}
}
}
}
return newTab;
}
这个逻辑代码看起来很长，但是写的还算比较好理解。大致理顺一下：
1 是否需要扩容
2 扩容一般将大小<<1 ,也就是之前的2倍
3容量大小导致迁移，比如
所以重点理一下迁移算法
依次对老数据一个个遍历
1 如果只有一个数据项
2 TreeNode数据结构
3 链表结构
迁移梳理：
1 依次找到老数据项
2 取模时候由于大小变了，在指定新index插入之前的Node，例如16->32
如果之前hash是2,则index=2的Node，现在需要hash&(32-1)也就是2地方植入新
Node，按道理index应该不变。
还有一种情况如果之前hash是31，则16的时候是15，而32的时候是31，则位置index
newIndex=oldIndex+16
还有其他情况吗，没有啦
3 这里需要注意啦，如果TreeNode交给TreeNode去弄，如果是普通一个数据就直接赋值，如果是链表要很复杂的
梳理一下链表迁移逻辑
分析是index不变的，则与运算为0
index需要index=index+oldSize.则与运算为1
例如
与运算取模 00001111 00011111
hash1 00001101 00001101
hash2 11111101 11111101
hash1取模结果 00001101 00001101
hash2取模结果 00001101 00011101
这样hash1与hash2在16的时候取模是一样的，32的时候是不一样的，
如果hash不变的，则需要在低位节点依次添加上去
如果hash变化，则需要在高节点链表依次添加上去
网友评论