为什么 hashmap 里 putMapEntries 只判断传入 map 的 size 是否大于当前 map 的阈值呢？

源码为 jdk1.8.

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            //说明 table 已经初始化过了，直接判断 s 是否大于当前 map 的阈值
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

但是else if (s > threshold)这里为什么不直接写成else if ((s + size) > threshold)呢？难道不应该把传入 map 的映射数量和当前 map 的映射数量加起来再比吗？

这样的话，可能在最后的循环里的某个 putVal 里，又会再次 resize 啊。

还有一个问题就是，为什么 float ft = ((float)s / loadFactor) + 1.0F;最后还要加 1 啊？就是因为这个加 1，导致下面这段代码：

import java.util.*;

public class test1 {
    public static void main(String[] args) {
        HashMap<String,Integer> oldMap = new HashMap<String,Integer>();
        for(int i=0;i<12;i++){
            oldMap.put(""+i,i);
        }
        HashMap<String,Integer> newMap = new HashMap<String,Integer>(oldMap);
        System.out.println();
    }
}

里面的 newMap 明明和 oldMap 的映射数量一样，但是其容量和阈值都是 oldMap 的二倍了。可见 oldMap 的容量是 16，阈值是 12.但 newMap 的容量是 32，阈值是 24. 因为 12/0.75=16，16 再加=17,17 再 tableSizeFor 得到 32.

KentY

2019-12-19 02:48:03 +08:00

为什么 /factor +1 比较好理解, 因为后面比较 threshold 等都是 int 比较, 刚刚 /factor 是个 float, 你后面的例子正好整除, 但是大多数不会是整数结果, 如果是 3.1, 比如, 那我们应该取 4 不能是 3, 也就是(int)(3.1+1)

另一个为什么不把自身的 size 加上. 我理解是当 s 就比 threshold 大了, resize 的 requirement 的概率就很大(并不是 100%), 而且 the more empty the table is, the cheaper the resize() costs. 所以提前 resize(), 因为 resize 是按照 2 的幂来的, 后面 put 是否需要不一定. 如果加上自身的, 即使> threshold, 虽然可能也会需要 resize, 可概率不如不加大, 所以就等到需要的时候再进行. (这是我的理解)

至于你 concern 的那个 "可能在最后的循环里的某个 putVal 里，又会再次 resize 啊" 这个对于加不加自身 size 几乎没影响. 如果需要后面再次 resize 的情况, 你＋了自身 size 判断, 一样会需要再 resize.

amiwrong123

2019-12-19 09:55:19 +08:00

@KentY
谢谢回答。

为什么 /factor +1 你的解释我大概理解了，就是说如果是小数的话，那么应该向上取整，即使我这种情况会让容量和阈值变成应有的二倍。那是不是意思就是 /factor +1 是为了保护某个特例，这种特例如果不加 1 就会造成容量和阈值都不够大，但是我现在又想不出来这种特例（就是 s 为多少时，这里就必须加 1 了）。。。

为什么不把自身的 size 加上，你说的我也大概懂了。大概就是 hashmap 的懒汉模式吧。
比如 s > threshold，且当前 map 的映射集合是传入 map 的映射集合的子集时（如果是子集，会使得两个 map 合并后，映射数量最少），即使是合并后映射数量最少的情况，也是必须 resize 的。
如果 s <= threshold，且传入 map 的映射集合是当前 map 的映射集合的子集时，这种情况就肯定不需要 resize 了。（这种情况很极端，其他情况还是有可能在后面的循环里再次 resize 的）

dyrone

2019-12-19 13:08:00 +08:00

部门描述：～

代码平台（代码托管、代码效能、代码智能）是阿里巴巴一站式智能研发协同平台的核心服务，对内为阿里几万产品研发相关人员提供工具支撑，对外是阿里云开发者生态关键一环。“Work Like Alibaba”将成为中国及至全世界开发者最潮流的口号。

本职位主要职责是负责代码平台基础设施的架构演进、Git 核心技术开发，代码领域技术趋势跟踪、下一代代码平台预言。我们是一群懂代码，爱 Git，有技术有梦想的工程师。让我们一起携手解决跨地域、分布式、海量代码托管等世界级业务和技术难题，为阿里巴巴集团内部、生态伙伴以及云上开发者服务。

我们的使命：帮助企业让更多的工作内容和工作行为 “有意义” 的数字化。
我们的愿景：服务一亿人的数字化办公。

岗位描述：
1、代码平台后端大规模服务器集群的分布式架构演进；
2、服务器计算、存储资源的再平衡、故障修复与隔离，服务器智能运维；
3、基于分布式存储的下一代代码平台，实现低延迟、高效率在线编码；
4、Git 核心代码开发，业界趋势跟踪，保持技术领先，优化用户体验等等。

岗位要求：
1、3 到 8 年的工作经验，精通 Go 语言、C 语言或 java 语言的一种。
2、熟悉分布式一致性协议，有分布式系统开发经验。
3、熟悉微服务架构，RPC 的基本原理、gRPC、pb 等原理和使用，加分。
4、热爱技术，有较强的学习能力、良好的团队合作能力、抗压能力。

KentY

2019-12-20 18:19:12 +08:00

@amiwrong123
关于+1. loadfactor 缺省有个值, 75%, 尽管 resize 都是按照 2 的幂, 这样计算, 这个商不会出现小数(默认起始 capacity 也是 16). 但是不要忘记, capacity and loadfactory 是可以用户给定的. 可是, resize 的算法是固定的, 所以会出现小数的情况. 如果要出现不整除的情况很容易, 你设计一个 2 的幂无法整除的除数的倒数就好了.

resize 需要 re-hash, 这是 hash-table data structure 里最 expensive 的操作. 但是又必须做. 所以才有了 loadfactor, threshold 那些零碎. 这些都没有必定有效的策略, 都是按照概率来的. 后面的子集情况是特殊情况, 但是有一部分 key 重叠是常见情况.

amiwrong123

2019-12-20 21:34:20 +08:00

@KentY
对哈，因为容量肯定是 2 的幂，且默认的 loadfactor 是 0.75 ，所以我那种情况会分配过大。但如果 loadfactor 是用户给的一个奇怪的小数（这得啥用户啊。。），使得容量*loadfactor 不等于整数的话，算出来的阈值也是要向下取整的。所以，反过来想，用 size / loadfactor 算出的容量，肯定也要向上取整了。

因为操作昂贵，所以只要在必须 resize 的情况下才 resize，其余需要 resize 的情况，就交给 putVal 再去触发 resize。

KentY

2019-12-20 21:56:26 +08:00

"因为操作昂贵，所以只要在必须 resize 的情况下才 resize，其余需要 resize 的情况，就交给 putVal 再去触发 resize。"
@amiwrong123
我觉得你说的这条不是太合适, 我们可以讨论.
resize 昂贵, 但如果 table 里面东西越少, 这个"昂贵"的操作越"廉价". 所以我们就要找一个情况, 看 table 需要这个昂贵操作的概率有多大, 如果很大, 我们就尽量早做, 如果没那么肯定, 那就等到该做的时候做. 这是我对那个 if 语句的想法.

再回来说你的例子, 好像你觉得本来 12, 变成了 24, 好像空间占用一下多了一倍. 其实你仔细想想, 你这个是特例, 不能推广到所有该 x 空间的都变成 2x, 因为你的那个 size 增长是线性的, 但是 resize 的结果是指数的, 你说的这个情况只有在那个 t 是整数, 而且刚好等于 threshold 的情况才会发生. 你再想想, 当不是初始化缺省值的 case 下, 这种情况发生会很小, 而且这种害处只体现在 table 本身很大的时候. 可是, 当 size 越大,这种情况出现的概率就越低.