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

Java 中, HashMap 扩容可以避免吗?

  •  
  •   lixyz · 2019-07-24 06:19:29 +08:00 · 6525 次点击
    这是一个创建于 1710 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一道面试题:

    HashMap 是如何扩容的,如何避免扩容?
    

    扩容的话,是扩容到大于初始容量的第一个 2 次方

    但是这个扩容操作可以避免吗?莫非是初始化的时候就定义足够大容量的?

    google 搜了一圈没有答案,求大神分析

    第 1 条附言  ·  2019-07-24 17:37:28 +08:00
    搜到这篇文章,感觉写的还挺好的
    扩容无法完全避免,只能在内存和性能之间做均衡
    第 2 条附言  ·  2019-07-24 17:42:12 +08:00
    没办法上链接,文章名字叫:
    关于 HashMap 容量的初始化,还有这么多学问。

    有需要的同学可以搜一下
    34 条回复    2019-07-24 17:30:31 +08:00
    quqiuzhu
        1
    quqiuzhu  
       2019-07-24 06:28:51 +08:00 via Android
    如果不扩容,多余的键值对如何处理? 如果丢弃调最老的,有 LRU。
    snappyone
        2
    snappyone  
       2019-07-24 06:35:15 +08:00 via Android
    问题的点是不是如何减少扩容时的一次性开销?将扩容开销分摊到后续的多次 put 上来避免大复制带来的停顿
    lqw3030
        3
    lqw3030  
       2019-07-24 07:17:21 +08:00 via iPhone
    不扩容最差的情况就是每次 hash 都碰撞,然后生成一个巨大的红黑树
    pierswu
        4
    pierswu  
       2019-07-24 08:18:08 +08:00
    LinkedHashMap 有一个 removeEldestEntry 方法,可以控制在什么情况下删除最旧的记录。
    所以只要在 map 中的记录数接近触发扩容的时候,删除最旧的记录,就永远不会扩容了。
    手动狗头
    Takamine
        5
    Takamine  
       2019-07-24 08:18:23 +08:00 via Android
    尽量避免他自我复制比较好。_(:з」∠)_
    skypyb
        6
    skypyb  
       2019-07-24 08:19:13 +08:00 via Android   ❤️ 1
    避免扩容那不是有病么...
    Kaiv2
        7
    Kaiv2  
       2019-07-24 08:20:44 +08:00 via Android
    如果是确定存放的数据,可指定大小
    nekolr
        8
    nekolr  
       2019-07-24 08:23:19 +08:00 via Android
    看源码,几个构造函数看一遍,可以给初始容量
    nekolr
        9
    nekolr  
       2019-07-24 08:24:43 +08:00 via Android
    找找 guava 的代码看,它的初始化是怎么确定值的
    hand515
        10
    hand515  
       2019-07-24 08:42:00 +08:00
    估计是要考 factor 的使用吧
    xuanbg
        11
    xuanbg  
       2019-07-24 09:03:13 +08:00
    自己知道有多少数据,初始值就设多少,这样就能不扩容了。不知道具体的数量,毛估估一下也能避免多次扩容。估不准的话,不扩容等着丢数据么?

    话说 hashMap 的扩容机制太不友好,应该引入链表来避免复制呀。。。
    asd123456cxz
        12
    asd123456cxz  
       2019-07-24 09:08:44 +08:00
    初始值定义到业务预估的足够大值,这个答案没啥问题吧。。应该去分析为什么需要扩容,如果数据量增长缓慢响应要求不高那么初始值小利于节约内存,频繁扩容也可以接受;反之就大大大。就像 3L 说的,死板避免扩容才是灾难
    Aresxue
        13
    Aresxue  
       2019-07-24 09:12:54 +08:00
    @xuanbg 主干改成链表的话性能就降低太多了,目前这种做法就是要求使用者要对数据量做一个估计。业务有需要的话自己重写一个 hashMap 就好了,像 fastjson 里面就自定义了一个 IdentityHashMap。
    xuanbg
        14
    xuanbg  
       2019-07-24 09:14:35 +08:00
    @xuanbg 如果把整个 hashMap 分拆成固定大小的一段一段,然后存在链表里面,就能避免复制了。然后把链表的每个节点地址都存在一个数组里面,解决下标段和地址的快速映射的问题就好。
    wwqgtxx
        15
    wwqgtxx  
       2019-07-24 09:19:13 +08:00 via iPhone
    @xuanbg 很多情况下,复制产生的代价会小于链表带来的读取损耗,你说的这种结构类似于 c++ stl 的 std::deque,但是在读取较多的负载下性能比 std::vector 差了不少
    LuGew
        16
    LuGew  
       2019-07-24 09:24:38 +08:00
    @xuanbg 存储链表地址的数组不也得扩容吗?
    cwjokaka
        17
    cwjokaka  
       2019-07-24 09:32:38 +08:00
    避免扩容只能预估数据量吧。。。不然就继承 hashmap,重写 put 方法,从而实现不扩容,由于继承,这个类依然是 hashmap,解题完毕
    lastpass
        18
    lastpass  
       2019-07-24 09:45:37 +08:00 via Android
    @xuanbg #11 hashmap 的底层实现就是靠的数组+链表+红黑树(jdk8)实现的呀。
    jimrok
        19
    jimrok  
       2019-07-24 09:49:47 +08:00
    减少扩容就要减少 hash 碰撞,避免拉链。那要看你能不能预估容量,并且使用特殊的 hash 算法来改进 hash 在空间上的分布。
    lastpass
        20
    lastpass  
       2019-07-24 09:54:41 +08:00 via Android
    扩容首先是无法避免的。只能说尽量避免(除非你能忍受碰撞带来的性能急剧下降。这道面试题应该是问你是否知道在 new hashmap 的时候最好能够根据数据的特性和大小,自己定义 initialCapacity 和 loadFactor。以减少 resiez 带来的性能消耗(其实 jdk8 的更新中有提到对 resize 的优化,这方面的问题其实不大,jdk7 时代还蛮严重的。)
    xuanbg
        21
    xuanbg  
       2019-07-24 09:58:29 +08:00
    @LuGew 这个数组就小多了呀,不但元素少,数据量也小,复制的性能问题可以忽略
    xuanbg
        22
    xuanbg  
       2019-07-24 10:07:50 +08:00
    @wwqgtxx 性能基本不会影响太多,按下标读的话,只不过是直接寻址变成可计算的两级寻址,寻址的时间复杂度还是 O(1)。通过 Key 读的话,一样是通过哈希寻址,并没有什么区别。
    joooooker21
        23
    joooooker21  
       2019-07-24 10:17:36 +08:00
    习惯的做法是提前确定并设置容量
    zhybb2010
        24
    zhybb2010  
       2019-07-24 10:26:05 +08:00
    指定大小。
    ykrank
        25
    ykrank  
       2019-07-24 11:03:04 +08:00
    @xuanbg Show me code. 这种研究透了的基础数据,要性能优化,得给出你的代码了
    Alex5467
        26
    Alex5467  
       2019-07-24 11:07:13 +08:00
    我想你大概是理解错了,避免扩容是避免不必要的扩容,比如你要存 64 个数据,初始化 map 的时候他只有 16 的初始容量,16*0.75 相当于只有 12 的容量,这个时候超过了初始容量,map 底层就得扩容了,所以在你知道要保存的数据大概数量的话最好的是给他设置初始容量值,这样的话超过 16 后他就不会自动扩容了,也就是避免扩容,面试官问的应该没问题
    Alex5467
        27
    Alex5467  
       2019-07-24 11:11:02 +08:00
    扩容是不可避免的,最开始的桶能装 1 升水,现在你差不多知道有十升水,你就会设置大一点的桶来装水,如果不设置的话会一直扩容,这样的性能是很差的
    hoorace
        28
    hoorace  
       2019-07-24 11:14:51 +08:00
    这个题目重点考察的是 hashmap 的内存管理,如果是容量不够的情况下是如何申请内存的。
    http://coding-geek.com/how-does-a-hashmap-work-in-java/
    Google 搜索关键词:hashmap memory allocation
    oaix
        29
    oaix  
       2019-07-24 12:04:34 +08:00
    @xuanbg #22 resize 不仅仅是加一块地址。所有的已有元素都需要重新哈希一遍。
    lihongjie0209
        30
    lihongjie0209  
       2019-07-24 12:41:00 +08:00
    initCapacity = Integer.Max_Value
    Raymon111111
        31
    Raymon111111  
       2019-07-24 14:45:33 +08:00
    预设一个大小

    但是不要过度优化

    几百个元素这种就没有必要考虑这种问题
    aqqwiyth
        32
    aqqwiyth  
       2019-07-24 17:06:47 +08:00
    还要追究这点性能么.....
    wysnylc
        33
    wysnylc  
       2019-07-24 17:21:48 +08:00
    @skypyb #6 +1
    Alex5467
        34
    Alex5467  
       2019-07-24 17:30:31 +08:00
    @wysnylc 扩容是可以避免的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2869 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 13:10 · PVG 21:10 · LAX 06:10 · JFK 09:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.