hashmap扩容
oldCap | newCap |
---|---|
oldCap=0 && threshold ==0 | 16 |
oldCap=0 && threshold >0 | cap = threshold |
0 < oldCap < MAXIMUM_CAPACITY | 原容量2倍 |
oldCap>= MAXIMUM_CAPACITY | 不扩容 |
我们可以看到即使进入到resize方法也未必会扩容,如果 oldCap>= MAXIMUM_CAPACITY时,即使超过扩容阈值也不会对原数组扩容;;
扩容的时候,首先会判断table的容量;根据容量大小分3大类情况
- 1.oldCap > 0
- 1.1oldCap >= MAXIMUM_CAPACITY(1<<30),就不会扩容newCap = oldCap,threshold=2*oldThr;
-
1.20< oldCap < MAXIMUM_CAPACITY,又已经初始化了(oldCap != 0),则会2倍扩容;newCap = oldCap << 1;
对于新的阈值newThr,则会根据oldCap,newCap共同判断;
- newCap < MAXIMUM_CAPACITY && oldCap >= 16;newThr = oldThr<<1 (2倍);
- newCap * loadFactor > MAXIMUM_CAPACITY ? newThr = Integer.MAX_VALUE : newCap * loadFactor
- 2.oldCap=0 && oldThr>0 ;newcap = oldThr;(为什么cap=0,而thr!=0?)
- 3.oldCap =0 && oldThr == 0 ;newCap = 16; newThr = 12;
下面我们看源码实现:
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) {//当oldCap >= MAXIMUM_CAPACITY(1<<30)时,不扩容;
threshold = Integer.MAX_VALUE;//阈值设置为最大整数
return oldTab;
}
//oldCap < MAXIMUM_CAPACITY 时,扩容:newCap = oldCap << 1;
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 2倍oldThr
}
else if (oldThr > 0) //创建对象时,指定了容量大小;
newCap = oldThr;
else { // 初始化时newCap = 16;newThr = 16 * 0.75 = 12;
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//设置新阈值newThr,
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) {//将oldTab的数据复制到newTab中
}
看到上面有一段逻辑
if (oldCap > 0) {
....
}
else if(oldThr >0){
.....
}
为什么会有这样的判断?原因是什么?因为我们知道thr = cap * loadFactor;如果cap=0,那thr也就等于0;那为什么还要做这种判断呢?
原因:在HashMap的构造方法中可以指定HashMap的容量,在这个时候会初始化threshold的值,并且不会创建table,因此会出现oldCap=0,而oldThr!=0的情况;
总结resize的流程图: