HashMap实现原理：容量、负载因子、hash与定位都搞定了吗？( 九 )_HashMap是常考点

即，当超过限制的时候会resize ，又因为我们使用的是2次幂的扩展，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

怎么理解呢？例如我们从16扩展为32时，具体的变化如下：

假设bucket大小n=2^k ，元素在重新计算hash之后，因为n变为2倍那么新的位置就是(2^(k+1)-1)&hash 。而2^(k+1)-1=2^k+2^k-1 ，相当于2^k-1的mask范围在高位多1bit(红色)(再次提醒，原来的长度n也是2的次幂) ，这1bit非1即0 。如图：

所以，我们在resize的时候，不需要重新定位，只需要看看原来的hash值在新增bit的位置上是1还是0就好了，是0的话位置没变，是1的话位置变成“原位置+oldCap” 。代码比较长就不贴了，下面为16扩充为32的resize示意图：

这个设计非常的巧妙，如果认为hash值是随机的，那么新增的1bit是0还是1也是随机的，因此resize的过程随机的把之前的冲突的节点分散到新的bucket中了。

HashMap实现原理：容量、负载因子、hash与定位都搞定了吗？( 九 )