Java 中， HashMap 扩容可以避免吗？

[lixyz]

有一道面试题：

HashMap 是如何扩容的，如何避免扩容？

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

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

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

搜到这篇文章，感觉写的还挺好的
扩容无法完全避免，只能在内存和性能之间做均衡

没办法上链接，文章名字叫：
关于 HashMap 容量的初始化，还有这么多学问。

有需要的同学可以搜一下

[quqiuzhu]

如果不扩容，多余的键值对如何处理？ 如果丢弃调最老的，有 LRU。

[snappyone]

问题的点是不是如何减少扩容时的一次性开销？将扩容开销分摊到后续的多次 put 上来避免大复制带来的停顿

[lqw3030]

不扩容最差的情况就是每次 hash 都碰撞，然后生成一个巨大的红黑树

[pierswu]

LinkedHashMap 有一个 removeEldestEntry 方法，可以控制在什么情况下删除最旧的记录。
所以只要在 map 中的记录数接近触发扩容的时候，删除最旧的记录，就永远不会扩容了。
手动狗头

[Takamine]

尽量避免他自我复制比较好。_(:з」∠)_

[skypyb]

避免扩容那不是有病么...

[Kaiv2]

如果是确定存放的数据，可指定大小

[nekolr]

看源码，几个构造函数看一遍，可以给初始容量

[nekolr]

找找 guava 的代码看，它的初始化是怎么确定值的

[hand515]

估计是要考 factor 的使用吧

[xuanbg]

自己知道有多少数据，初始值就设多少，这样就能不扩容了。不知道具体的数量，毛估估一下也能避免多次扩容。估不准的话，不扩容等着丢数据么？

话说 hashMap 的扩容机制太不友好，应该引入链表来避免复制呀。。。

[asd123456cxz]

初始值定义到业务预估的足够大值，这个答案没啥问题吧。。应该去分析为什么需要扩容，如果数据量增长缓慢响应要求不高那么初始值小利于节约内存，频繁扩容也可以接受；反之就大大大。就像 3L 说的，死板避免扩容才是灾难

[Aresxue]

@xuanbg 主干改成链表的话性能就降低太多了，目前这种做法就是要求使用者要对数据量做一个估计。业务有需要的话自己重写一个 hashMap 就好了，像 fastjson 里面就自定义了一个 IdentityHashMap。

[xuanbg]

@xuanbg 如果把整个 hashMap 分拆成固定大小的一段一段，然后存在链表里面，就能避免复制了。然后把链表的每个节点地址都存在一个数组里面，解决下标段和地址的快速映射的问题就好。

[wwqgtxx]

@xuanbg 很多情况下，复制产生的代价会小于链表带来的读取损耗，你说的这种结构类似于 c++ stl 的 std::deque，但是在读取较多的负载下性能比 std::vector 差了不少

[LuGew]

@xuanbg 存储链表地址的数组不也得扩容吗？

[cwjokaka]

避免扩容只能预估数据量吧。。。不然就继承 hashmap,重写 put 方法,从而实现不扩容，由于继承，这个类依然是 hashmap，解题完毕

[lastpass]

@xuanbg #11 hashmap 的底层实现就是靠的数组+链表+红黑树(jdk8)实现的呀。

[jimrok]

减少扩容就要减少 hash 碰撞，避免拉链。那要看你能不能预估容量，并且使用特殊的 hash 算法来改进 hash 在空间上的分布。

[lastpass]

扩容首先是无法避免的。只能说尽量避免(除非你能忍受碰撞带来的性能急剧下降。这道面试题应该是问你是否知道在 new hashmap 的时候最好能够根据数据的特性和大小，自己定义 initialCapacity 和 loadFactor。以减少 resiez 带来的性能消耗(其实 jdk8 的更新中有提到对 resize 的优化，这方面的问题其实不大，jdk7 时代还蛮严重的。)

[xuanbg]

@LuGew 这个数组就小多了呀，不但元素少，数据量也小，复制的性能问题可以忽略

[xuanbg]

@wwqgtxx 性能基本不会影响太多，按下标读的话，只不过是直接寻址变成可计算的两级寻址，寻址的时间复杂度还是 O(1)。通过 Key 读的话，一样是通过哈希寻址，并没有什么区别。

[joooooker21]

习惯的做法是提前确定并设置容量

[zhybb2010]

指定大小。

[ykrank]

@xuanbg Show me code. 这种研究透了的基础数据，要性能优化，得给出你的代码了

[Alex5467]

我想你大概是理解错了，避免扩容是避免不必要的扩容，比如你要存 64 个数据，初始化 map 的时候他只有 16 的初始容量，16*0.75 相当于只有 12 的容量，这个时候超过了初始容量，map 底层就得扩容了，所以在你知道要保存的数据大概数量的话最好的是给他设置初始容量值，这样的话超过 16 后他就不会自动扩容了，也就是避免扩容，面试官问的应该没问题

[Alex5467]

扩容是不可避免的，最开始的桶能装 1 升水，现在你差不多知道有十升水，你就会设置大一点的桶来装水，如果不设置的话会一直扩容，这样的性能是很差的

[hoorace]

这个题目重点考察的是 hashmap 的内存管理，如果是容量不够的情况下是如何申请内存的。
http://coding-geek.com/how-does-a-hashmap-work-in-java/
Google 搜索关键词：hashmap memory allocation

[oaix]

@xuanbg #22 resize 不仅仅是加一块地址。所有的已有元素都需要重新哈希一遍。

[lihongjie0209]

initCapacity = Integer.Max_Value

[Raymon111111]

预设一个大小

但是不要过度优化

几百个元素这种就没有必要考虑这种问题

[aqqwiyth]

还要追究这点性能么.....

[wysnylc]

@skypyb #6 +1

[Alex5467]

@wysnylc 扩容是可以避免的