V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  Java

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

  •  
  •   amiwrong123 · 2019-12-18 23:37:55 +08:00 · 3597 次点击
    这是一个创建于 1801 天前的主题,其中的信息可能已经有所发展或是发生改变。

    源码为 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 的二倍了。 QHqurV.png 可见 oldMap 的容量是 16,阈值是 12.但 newMap 的容量是 32,阈值是 24. 因为 12/0.75=16,16 再加=17,17 再 tableSizeFor 得到 32.

    11 条回复    2019-12-20 23:12:26 +08:00
    KentY
        1
    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
        2
    amiwrong123  
    OP
       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
        3
    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
        4
    KentY  
       2019-12-19 15:56:00 +08:00 via iPhone
    @dyrone 还人工群发广告的公司.... 技术能好到哪去
    amiwrong123
        5
    amiwrong123  
    OP
       2019-12-19 16:53:34 +08:00
    每次发的源码讨论的帖子回复的人都特别少,这唯一的两人其中一个还是广告。。。是我提的问题太低端了吗。。。
    wc951
        6
    wc951  
       2019-12-20 17:45:44 +08:00 via Android
    @amiwrong123 反思一下自己是不是被卖片的盯上了🐶
    KentY
        7
    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
        8
    amiwrong123  
    OP
       2019-12-20 21:34:20 +08:00
    @KentY
    对哈,因为容量肯定是 2 的幂,且默认的 loadfactor 是 0.75 ,所以我那种情况会分配过大。但如果 loadfactor 是用户给的一个奇怪的小数(这得啥用户啊。。),使得容量*loadfactor 不等于整数的话,算出来的阈值也是要向下取整的。所以,反过来想,用 size / loadfactor 算出的容量,肯定也要向上取整了。

    因为操作昂贵,所以只要在必须 resize 的情况下才 resize,其余需要 resize 的情况,就交给 putVal 再去触发 resize。
    amiwrong123
        9
    amiwrong123  
    OP
       2019-12-20 21:35:04 +08:00
    @wc951
    我可太难了
    KentY
        10
    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 越大,这种情况出现的概率就越低.
    amiwrong123
        11
    amiwrong123  
    OP
       2019-12-20 23:12:26 +08:00
    @KentY
    嗯,你说的关于需要做的概率这一点我觉得有道理,反正就是,如果都提前知道需要了,那就尽早做呗。

    嗯,明白啦。我这是确实是个特例了,而且就算出现了这种特例(发生概率也很低),也只是多分配点大小嘛,也没啥关系。

    话说 jdk 作者还想得挺周全,回头我继续精读 HashMap 源码,要是有问题我还想请教下层主😂,哈哈哈
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2060 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 00:34 · PVG 08:34 · LAX 16:34 · JFK 19:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.