大发pk10_pk10下载_大发pk10下载 - 由大发pk10,pk10下载,大发pk10下载社主办的《大发pk10,pk10下载,大发pk10下载》是我国消费领域中一张全国性、全方位、大容量的综合性日报。其立足消费网投领域,依托轻工行业,面向城乡市场,最先发布相关的专业权威资讯。

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

  • 时间:
  • 浏览:1

// 预计存入 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 中,提供了1个多指定初始容量的构造法律法律依据 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 在1个多合法的范围内。

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

到这里也就清楚了,人太好 当我们都都 儿在初始化时,传递进来的 initialCapacity 人太好 被赋值给 threshold,咋样让 它实际是 table 的尺寸,咋样让 最终会通过 loadFactor 重新调整 threshold

没有 回到很久 的什么的问题就有答案了,人太好 HashMap 初始容量指定为 10000,咋样让 它本来我表示 table 数组为 10000,扩容的重要法律法律依据扩容阈值会在 resize() 中调整为 768(1024 * 0.75)。

它是不足以承载 10000 条数据的,最终在存够 1k 条数据很久 ,就有触发一次动态扩容。

通常在初始化 HashMap 时,初始容量就有根据业务来的,而不必是1个多固定值,为此当我们都都 儿需要有1个多特殊除理的法律法律依据,本来我将预期的初始容量,再除以 HashMap 的装载因子,默认时本来我除以 0.75。

例如愿意用 HashMap 存放 1k 条数据,应该设置 10000 / 0.75,实际传递进去的值是 1333,然就有被 tableSizeFor() 法律法律依据调整到 2048,足够存储数据而不必触发扩容。

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

小结时刻

到这里,就了解清楚了 HashMap 的初始容量,应该咋样科学的计算,本质上你传递进去的值原应并无法直接存储没有 多数据,会有1个多动态调整的过程。其中就需要将当我们都都 儿预期的值进行放大,比较科学的本来我法律法律依据装载因子进行放大。

最后当我们都都 儿再总结一下:

  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 初始容量时,是否 应该考虑装载因子,才有了此文。

原应本文对你有所帮助,留言、转发、点好看是最大的支持,谢谢!


公众号后台回复成长『成长』,原应得到我准备的学习资料,也能回复『加群』,共同学习进步。