HashMap扩容流程[通俗易懂]

2022-09-29 11:47:30 浏览数 (1)

大家好，又见面了，我是你们的朋友全栈君。

文章目录

    • 为什么扩容？
    • 什么时候扩容？
    • 如何扩容？

今天在和同时讨论HashMap的时候，提到了扩容和冲哈希的事情，然后我发现大家都是一种半懂不懂的状态。于是回去做了一番功课，写下这篇文章。

HashMap的扩容，又被很多人叫rehash、重哈希，我本人是很反对这个叫法的，事实上HashMap扩容的时候，Node中存储的Key的hash值并没有发生变化，只是Node的位置发生了变化。

首先说为什么需要扩容？这个问题好像有点简单，不就是因为容量满了就需要库容了吗？这种思想对于链表来说是没有问题的，但是对于HashMap来说，并不是因为这个原因，而是HashMap认为性能不够好时。

原因我简单说下，当然关于哈希表我就不再过多说了，还不懂的同学赶紧百度。

为什么扩容？

我们知道理论上哈希表的读时间复杂度是O(1)，但是没有一种哈希方法能保证绝对的哈希均匀，为了解决哈希冲突又往往采用链地址法解决，那这样时间复杂度愈发偏离O(1)了，此时进行扩容，其实是让哈希表分散的更均匀，解决性能不够好的问题。

关于JDK1.8中的HashMap结构，在这里我就不多说了，哈希表 链表，长度达到一定时链表转换成红黑树（这时候是不是得有面试官出来问，长度多长才转红黑树啊？），为了让小伙伴们看的更直观，我这里偷一张图上来：

什么时候扩容？

那么什么时候需要扩容？答案也很简单：1.初始化后放入元素时 2.达到阈值时

  1. 创建对象以后，HashMap并不是立即初始化table，而是在第一次放入元素时，才会初始化table，这很HashMap节省内存得一种机制，而table的初始化其实是resize方法实现的。
  2. 达到阈值时，这个就比较有意思，所谓阈值，就是HashMap中threshold这个属性，阈值的计算方式很简单，基本上就是capacity（table容量） * loadFactor（负载因子），这里我觉得capacity应该称为理论容量，是因为正常情况下达到阈值就扩容了，达到阈值时HashMap认为哈希冲突的次数会不能接受，因此需要扩容。

因为这里我是以JDK1.8源码作为样本分析的，如果我没记错的话，JDK1.7中还存在rehash方法，但是JDK1.8中已经改名叫resize方法了，那我们就不管JDK1.7中是如何实现扩容，直接上JDK1.8源码。

如何扩容？

先来看扩容函数的前半部分：

代码语言：javascript复制
final Node<K,V>[] resize() { 

// 扩容前原本的table
Node<K,V>[] oldTab = table;
// 这里进行判断，区分尚未初始化的情况 
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { 
 // 非初始化情况
/* * 当原本的capacity已经超过最大值以后 * HashMap选择不再扩容，然后threshold置为最大值 */
if (oldCap >= MAXIMUM_CAPACITY) { 

threshold = Integer.MAX_VALUE;
return oldTab;
}
/* * 这种是常见的的扩容情况，table容量会扩大两倍 * 同时HashMap的阈值也跟着扩大两倍 */
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 2倍阈值
}
else if (oldThr > 0) // 指定大小n的初始化情况下，table容量取>n的最小2倍数
newCap = oldThr;
else { 
               // 不指定初始化大小，table容量取默认值16
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { 
 
// 指定大小初始化情况下，阈值 = table容量 * 负载因子(默认0.75)
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 最后确定阈值
threshold = newThr;
待续......
}

resize()方法的前半部分主要是对于新阈值和新容量的确定，这里有三种情况：

  1. 初始化已完成的正常扩容逻辑：table容量和阈值都扩大2倍
  2. 指定大小的初始化逻辑：算出大于等于指定初始化容量的最小2的倍数，作为table容量
  3. 未指定大小的初始化逻辑：默认table容量16，阈值为16 * 0.75 = 12

关于第二种逻辑，简单来说就是，指定初始化值为3，那么table容量就是4，如果指定初始化大小是10，那么table容量就是16，如果是2的次幂，就直接作为table容量。

再看resize方法的后半段：

代码语言：javascript复制
final Node<K,V>[] resize() { 

......接上文
@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) { 
 
// 遍历原本的table
Node<K,V> e;
if ((e = oldTab[j]) != null) { 

oldTab[j] = null; // 为了GC
if (e.next == null)
// 如果table上没有链表的情况下，直接转移到对应位置
// 转移到的位置就是get方法中取的下标位置，tab[(n - 1) & hash]
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;
// 如果entry的哈希值高位为0，会被拆分到lo链表
if ((e.hash & oldCap) == 0) { 

if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { 

// 如果entry的哈希值高位为1，会被拆分到hi链表 
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { 

loTail.next = null;
// 高位是0，因此lo链表不需要移位，
// hash & (newCap-1)和hash & (oldCap-1)获得下标位置一样
newTab[j] = loHead;
}
if (hiTail != null) { 

hiTail.next = null;
// 高位是1，hi链表移位到 j oldCap位置，
// j   oldCap相当于高位补1，直接移到这个位置
newTab[j   oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

这里为了能说的更通俗易懂一些，我举个简单的例子：

首先假设原本有几个key，他们的的hash值为：

key

hash值

下标 hash & (length-1)

key1

00000101

00000101 = 5

key2

00010101

00000101 = 5

key3

00100101

00000101 = 5

key4

00110101

00000101 = 5

而假设原本table容量 oldCap = 16;

他们在table中存储的下标位置都是：

代码语言：javascript复制
hash & (table.length-1) = 0101 & 0111

那么这几个key都会存储在table[5]位置，如下图 ：

当进行扩容时，容量扩大一倍也就是newCap = 32,此时table.length -1 = 31

hash & (table.length – 1) 就会出现两种情况：

  1. key1 和 key3 的下标还是5 （0000 0101）
  2. key2 和 key4 的下标变为了 21 (0001 0101)

key

hash值

下标 hash & (length-1)

key1

00000101

00000101 = 5

key2

00010101

00001101 = 21

key3

00100101

00000101 = 5

key4

00110101

00001101 = 21

到这应该能明白，resize方法里的lo列表和hi列表是什么意思了，其实就是看key高一位的哈希值是1还是0，来决定是放到哪个队列里。 移位后的HashMap如下图：

这里HashMap非常精妙的实现了扩容，没有重新计算对象的哈希值，甚至连下标的重新计算也只需要进行一位相与的计算（hash高位 & newCap-1 )。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/193523.html原文链接：https://javaforall.cn

hashmap jdk jquery 编程算法

0 人点赞