为什么 hashmap 里 putMapEntries 只判断传入 map 的 size 是否大于当前 map 的阈值呢? - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX    Java

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

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

    源码为 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     Solana     2544 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 26ms UTC 02:29 PVG 10:29 LAX 19:29 JFK 22:29
    Do have faith in what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86