最近回顾了下 HashMap 的源码(JDK1.7),当读到 putAll 方法时,发现了之前写的 TODO 标记,当时由于时间匆忙没来得及深究,现在回顾到了就再仔细思考了下

 @Override public void putAll(Mapextends K, ? extends V> m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; // TODO 这里的 numKeysToBeAdded 是不是应该要 this.size+m.size() 呢? // TODO 这里确实有点问题,下面的 for 循环中 put 操作可能会导致再次 resize,奇怪怎么没人提出这个问题呢?
    if (numKeysToBeAdded > threshold) { // +1 是为了补上被强转为 int 而抹去的小数部分
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity)
            newCapacity <<= 1; if (newCapacity > table.length)
            resize(newCapacity);
    } for (Map.Entryextends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
            }

  如注释中所示 numKeysToBeAdded > threshold 就是想提前判断 Map 是否需要扩容,如果需要的话则直接一步到位,从而防止循环中的 put 操作引起多次扩容,以次来减小 resize 方法带来的性能开销。

但是:我们看方法的第一行,int numKeysToBeAdded = m.size(); 如果要实现扩容一步到位的话,这里的 numKeysToBeAdded 不应该是当前 Map 的 size 加 m 的 size 之和吗? this.size + m.size() > threshold

就扩容才能保证 m 中所有元素添加到当前 HashMap 后只触发一次 resize 。

  测试代码如下,直接 debug HashMap 的 putAll 方法,我们可以看到整个 putAll 是进行了两次 resize

    Map map = new HashMap(4);
    Map m = new HashMap(8);
    map.put("a", "haha");
    map.put("b", "haha");
    map.put("c", "haha");
    m.put("1", "a");
    m.put("2", "a");
    m.put("3", "a");
    m.put("4", "a");
    map.putAll(m);

  JDK1.8 的 HashMap 已经实现已经做了很大的修改,但是当我切换到 1.8 debug 时还是 resize 了两次,为什么呢?仔细看下面的注释(当时看源码的时候直接把这段注释忽略了,汗),JDK 的大神们给出了如下的解释,显然他们也知道这个问题,但是主要考虑到 m 和当前的 HashMap 中可能存在重复的 key,这样的话就可能造成 HashMap 浪费了比较大的空间(画外音:HashMap 默认加载因子为 0.75 的设计初衷不就是采取了空间换时间的思想嚒??)

    /* * Expand the map if the map if the number of mappings to be added
     * is greater than or equal to threshold.  This is conservative; the
     * obvious condition is (m.size() + size) >= threshold, but this
     * condition could result in a map with twice the appropriate capacity,
     * if the keys to be added overlap with the keys already in this map.
     * By using the conservative calculation, we subject ourself
     * to at most one extra resize. */

在 HashMap 中 size 肯定会小于或等于 threshold ,所以 putAll 时当 m.size()> threshold 进行扩容,HashMap 的容量增加至少 1 倍,则因为存在 m.size() > size 所以就算 m.size()+ size > threshold( 第一次扩容后) 只要再做一次扩容就可以满足 HashMap 的规则了。

更全的学习注释可以参考:https://github.com/hiccup234/misc/blob/master/src/main/java/top/hiccup/jdk/container/mycontainer/MyHashMap7.java

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    2389 引用 • 6835 回帖 • 1160 关注
感谢    关注    收藏    赞同    反对    举报    分享