文章目录

HashMap底层的扩容机制resize扩容resize源码源码文字说明HashMap底层为什么是2倍扩容？

HashMap底层的扩容机制

resize扩容

HashMap会在两个地方进行resize(扩容):

1 ，HashMap实行了懒加载, 新建HashMap时不会对table进行赋值, 而是到第一次插入时, 进行resize时构建table; 2， 当HashMap.size 大于 threshold时, 会进行resize;threshold的值，当第一次构建时, 如果没有指定HashMap.table的初始长度, 就用默认值16, 否则就是指定的值; 然后不管是第一次构建还是后续扩容, threshold = table.length * loadFactor;

在Java8的扩容中，不是简单的将原数组中的每一个元素取出进行重新hash映射，而是做移位检测。所谓移位检测的含义具体是针对HashMap做映射时的&运算所提出的，通过上文对&元算的分析可知，映射的本质即看hash值的某一位是0还是1，当扩容以后，会相比于原数组多出一位做比较，由多出来的这一位是0还是1来决定是否进行移位，而具体的移位距离，也是可知的，及位原数组的大小，我们来看下表的分析，假定原表大小16。

由上表可知，是否移位，由扩容后表示的最高位是否1为所决定，并且移动的方向只有一个，即向高位移动。因此，可以根据对最高位进行检测的结果来决定是否移位，从而可以优化性能，不用每一个元素都进行移位，

resize源码

final Node[]resize(){

Node[]oldTab=table;

int oldCap=(oldTab==null)?0:oldTab.length;

int oldThr=threshold;

int newCap,newThr=0;

if(oldCap>0){

// 如果当前哈希桶容量超过最大值2^30，直接返回旧哈希桶大小

// 到达上线 threshold 设置最大阈值返回 表示之后就不再扩容了，随便存，随便hash冲

// 突去，就这么大，无限增加红黑树节点了

if(oldCap>=MAXIMUM_CAPACITY){

threshold=Integer.MAX_VALUE;

return oldTab;

}

// 按照两倍扩容后，如果容量没有达到上限

// 并且旧容量已经超过16

// newCap翻倍，则按照两倍的方式扩容

else if((newCap=oldCap<<1)

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

// 将新容量设置为默认值16

// 将扩容阈值设置为0.75*16

newCap=DEFAULT_INITIAL_CAPACITY;

newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);

}

// 如果新阈值为0，按照新容量的大小重新计算下一次扩容时的阈值

// 计算方式：采用新容量 * 负载因子

// 即扩容的时机为：当元素个数超过阈值时则扩容

if(newThr==0){

float ft=(float)newCap*loadFactor;

// 如果新容量和阈值都是在2^30以内，下一次库哦哦荣的阈值则为ft

// 否则改为最大值

newThr=(newCap

(int)ft:Integer.MAX_VALUE);

}

// 更新下次扩容的上线

threshold=newThr;

@SuppressWarnings({"rawtypes", "unchecked"})

// // 申请更多的桶，将旧哈希桶中节点转移到新哈希桶中

Node[]newTab=(Node[])new Node[newCap];

table=newTab;

if(oldTab!=null){

for(int j=0;j

Node 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)e).split(this,newTab,j,oldCap);

else{ // preserve order

Node loHead=null,loTail=null;

Node hiHead=null,hiTail=null;

Node next;

do{

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;

}

}

}

}

}

return newTab;

}

源码文字说明

1 如果table == null, 则为HashMap的初始化, 生成空table返回即可;

2 如果table不为空, 需要重新计算table的长度, newLength = oldLength << 1(注, 如果原oldLength已经到了上限, 则newLength = oldLength);

3 遍历oldTable:

3.1 首节点为空, 本次循环结束;

3.1 首节点不为空无后续节点, 重新计算hash位, 本次循环结束;

3.2 当前是红黑树, 走红黑树的重定位;

3.3 当前是链表, JAVA7时还需要重新计算hash位, 但是JAVA8做了优化, 通过(e.hash & oldCap) == 0来判断是否需要移位; 如果为真则在原位不动, 否则则需要移动到当前hash槽位 + oldCap的位置;

HashMap底层为什么是2倍扩容？

第一是因为哈希函数的问题 通过除留余数法方式获取桶号，因为Hash表的大小始终为2的n次幂，因此可以将取模转为位运算操作，提高效率，容量n为2的幂次方，n-1的二进制会全为1，位运算时可以充分散列，避免不必要的哈希冲突，这也就是为什么要按照2倍方式扩容的一个原因 第二是因为是否移位的问题 是否移位，由扩容后表示的最高位是否1为所决定，并且移动的方向只有一个，即向高位移动。因此，可以根据对最高位进行检测的结果来决定是否移位，从而可以优化性能，不用每一个元素都进行移位，因为为0说明刚好在移位完之后的位置，为1说明不是需要移动oldCop，这也是其为什么要按照2倍方式扩容的第二个原因。