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

[lixyz]

有一道面试题：

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

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

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

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

[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 时代还蛮严重的。)