面试官:”准备用HashMap存1w条数据,构造时传10000会触发扩容吗?“

您所在的位置:网站首页 hashmap创建时赋值 面试官:”准备用HashMap存1w条数据,构造时传10000会触发扩容吗?“

面试官:”准备用HashMap存1w条数据,构造时传10000会触发扩容吗?“

2023-10-09 19:14| 来源: 网络整理| 查看: 265

// 预计存入1w条数据,初始化赋值10000,避免 resize。 HashMap map = new HashMap(10000) // for (int i = 0; i > 1;   n |= n >>> 2;   n |= n >>> 4;   n |= n >>> 8;   n |= n >>> 16;   return (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 = resize()).length; // 调用 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_VALUE;             return oldTab;         }         else if ((newCap = oldCap 


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3