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

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

  •  
  •   lixyz · 112 天前 · 3173 次点击
    这是一个创建于 112 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一道面试题:

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

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

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

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

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

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

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

    但是不要过度优化

    几百个元素这种就没有必要考虑这种问题
        32
    aqqwiyth   112 天前
    还要追究这点性能么.....
        33
    wysnylc   112 天前
    @skypyb #6 +1
        34
    Alex5467   112 天前
    @wysnylc 扩容是可以避免的
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   949 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 23ms · UTC 22:04 · PVG 06:04 · LAX 14:04 · JFK 17:04
    ♥ Do have faith in what you're doing.