在途中

Good Luck To You!

为什么阿里巴巴修正了HashMap关于1024个元素扩容的次数?

   图片  

    来源:juejin.cn/post/7302724955699789863


  • 引言
  • 第一次put调用resize()
  • 调用resize()的次数
  • 总结

引言

最近在翻看《阿里巴巴开发手册-嵩山版》即最新版时,发现其修正了关于「HashMap关于1024个元素扩容的次数」 在先前的版本泰山版我们可以看到以下描述:

图片

图片

而最新版嵩山版则可以看到:

图片

图片

同时我们也可在嵩山版的版本历史中看到对以上变化的描述:

图片

图片

并且我在官网文档中也同样发现了采访视频对这一变化,主持人对孤尽老师提出了以下疑问:

主持人:

有同学问,嵩山版修正了 HashMap 关于 1024 个元素扩容的次数?那么这个泰山版中是七次扩容,我感觉是正确的,为什么现在进行了修改?

孤尽老师:

大家可以看到嵩山版描述都改了,就没有讲「扩容」,讲叫「resize」的次数。因为 resize 的这个次数的话,我们在调 resize 的时候,就 put,如果你new了一个 HashMap 它并不会给你分配空间,第一次 put 的时候,它才会给你分配空间。所以就是说我们在第一次 put 的时候,也会调 resize。但是很多同学就会争议,说这个算不算扩容?那其实就是说我们在这个点上,其实为了,因为计算机我们大家都是搞计算机的,都希望用没有「二义性」的语言来表示。所以在嵩山版本里面进行了修改,然后我们改成了 resize 的方式来说明这到底是它的容量是如何变化的。因为扩容这个词的话,大家的理解是不一样的。这也是我们有一次大概在业界我们有一个打卡就是一个打卡测试题,这个题里面我们有一个选项。当时选的同学是两种答案,但是这两种答案都是有自己的道理。所以我们也是借鉴了这个看法,然后在这个嵩山版里面也写的更加明确了。就是叫 resize 的次数,不叫扩容的次数。

以下是文档下载链接和采访视频地址。

https://developer.aliyun.com/topic/java20

我们可以从孤尽老师的回答中提炼出主要发生的变化是:

  • 扩容次数修改为「resize次数」 。主要的问题是每个人对「扩容」这个定义存在分歧。
  • 扩容的主要分歧是在:没有给 HashMap 进行初始化的时候,第一次 put 的时候才会分配空间,也会调用 resize。那这操作个算不算扩容?即初始化容量这个操作算不算扩容?
  • 所以扩容次数修改为 resize 次数。

图片

图片

那么我们先来看一下第一次 put 的时候调用 resize 这个操作是什么?

第一次put调用resize()

前面孤尽老师的回答中也强调了这个 put() 方法调用 resize() 方法是存在一个条件的:

「如果你new了一个HashMap它并不会给你分配空间。同时文档中也写了由于没有设置容量初始大小。」

除了这个条件其实还有一个额外的条件,就是这是在 JDK1.8 之后 HashMap 才会有的操作。以下源码都来自 JDK1.8。

要理解这句话我们首先要看下 HashMap 的源码,看下它的构造器方法。

图片

图片

存在四个构造方法

//参数:初始容量,负载因子
public HashMap(int initialCapacity, float loadFactor) {  }  

//参数:初始容量。调用上一个构造函数,默认的负载因子(0.75)
public HashMap(int initialCapacity) {  this(initialCapacity, DEFAULT_LOAD_FACTOR);  }  

//参数:无参构造器。创建的HashMap具有默认的负载因子(0.75)
public HashMap() {  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  }  

//参数:使用与指定Map相同的映射构造一个新的HashMap。创建的HashMap具有默认的负载因子(0.75)和足够在指定Map中保存映射的初始容量。
public HashMap(Map<? extends K, ? extends V> m) {  
    this.loadFactor = DEFAULT_LOAD_FACTOR;  
    putMapEntries(m, false);  
}

也就是说当我们使用一个无参构造器创建 HashMap 的时候。

Map<String,String> map = new HashMap<>();

调用的就是上述构造方法的第三个方法,只会设置默认的负载因子为 0.75。就没有其他操作了。。

而当我们对这个 HashMap 进行 put() 操作的时候。

Map<String,String> map = new HashMap<>();
map.put("first","firstValue");

我们看一下源码,进行了什么操作?

图片

图片
public V put(K key, V value) {
      return putVal(hash(key), key, value, falsetrue);
  }

  /**
   * Implements Map.put and related methods.
   *
   * @param hash hash for key
   * @param key the key
   * @param value the value to put
   * @param onlyIfAbsent if true, don't change existing value
   * @param evict if false, the table is in creation mode.
   * @return previous value, or null if none
   */
  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;
      if ((p = tab[i = (n - 1) & hash]) == null)
          tab[i] = newNode(hash, key, value, null);
      else {
          Node<K,V> e; K k;
          if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k))))
              e = p;
          else if (p instanceof TreeNode)
              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
          else {
              for (int binCount = 0; ; ++binCount) {
                  if ((e = p.next) == null) {
                      p.next = newNode(hash, key, value, null);
                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                          treeifyBin(tab, hash);
                      break;
                  }
                  if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                      break;
                  p = e;
              }
          }
          if (e != null) { // existing mapping for key
              V oldValue = e.value;
              if (!onlyIfAbsent || oldValue == null)
                  e.value = value;
              afterNodeAccess(e);
              return oldValue;
          }
      }
      ++modCount;
      if (++size > threshold)
          resize();
      afterNodeInsertion(evict);
      return null;
  }

其实调用的是内部的 putVal() 方法。同时我们也可看见我们前面的构造器方法中除了设置了负载因子,就没有其他操作了,所以是符合if ((tab = table) == null || (n = tab.length) == 0),大家也可 debug 断点打在这进行验证。所以就会执行下面的代码n = (tab = resize()).length;调用了一次 resize(),同时对 n 进行了赋值操作。

那么我们通过源码的确发现了,在 JDK1.8 中「由于没有设置 HashMap 容量初始大小」 ,在第一次进行 put()操作的时候,HashMap 会调用一次 resize() 方法初始化容量为 16。(resize 的源码也不是本篇文章的重点,所以我这边会直接提供结论,并且再次强调一下 JDK1.7 是会初始化容量为 16 的,而不是在是第一次进行 put() 操作时初始化容量。)

调用resize()的次数

在嵩山版中修订了 HashMap 关于 1024 个元素扩容的次数修改为:resize() 方法总共会调用 8 次。

那么我们来看一下到底是哪 8 次?

再次重申一下本篇文章主要是讲嵩山版对这个扩容次数的修改,本文不会再次分析会直接给出对应的结论为已知条件进行分析。如想知道更多细节和版本差异,请移步我的历史文章。

以下是我们可以从源码中得出的结论:

  1. HashMap 没有初始化容量时默认负载因子为 0.75,在第一次 put() 时会调用 resize() 进行初始化,容量为 16。(JDK1.8)
  2. HashMap 中的阈值 threshold 为capacity * load factor容量*负载因子。例如容量为 16,那么阈值 threshold 就为16*0.75=12。
  3. 当 HashMap 进行 put() 的时候,元素个数大于等于当前阈值的时候size>=threshold,会进行 resize() 操作。容量和阈值都会乘以 2。例如初始容量为 16,那么当我们 put 第 12 个元素的时候,就会进行 resize() 操作。

基于以上已知的结论,那么我们就能很容易的知道,在 JDK1.8 中没有给 HashMap 初始化容量时,存储 1024 个元素调用resize()的次数和时机了。(默认阈值为 0.75)

resize次数容量阈值调用时机最大存储元素个数
第一次1612存放第1个元素时12
第二次3224存放第个24元素24
第三次6448存放第个48元素48
第四次12896存放第个96元素96
第五次256192存放第个196元素196
第六次512384存放第个384元素384
第七次1024768存放第个768元素768
第八次20481536存放第个1536元素1536

所以在第 7 次进行 resize() 后,HashMap 的 capacity 为 1024 了,但是当我们存放第 768 个元素时,size>=threshold就会进行第 8 次扩容,此时才能真正的存放下 1024 个元素。

所以在 JDK1.8 中没有给 HashMap 初始化容量时,存储 1024 个元素,会调用resize() 8 次。

其实 resize() 操作也是十分消耗性能的,我们存储 1024 个元素的时候没有设置初始值就会调用 8 次。如果我们给其设置了 2048 容量,那么我们可以避免了。所以阿里巴巴同时建议我们给 HashMap 初始化时给定容量。

总结

此番修正主要是每个人对「扩容」定义存在了分歧,在 JDK1.8 中如果没有给 HashMap 设置初始容量,那么在第一次put()操作的时候会进行 resize()。而有的人认为这算一次扩容,有的人认为这不是一次扩容,这只是 HashMap 容量的初始化。

所以存储 1024 的元素时:

  • 前者的人认为扩容次数为8次。
  • 后者的人认为扩容次数为7次。



«    2024年1月    »
1234567
891011121314
15161718192021
22232425262728
293031
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
    文章归档
    网站收藏
    友情链接

    Powered By Z-BlogPHP 1.7.3

    Copyright 11taotao.com Rights Reserved.