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

  • 时间:
  • 浏览:2
  • 来源:极速快3_快3讨论群_极速快3讨论群

// 预计存入 1w 条数据,初始化赋值 100000,处理 resize。
HashMap<String,String> map = new HashMap<>(100000)
// for (int i = 0; i < 100000; i++)

Java 集合的扩容

HashMap 算不算 亲戚亲戚我们我们我们都 最常用的集合之一,觉得对于 Android 开发者,Google 官方推荐了更省内存的 SparseArray 和 ArrayMap,否则 HashMap 依然是最常用的。

亲戚亲戚我们我们我们都 通过 HashMap 来存储 Key-Value 你你这个键值对形式的数据,其结构通过哈希表,让存取数率最好时还都可以 达到 O(1),而又是因为分析着是因为分析着趋于稳定的 Hash 冲突,引入了链表和红黑树的型态,让数率最差也差不过 O(logn)。

整体来说,HashMap 作为一款工业级的哈希表型态,数率还是有保障的。

编程语言提供的集合类,觉得底层还是基于数组、链表你你这个最基本的数据型态,否则和亲戚亲戚我们我们我们都 直接使用数组不同,集合在容量匮乏时,会触发动态扩容来保证有足够的空间存储数据

动态扩容,涉及到数据的拷贝,是并算不算「较重」的操作。那是因为分析着还都可以 提前选取集合将要存储的数据量范围,就还都可以 通过构造土法子 ,指定集合的初始容量,来保证接下来的操作中,不至于触发动态扩容。

这就引入了本文开篇的问題,是因为分析着使用 HashMap,当初始化是构造函数指定 1w 时,后续亲戚亲戚我们我们我们都 立即存入 1w 条数据,算不算 符合与其不用触发扩容呢?

在分析你你这个问題前,原来 们先来看看,HashMap 初始化时,指定初始容量值都做了有哪些?

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

HashMap 的初始化

在 HashMap 中,提供了另2个 指定初始容量的构造土法子 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 初始化

当亲戚亲戚我们我们我们都 把初始容量,调整到 10000 时,情况表又不一样了,情况表表具体分析。

再回到 HashMap 的构造土法子 ,threshold 为扩容的阈值,在构造土法子 中由 tableSizeFor() 土法子 调整后直接赋值,全都在构造 HashMap 时,是因为分析着传递 10000,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<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length; // 调用 resize()
    // ...
}

resize() 土法子 中,调整了最终 threshold 值,以及完成了 table 的初始化。

final Node<K,V>[] resize() {
    Node<K,V>[] 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 << 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) {
        // ②
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // ③
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab; // ④
    // ....
}

注意看代码中的注释标记。

是因为分析着 resize() 还糅合了动态扩容的逻辑,全都我将初始化 table 的逻辑用注释标记出来了。其中 xxxCap 和 xxxThr 分别对应了 table 的容量和动态扩容的阈值,全都趋于稳定旧和新两组数据。

当亲戚亲戚我们我们我们都 指定了初始容量,且 table 未被初始化时,oldThr 就不为 0,则会走到代码 的逻辑。在其中将 newCap 赋值为 oldThr,也否则新创建的 table 会是亲戚亲戚我们我们我们都 构造的 HashMap 时指定的容量值。

刚刚该进入代码 的逻辑,其中就通过装载因子(loadFactor)调整了新的阈值(newThr),当然这里也做了一些限制时要让 newThr 在另2个 合法的范围内。

在代码 中,将使用 loadFactor 调整后的阈值,重新保存到 threshold 中。并通过 newCap 创建新的数组,将其指定到 table 上,完成 table 的初始化(代码 )。

到这里也就清楚了,觉得亲戚亲戚我们我们我们都 在初始化时,传递进来的 initialCapacity 觉得被赋值给 threshold,否则它实际是 table 的尺寸,否则最终会通过 loadFactor 重新调整 threshold

那么回到刚刚的问題也有答案了,觉得 HashMap 初始容量指定为 10000,否则它否则表示 table 数组为 10000,扩容的重要土法子 扩容阈值会在 resize() 中调整为 768(1024 * 0.75)。

它是匮乏以承载 10000 条数据的,最终在存够 1k 条数据刚刚,总要触发一次动态扩容。

通常在初始化 HashMap 时,初始容量也有根据业务来的,而不用是另2个 固定值,为此亲戚亲戚我们我们我们都 时要有另2个 特殊处理的土法子 ,否则将预期的初始容量,再除以 HashMap 的装载因子,默认时否则除以 0.75。

之类于想要用 HashMap 存放 1k 条数据,应该设置 10000 / 0.75,实际传递进去的值是 1333,然总要被 tableSizeFor() 土法子 调整到 2048,足够存储数据而不用触发扩容。

当想用 HashMap 存放 1w 条数据时,依然设置 100000 / 0.75,实际传递进去的值是 13333,会被调整到 16384,和亲戚亲戚我们我们我们都 直接传递 100000 效果是一样的。

小结时刻

到这里,就了解清楚了 HashMap 的初始容量,应该咋样科学的计算,本质上你传递进去的值是因为分析着并无法直接存储那么多数据,会有另2个 动态调整的过程。其中就时要将亲戚亲戚我们我们我们都 预期的值进行放大,比较科学的否则土法子 装载因子进行放大。

最后亲戚亲戚我们我们我们都 再总结一下:

  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 数据量范围,还都可以 预设 HashMap 的容量值来提升数率,否则时要注意要考虑装载因子的影响,还都可以 保证不用触发预期之外的动态扩容。

HashMap 作为 Java 最常用的集合之一,市面上优秀的文章全都,否则很少人们从初始容量的宽度来分析其中的逻辑,而初始容量又是集合中比较实际的优化点。觉得不少人也搞不清楚,在设置 HashMap 初始容量时,算不算 应该考虑装载因子,才有了此文。

是因为分析着本文对你有所帮助,留言、转发、点好看是最大的支持,谢谢!


公众号后台回复成长『成长』,是因为分析着得到我准备的学习资料,还都可以 回复『加群』,同去学习进步。