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

最近在翻看《阿里巴巴开发手册-嵩山版》即最新版时,发现其修正了关于「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, false, true);
  }

  /**
   * 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次数 容量 阈值 调用时机 最大存储元素个数
第一次 16 12 存放第1个元素时 12
第二次 32 24 存放第个24元素 24
第三次 64 48 存放第个48元素 48
第四次 128 96 存放第个96元素 96
第五次 256 192 存放第个196元素 196
第六次 512 384 存放第个384元素 384
第七次 1024 768 存放第个768元素 768
第八次 2048 1536 存放第个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次。

孤尽老师说对此分歧,希望用没有「二义性」的语言来表示,所以「扩容次数」修正为「resize次数」。

扫码领红包

微信赞赏支付宝扫码领红包

发表回复

后才能评论