HashMap使用initialCapacity初始化值进行性能优化

2次阅读

共计 925 个字符,预计需要花费 3 分钟才能阅读完成。

我们一般在写代码时,使用 HashMap 数据结构存数据时,有时候不会做容量大小设置,这样可能会造成一些内存浪费,所以,在知道存储的键值对数量的情况下,做初始化比较好。

一、创建 HashMap

新建一个 hashMap 的时候,可以通过 initialCapacity 设置 hashMap 长度的初始化值。

Map<String, Object> resultMap = new HashMap<String, Object>(initialCapacity: 5);

hashMap 源码中 initialCapacity 的初始值为 16,负载因子为 0.75;

所以一个 hashMap 中默认存储长度为 16 * 0.75 = 12,也就是如果 hashMap.put 的键值对数量小于 12 的时候,hashMap 位置够用;但是当添加的键值对数超过 12 后,hashMap 需要扩容,一倍,也就是长度从 12 扩容到 24;

例如键值对一共 13 个,这样剩余 11 个位置性能都浪费了,那么如果已知需要添加的键值对数量,就可以通过设置 initialMap 的值,来避免 hashMap 扩容,减少性能消耗。

我们需要往 hashMap 中添加 6 个键值对,6 / 0.75 = 8;那就可以把 initialCapacity 设置为 9 比较合适,节省性能。

二、原理

公式是《阿里巴巴 Java 开发手册》中的一个建议,在 Guava 中也是提供了相同的算法,更甚之,这个算法实际上是 JDK8 中 putAll() 方法的实现。这是公式的得出是因为, 当 HashMap 内部维护的哈希表的容量达到 75% 时(默认情况下),就会触发 rehash(重建 hash 表)操作。而 rehash 的过程是比较耗费时间的。所以初始化容量要设置成 expectedSize/0.75 + 1 的话,可以有效地减少冲突,也可以减小误差 ”

我的理解是: 当数组长度是可容纳长度的 75% 时,就会重新建立数组, 产生额外开销,所以这个预期的数组长度要小于可容纳的长度的 75%,也就是 (initialCapacity – 1) * 0.75 = 预期数组长度,即 initialCapacity * 0.75 > 预期数组长度

三、公式

最后,千言万语都汇成最后这一个容量公式:

initialCapacity = expectedSize/0.75 + 1
正文完
 0