这是一个创建于 1985 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一道面试题：
HashMap 是如何扩容的，如何避免扩容？
扩容的话，是扩容到大于初始容量的第一个 2 次方
但是这个扩容操作可以避免吗？莫非是初始化的时候就定义足够大容量的？
google 搜了一圈没有答案，求大神分析
第 1 条附言 · 2019-07-24 17:37:28 +08:00
搜到这篇文章，感觉写的还挺好的
扩容无法完全避免，只能在内存和性能之间做均衡
扩容无法完全避免，只能在内存和性能之间做均衡
第 2 条附言 · 2019-07-24 17:42:12 +08:00
没办法上链接，文章名字叫：
关于 HashMap 容量的初始化，还有这么多学问。
有需要的同学可以搜一下
关于 HashMap 容量的初始化，还有这么多学问。
有需要的同学可以搜一下
 |
1
quqiuzhu 2019-07-24 06:28:51 +08:00 via Android
如果不扩容，多余的键值对如何处理？ 如果丢弃调最老的，有 LRU。
|
 |
2
snappyone 2019-07-24 06:35:15 +08:00 via Android
问题的点是不是如何减少扩容时的一次性开销？将扩容开销分摊到后续的多次 put 上来避免大复制带来的停顿
|
 |
3
lqw3030 2019-07-24 07:17:21 +08:00 via iPhone
不扩容最差的情况就是每次 hash 都碰撞，然后生成一个巨大的红黑树
|
 |
4
pierswu 2019-07-24 08:18:08 +08:00
LinkedHashMap 有一个 removeEldestEntry 方法，可以控制在什么情况下删除最旧的记录。
所以只要在 map 中的记录数接近触发扩容的时候，删除最旧的记录，就永远不会扩容了。 手动狗头 |
 |
5
Takamine 2019-07-24 08:18:23 +08:00 via Android
尽量避免他自我复制比较好。_(:з」∠)_
|
 |
6
skypyb 2019-07-24 08:19:13 +08:00 via Android  1
避免扩容那不是有病么...
|
 |
7
Kaiv2 2019-07-24 08:20:44 +08:00 via Android
如果是确定存放的数据，可指定大小
|
 |
8
nekolr 2019-07-24 08:23:19 +08:00 via Android
看源码，几个构造函数看一遍，可以给初始容量
|
|
9
nekolr 2019-07-24 08:24:43 +08:00 via Android
找找 guava 的代码看，它的初始化是怎么确定值的
|
 |
10
hand515 2019-07-24 08:42:00 +08:00
估计是要考 factor 的使用吧
|
 |
11
xuanbg 2019-07-24 09:03:13 +08:00
自己知道有多少数据，初始值就设多少，这样就能不扩容了。不知道具体的数量，毛估估一下也能避免多次扩容。估不准的话，不扩容等着丢数据么？
话说 hashMap 的扩容机制太不友好，应该引入链表来避免复制呀。。。 |
 |
12
asd123456cxz 2019-07-24 09:08:44 +08:00
初始值定义到业务预估的足够大值，这个答案没啥问题吧。。应该去分析为什么需要扩容，如果数据量增长缓慢响应要求不高那么初始值小利于节约内存，频繁扩容也可以接受；反之就大大大。就像 3L 说的，死板避免扩容才是灾难
|
 |
13
Aresxue 2019-07-24 09:12:54 +08:00
@xuanbg 主干改成链表的话性能就降低太多了，目前这种做法就是要求使用者要对数据量做一个估计。业务有需要的话自己重写一个 hashMap 就好了，像 fastjson 里面就自定义了一个 IdentityHashMap。
|
|
14
xuanbg 2019-07-24 09:14:35 +08:00
@xuanbg 如果把整个 hashMap 分拆成固定大小的一段一段，然后存在链表里面，就能避免复制了。然后把链表的每个节点地址都存在一个数组里面，解决下标段和地址的快速映射的问题就好。
|
 |
15
wwqgtxx 2019-07-24 09:19:13 +08:00 via iPhone
@xuanbg 很多情况下，复制产生的代价会小于链表带来的读取损耗，你说的这种结构类似于 c++ stl 的 std::deque，但是在读取较多的负载下性能比 std::vector 差了不少
|
 |
17
cwjokaka 2019-07-24 09:32:38 +08:00
避免扩容只能预估数据量吧。。。不然就继承 hashmap,重写 put 方法,从而实现不扩容，由于继承，这个类依然是 hashmap，解题完毕
|
 |
18
lastpass 2019-07-24 09:45:37 +08:00 via Android
@xuanbg #11 hashmap 的底层实现就是靠的数组+链表+红黑树(jdk8)实现的呀。
|
 |
19
jimrok 2019-07-24 09:49:47 +08:00
减少扩容就要减少 hash 碰撞，避免拉链。那要看你能不能预估容量，并且使用特殊的 hash 算法来改进 hash 在空间上的分布。
|
|
20
lastpass 2019-07-24 09:54:41 +08:00 via Android
扩容首先是无法避免的。只能说尽量避免(除非你能忍受碰撞带来的性能急剧下降。这道面试题应该是问你是否知道在 new hashmap 的时候最好能够根据数据的特性和大小，自己定义 initialCapacity 和 loadFactor。以减少 resiez 带来的性能消耗(其实 jdk8 的更新中有提到对 resize 的优化，这方面的问题其实不大，jdk7 时代还蛮严重的。)
|
|
22
xuanbg 2019-07-24 10:07:50 +08:00
@wwqgtxx 性能基本不会影响太多，按下标读的话，只不过是直接寻址变成可计算的两级寻址，寻址的时间复杂度还是 O(1)。通过 Key 读的话，一样是通过哈希寻址，并没有什么区别。
|
 |
23
joooooker21 2019-07-24 10:17:36 +08:00
习惯的做法是提前确定并设置容量
|
 |
24
zhybb2010 2019-07-24 10:26:05 +08:00
指定大小。
|
 |
26
Alex5467 2019-07-24 11:07:13 +08:00
我想你大概是理解错了，避免扩容是避免不必要的扩容，比如你要存 64 个数据，初始化 map 的时候他只有 16 的初始容量，16*0.75 相当于只有 12 的容量，这个时候超过了初始容量，map 底层就得扩容了，所以在你知道要保存的数据大概数量的话最好的是给他设置初始容量值，这样的话超过 16 后他就不会自动扩容了，也就是避免扩容，面试官问的应该没问题
|
|
27
Alex5467 2019-07-24 11:11:02 +08:00
扩容是不可避免的，最开始的桶能装 1 升水，现在你差不多知道有十升水，你就会设置大一点的桶来装水，如果不设置的话会一直扩容，这样的性能是很差的
|
 |
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 |
 |
30
lihongjie0209 2019-07-24 12:41:00 +08:00
initCapacity = Integer.Max_Value
|
 |
31
Raymon111111 2019-07-24 14:45:33 +08:00
预设一个大小
但是不要过度优化 几百个元素这种就没有必要考虑这种问题 |
 |
32
aqqwiyth 2019-07-24 17:06:47 +08:00
还要追究这点性能么.....
|
Select Language