hashmap扩容面试_面试必问系列之你必须知道的HashMap扩容

灰太狼 2023-01-09 12:56 157阅读 0赞

前面我们已经看过HashMap中put方法的内部实现流程啦，那么今天我们就来一起看看resize()方法到底做了些什么吧！我们继续来看下JDK 1.8中HashMap resize()方法的源码：

final Node\[\] resize() \{

Node\[\] oldTab = table;

//获取当前tab的容量

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

int oldThr = threshold;

int newCap, newThr = 0

//判断容量是否大于0

if (oldCap > 0) \{

//判断容量是否超过最大容量，如超过最大容量，则将阈值设置为最大容量

if (oldCap >= MAXIMUM\_CAPACITY) \{

threshold = Integer.MAX\_VALUE;

return oldTab;

//判断将当前tab容易扩大一倍后是否小于最大容量并大于等于初始容量

//如果满足，则将阈值扩大一倍

else if ((newCap = oldCap << 1) < MAXIMUM\_CAPACITY &&

oldCap >= DEFAULT\_INITIAL\_CAPACITY)

newThr = oldThr << 1; // double threshold

//如果当前tab容量为0并且阈值大于0，则将新容量设置为阈值

else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

else \{ // zero initial threshold signifies using defaults

//设置默认容量，设置阈值

newCap = DEFAULT\_INITIAL\_CAPACITY;

newThr = (int)(DEFAULT\_LOAD\_FACTOR \* DEFAULT\_INITIAL\_CAPACITY);

//此处针对有传入初始容量的实例，计算新的阈值

if (newThr == 0) \{

float ft = (float)newCap \* loadFactor;

newThr = (newCap < MAXIMUM\_CAPACITY && ft < (float)MAXIMUM\_CAPACITY ?

(int)ft : Integer.MAX\_VALUE);

//设置新的阈值

threshold = newThr;

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

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

table = newTab;

if (oldTab != null) \{

//遍历节点数组，将节点移入新的节点数组table

for (int j = 0; j < oldCap; ++j) \{

Node e;

if ((e = oldTab\[j\]) != null) \{

oldTab\[j\] = null;

//如果该位置只有一个节点则计算index索引并移入

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;

//重新计算索引位置

//e.hash & oldCap == 0 存入lo链,否则存入hi链

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);

//将lo链存入当前位置

if (loTail != null) \{

loTail.next = null;

newTab\[j\] = loHead;

//将hi链存入oldCap+j位置

if (hiTail != null) \{

hiTail.next = null;

newTab\[j + oldCap\] = hiHead;

return newTab;

复制代码

相信很多小伙伴看到e.hash & oldCap这句话很费解，但相信看了下面的例子后，小伙伴们就能明白了。

首先，我们假设oldCap为16，当前j=3,此时这个位置的链表上有A、B两个节点，这两个节点的(n-1)&hash=3,那么我们是不是可能理解为下面的情况：

hash(A): 0000 ... 0000 0011

hash(B): 0000 ... 0001 0011

n-1(15): 0000 ... 0000 1111

结果：

A: 0000 ... 0000 0011

B: 0000 ... 0000 0011

复制代码

那么 oldCap&hash 也就是 n&hash，是不是可以如下理解呢

hash(A): 0000 ... 0000 0011

hash(B): 0000 ... 0001 0011

n(oldCap): 0000 ... 0001 0000 结果: A:0 B：16

newCap-1: 0000 ... 0001 1111 结果: A:3 B:19 (oldCap+j)

复制代码

通过这样一对比，大家发现没有，容量扩大一倍后计算位置与旧tab的索引index存在一定联系。

当 oldCap & hash = 0 时，新表位置与旧表保持一致

当 oldCap & hash != 0 时，新表位置为oldCap+j

复制代码

在扩容的时候通过这种方式，将一个链表合理的拆分成为了两部分，还省去了重新计算hash值的时间。这个设计是不是很精妙呢，反正我已经给作者献上了膝盖了。

hashmap扩容面试_面试必问系列之你必须知道的HashMap扩容

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 java八股文面试[数据结构]——HashMap扩容优化

相关 HashMap扩容机制

相关 hashmap 扩容机制

相关 HashMap扩容机制

相关 Java之HashMap系列--HashMap扩容的原理

相关面试必问之HashMap

相关 HashMap 扩容原理

相关 hashmap扩容面试_面试必问系列之你必须知道的HashMap扩容

相关 HashMap扩容机制

相关 HashMap的扩容