面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端

// 估计存入 1w 条数据,初始化赋值 10000,防止 resize。
HashMap map = new HashMap<>(10000)
// for (int i = 0; i < 10000; i++)

Java 调集的扩容

HashMap 算是咱们最常用的调集之一,尽管关于 Android 开发者,Google 官方引荐了更省内存的 SparseArray 和 ArrayMap,可是 HashMap 仍然是最常用的。

咱们经过 HashMap 来存储 Key铭铭胶水-Value 这种键值对办法的数据,其内部经过哈希表,让存取功率最好时能够到达 O(1),而又由于或许存在的 Hash面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端 抵触,引入了链表和红黑树的结构,让功率最差也差不过 O(logn)。

全体来说,HashMap 作为一款工业级的哈希表结构,功率仍是有确保的。

编程言语供给的调集类,尽管底层仍是根据数组、链表这种最根本的数据结构,可是和咱们直接运用数滥竽充数组不同,调集在容量缺乏时,会触发动态扩容来确保有满足的空间存储数据

动态扩容,触及到数据的复制,是一种「较重」的操作。那假如能够提早确认调集即将存储的数据量规模,就能够经过结构办法,指定调集的初始容量,来确保接下来的操作中,不至于触发动态扩容。

这就引入了本文开篇的问题,假如运用 HashMap,最初王瑞侯勇始化是结构函数指定 1w 时,后续咱们当即存入 1w 条数据,是否契合与其不会触发扩容呢?

在剖析这个问题前,那咱们先来看看,HashMap 初始化时,指定初始容量值都做了什么?

PS:本文所触及代码,均以 JDK 1.8 中 HashMap 的源码举例。

HashMap 的初始化

在 HashMap 中,供给了一个指定初始容量的结构办法 HashMap(int initialCapacity),这个办法终究会调用到 HashMap 另一个结构办法,其间的参数 loadFactor 便是默许值 0轿车电瓶寿数.75f。

public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "本庄優花 + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor刘海燕哈弗(initialCapacity);
}

其间的成员变量 threshold 便是用来存储,触发 HashMap 扩容的阀值,也便是说,当 HashMap 存储的数据量达国外天体到 threshold 时,就会触发扩容。

从结构办法的逻辑能够看出,HashMap 并不是直接运用外部传递进来的 initialCapacity,而是经过了 tableSizeFor() 办法的处理,再赋值到 threshole 上。

static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

在 tableSizeFor() 办法中,经过逐渐位运算,就能够让返回值,保持在 2 的 N 次幂。以方便在扩容的时分,快速核算数据在扩容后的新表中的方位癔症。

那么当咱们从外部传递进来 1w 时,实践上经过 tableSizeFor() 办法处理之后,就会变成 2 的 14 次幂 16384,再算上负载因子 0.75f,实践在不触发扩容的前提下,可存储的数据容量是 12288(16384 * 0.75f)。

这种场景下,用来寄存 1w 条数据,捉襟见肘了,并不会触发咱们猜测的扩容。

HashMap 的 table 初始化

当咱们把初始容量,调整到 1000 时,状况又不相同了,详细状况详细剖析。

再回到 HashMap 的结构办法,threshold 为扩容重庆极地海洋国际的阀值,在结构办法中由 tableSizeFor() 办法调整后直接赋值,所以在结构 HashMap 时,假如传递 1000,threshold 调整后的值确实是 1024,但 HashMap 并不直接运用它。

细心想想就会知道,初始化时决议了 threshold 值,但其装载因子(loadFactor)并没有参加运算,那在后面详细逻辑的时分,HashMap 是怎么处理的呢?

在 HashMap 中,一切的数据,都是经过成员变量 table 数组来存储的,在 JDK 1.7 和 1.8 中尽管 table 的类型有所不同,可是数组这种根本结构并没有改变。那么 table、threshold、loadFactor 三者之间的联系,便是:

table.size == threshold * loadFactor

那这个 table 是在什么时分初始化的呢?这就要说会到咱们一直在逃避的问题,HashMap 的扩容。

在 HashMap 中,动态扩容的逻辑在 resize() 办法中。这个办法不仅仅承当了 table 的扩容,它还承当了 table 的初始化。

当咱们初次调用 HashMap 的 put() 办法存数据时,假如发现 table 为 null,则会调用 resize() 去初始化 table,详细逻辑在 putVal() 办法中。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端 = resize()).length; // 调用 面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端resize()
// ...
}

在 resize() 办法中,调整了终究 threshold 值,以及完结了 table 的初始化。

final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_触手tvVALUE;
return oldTab;
眼角痒}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr; // ①
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);正大集团
}
if (newThr == 0) {
面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端// ②
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // ③
Node[] newTab = (Node[])new Node[newCap];
table = newTab; // ④
// ....
}

留意看代码中的注释符号。由于 resize() 还糅合了动态扩容的逻辑,所以我将初始化 table 的逻辑用注释符号出来了。其间 xxxCap 和 xxxThr 别离对应了 table 的容量和动态扩容的阀值,所以存在旧和新两组数据。

当咱们指定了初始容量,且 table 未被初始化时,oldThr 就不为 0,则会走到代码 ① 的逻辑。在其间将 newCap 赋值为 oldThr,也便是新创立的 table 会是咱们钵结构的 HashMap 时指定的容量值。

之后会进入代码 ② 的逻辑,其间就经过装载因子(loadFactor)调整了新的阀值(newThr),当然这儿也做了一些约束需求让 newThr 在一个合法的规模内。

在代码 ③ 中,将运用 loadFactor 调整后的阀值,从头保存到 threshold 中。并经过 newCap 创立新的数组,将其指定到 table 上,完结 table 的初始化(代码 ④)。

到这儿也就清楚了,尽管咱们在初始化时,传递进来的 initialCapacity 尽管被禁片排行赋值给 thrdj热舞eshold,可是它实践是 table 的尺度,而且终究会经过 loadFactor 从头调整 threshold。

那么回到之前的问题就有答案了,尽管 HashMap 初始容量指定为 1000,可是它仅仅表明 table 数组为 1000,扩容的重要根据扩容阀值会在 resize() 中调整为 768(1024 * 0.75)。

它面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端是缺乏以承载 1000 条数据的,终究在存够 1k 条数据之前,还会触发一次动态扩容。

通常在初始化 HashMap 时,初始容量都王局志安是根据事务来的,而不会是一个固定值,为此咱们需求有一个特别处理的办法,便是将预期的初始容量,再除以 HashMap 的装载因子,默许时便是除以面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端 0.75。

例如想要用 HashMap 寄存 1k 条数据,应该设置 1000 / 0.75,实践传递进去的值是 1333,然后会被 tableSizeFor() 办法调整到 2048,满足存储数据而不会触发扩容。

当想用 HashMap 寄存 1w 条数据时,仍然设置 10000 / ppt背景图0.75,实践传递进去的值是 13333,会被调整到 16384,和咱们直接传递 10000 作用是相同的。

小结时间

到这儿,就了解清楚了 HashMap 的初始容量,应该怎么科学的核算,本质上你传递进去的值或许并无法直接存储这么多数据,会有一个动态调整的进程。其间就需求将咱们预期的值进行扩大,比较科学的便是根据装载因子进行扩大。

终究咱们再总结一下:

  1. HashMap 结构办法传递的 initialCapacity,尽管在处理后被存入了 loadFactor 亲密联系中,但它实践表明 table 的容量。
  2. 结构办法传递的 initialCapacity,终究会被 tableSizeFor() 办法动态调整为 2 的 N 次幂,以方便在扩容的时分,核算数据在 newTable 中的方位。
  3. 假如设置了 table 的初始容量,会在初始化 table 时,将扩容阀值 threshold 从头调整为 table.size * loadFactor。
  4. HashMap 是否扩容,由 threshold 决议,而 threshold 又由初始容量和 loadFactor 决议。
  5. 假如咱们预先知道 HashMap 数据量规模,能够预设 alreadyHashMap 的容量值来提高功率,可是需求留意要考虑装载因子的影响,才干确保不会触发预期之外的动态扩容。

HashMap 作为 Java 最常用的调集之一,市面上优异的文章许多,可是很少有人从初始容量的视点来剖析其间的逻辑,而初始容量又是调集中比较实践的优化点。其实不少人也搞不清楚,在设置 HashMap 初始容量时,是否应该考虑装载因子,才有了此文。

假如本文对你有所协助,留言、转发、点赞是最大的支撑,谢谢!


在头条号私信我。我会送你一些我收拾的学习材料,包括:Android反编译、算法、规划形式、虚拟机、Linux、Kotlin、Python、爬虫、Web项面试官:“在HashMap中保存1w的数据,在结构上传达10000会诱发扩张吗? " "-betway体育注册_必威体育网站-必威客户端目源码。

评论(0)