扩容方法 resize( )
扩容机制：
- 什么时候才需要扩容
当HashMap中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值是 0.75 - HashMap 的扩容是什么
进行扩容，会伴随着一次重· hash分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize
设计计算hash值时，要避免出现hash冲突。也就是说不能让它出现链表，更不应该出现红黑树，这样性能很差，如果出现了，证明hash算法，设计的太差。为了避免hash冲突，一，hash算法，二，加载因子
HashMap在进行扩容时，使用的rehash(伪哈希) 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的(n - 1) & hash的结果相比，只是多了一个bit位，所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置
源数组长度: 16 n = 16 n-1=15
(n-1) & hash
0000 0000 0000 0000 0000 0000 0001 0000 16
0000 0000 0000 0000 0000 0000 0000 1111 15 n-1
假设一个hash1(key1): 1111 1111 1111 1111 0000 1111 0000 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 索引 5
0000 0000 0000 0000 0000 0000 0000 1111 15 n-1
假设一个hash2(key2): 1111 1111 1111 1111 0000 1111 0001 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 索引 5
=======================================================================================
此时数组扩容--> 16 * 2 = 32 n = 32 n-1=31
(n-1) & hash
0000 0000 0000 0000 0000 0000 0010 0000 32
0000 0000 0000 0000 0000 0000 0001 1111 31 n-1
假设一个hash1(key1): 1111 1111 1111 1111 0000 1111 0000 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 索引 5
0000 0000 0000 0000 0000 0000 0001 1111 31 n-1
假设一个hash2(key2): 1111 1111 1111 1111 0000 1111 0001 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0101 索引 5 + 16
扩容之后的索引位置要么是原来索引,要么是原来索引 + 旧数组容量
举例:
5 或者 5 + 16
因此元素在重新计算hash之后，因为n变为 2 倍，那么 n - 1 的标记范围在高位多 1bit(红色)，因此新的index就会发生这样的变化
5 是假设计算出来的原来的索引。这样就验证了上述所描述的：扩容之后所以节点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置
因此，我们在扩充
HashMap的时候，不需要重新计算 hash，只需要看看原来的hash 值新增的那个 bit 是 1 还是 0 就可以了，是 0 的话索引没变，是 1 的话索引变成 “原位置 + 旧容量” 。可以看看下图为 16 扩充为 32 的resize示意图：
正是因为这样巧妙的 rehash(伪哈希) 方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit 是 0 还是 1 可以认为是随机的，在 resize的过程中保证了rehash(伪哈希)之后每个桶上的结点数一定小于等于原来桶上的结点数，保证了 rehash(伪哈希) 之后不会出现更严重的 hash冲突，均匀的把之前的冲突的结点分散到新的桶中了
源码 resize 方法的解读
final Node<K,V>[] resize() {
// 得到当前数组
Node<K,V>[] oldTab = table;
// 如果当前数组等于null长度返回0，否则返回当前数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//当前阀值点 默认是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
// 如果老的数组长度大于0
// 开始计算扩容后的大小
if (oldCap > 0) {
// 超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
// 修改阈值为int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
没超过最大值，就扩充为原来的2倍
1) (newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量
2）oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值扩大一倍
newThr = oldThr << 1; // double threshold
}
// 老阈值点大于0 直接赋值
else if (oldThr > 0) // 老阈值赋值给新的数组长度
newCap = oldThr;
else { // 直接使用默认值
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize最大上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 新的阀值 默认原来是12 乘以2之后变为24
threshold = newThr;
// 创建新的哈希表
@SuppressWarnings({"rawtypes","unchecked"})
//newCap是新的数组长度--》32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 判断旧数组是否等于空
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
// 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 原来的数据赋值为null 便于GC回收
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 { // 采用链表处理冲突
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 通过上述讲解的原理来计算结点的新位置
do {
// 原索引
next = e.next;
// 这里来判断如果等于true e这个结点在resize之后不需要移动位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
网友评论