HashMap 使用 HashMap(int initialCapacity)对集合进行初始化.
在默认的情况下, HashMap 的容量是 16. 但是如果用户通过构造函数指定了一个数字作为容量, 那么 Hash 会选择大于该数字的第一个 2 的幂作为容量. 比如如果指定了 3, 则容量是 4; 如果指定了 7, 则容量是 8; 如果指定了 9, 则容量是 16.
为什么要设置 HashMap 的初始化容量
在《阿里巴巴 Java 开发手册》中, 有一条开发建议是建议我们设置 HashMap 的初始化容量.
下面我们通过具体的代码来了解下为什么会这么建议.
我们先来写一段代码在 JDK1.7 的环境下运行, 来分别测试下, 在不指定初始化容量和指定初始化容量的情况下性能情况的不同.
- public static void main(String[] args) {
- int aHundredMillion = 10000000;
- // 未初始化容量
- Map<Integer, Integer> map = new HashMap<>();
- long s1 = System.currentTimeMillis();
- for (int i = 0; i <aHundredMillion; i++) {
- map.put(i, i);
- }
- long s2 = System.currentTimeMillis();
- System.out.println("未初始化容量, 耗时:" + (s2 - s1)); // 14322
- // 初始化容量为 50000000
- Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2);
- long s3 = System.currentTimeMillis();
- for (int i = 0; i <aHundredMillion; i++) {
- map1.put(i, i);
- }
- long s4 = System.currentTimeMillis();
- System.out.println("初始化容量 5000000, 耗时:" + (s4 - s3)); // 11819
- // 初始化容量为 100000000
- Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion);
- long s5 = System.currentTimeMillis();
- for (int i = 0; i <aHundredMillion; i++) {
- map2.put(i, i);
- }
- long s6 = System.currentTimeMillis();
- System.out.println("初始化容量为 10000000, 耗时:" + (s6 - s5)); // 7978
- }
从以上的代码不难理解, 我们创建了 3 个 HashMap, 分别使用默认的容量 (16), 使用元素个数的一半(5 千万) 作为初始容量和使用元素个数 (一亿) 作为初始容量进行初始化, 然后分别向其中 put 一亿个 KV.
从上面的打印结果中可以得到一个初步的结论: 在已知 HashMap 中将要存放的 KV 个数的时候, 设置一个合理的初始化容量可以有效地提高性能. 下面我们来简单分析一下原因.
我们知道, HashMap 是有扩容机制的. 所谓的扩容机制, 指的是当达到扩容条件的时候, HashMap 就会自动进行扩容. 而 HashMap 的扩容条件就是当 HashMap 中的元素个数 (Size) 超过临界值 (Threshold) 的情况下就会自动扩容.
threshold = loadFactor * capacity
在元素个数超过临界值的情况下, 随着元素的不断增加, HashMap 就会发生扩容, 而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表, 这一操作需要消耗大量资源, 是非常影响性能的. 因此, 如果我们没有设置初始的容量大小, HashMap 就可能会不断发生扩容, 也就使得程序的性能降低了.
另外, 在上面的代码中我们会发现, 同样是设置了初始化容量, 设置的数值不同也会影响性能, 那么当我们已知 HashMap 中即将存放的 KV 个数的时候, 容量的设置就成了一个问题.
HashMap 中容量的初始化
开头提到, 在默认的情况下, 当我们设置 HashMap 的初始化容量时, 实际上 HashMap 会采用第一个大于该数值的 2 的幂作为初始化容量.
- Map<String, String> map = new HashMap<>(1);
- map.put("huangq", "yanggb");
- Class<?> mapType = map.getClass();
- Method capacity = mapType.getDeclaredMethod("capacity");
- capacity.setAccessible(true);
- System.out.println("capacity :" + capacity.invoke(map)); // 2
当初始化的容量设置成 1 的时候, 通过反射取出来的 capacity 却是 2. 在 JDK1.8 中, 如果我们传入的初始化容量为 1, 实际上设置的结果也是 1. 上面的代码打印的结果为 2 的原因, 是代码中给 map 塞入值的操作导致了扩容, 容量从 1 扩容到了 2. 事实上, 在 JDK1.7 和 JDK1.8 中, HashMap 初始化容量 (capacity) 的时机不同. 在 JDK1.8 中, 调用 HashMap 的构造函数定义 HashMap 的时候, 就会进行容量的设定. 而在 JDK1.7 中, 要等到第一次 put 操作时才进行这一操作.
因此, 当我们通过 HashMap(int initialCapacity)设置初始容量的时候, HashMap 并不一定会直接采用我们传入的数值, 而是经过计算, 得到一个新值, 目的是提高 hash 的效率. 比如 1->1,3->4,7->8 和 9->16.
HashMap 中初始容量的合理值
通过上面的分析我们可以知道, 当我们使用 HashMap(int initialCapacity)来初始化容量的时候, JDK 会默认帮我们计算一个相对合理的值当做初始容量. 那么, 是不是我们只需要把已知的 HashMap 中即将存放的元素个数直接传给 initialCapacity 就可以了呢?
initialCapacity = (需要存储的元素个数 / 负载因子) + 1
这里的负载因子就是 loaderFactor, 默认值为 0.75.
initialCapacity = expectedSize / 0.75F + 1.0F
上面这个公式是《阿里巴巴 Java 开发手册》中的一个建议, 在 Guava 中也是提供了相同的算法, 更甚之, 这个算法实际上是 JDK8 中 putAll()方法的实现. 这是公式的得出是因为, 当 HashMap 内部维护的哈希表的容量达到 75% 时 (默认情况下), 就会触发 rehash(重建 hash 表) 操作. 而 rehash 的过程是比较耗费时间的. 所以初始化容量要设置成 expectedSize/0.75 + 1 的话, 可以有效地减少冲突, 也可以减小误差.
总结
当我们想要在代码中创建一个 HashMap 的时候, 如果我们已知这个 Map 中即将存放的元素个数, 给 HashMap 设置初始容量可以在一定程度上提升效率.
但是, JDK 并不会直接拿用户传进来的数字当做默认容量, 而是会进行一番运算, 最终得到一个 2 的幂. 而为了最大程度地避免扩容带来的性能消耗, 通常是建议可以把默认容量的数字设置成 expectedSize / 0.75F + 1.0F.
在日常开发中, 可以使用 Guava 提供的一个方法来创建一个 HashMap, 计算的过程 Guava 会帮我们完成.
Map<String, String> map = Maps.newHashMapWithExpectedSize(10);
最后要说的一点是, 这种算法实际上是一种使用内存换取性能的做法, 在真正的应用场景中要考虑到内存的影响.
"当你认真喜欢一个人的时候, 你的全世界都是她."
来源: https://www.cnblogs.com/yanggb/p/11613070.html