一. 前言
最近,我在协助同事优化一段批处理任务时,偶然发现了一个有趣的问题。我们使用了一个庞大的 HashMap
,每次获取数据之前都会调用 containsKey()
方法。这就像在寻找一把钥匙之前,先要确认这个钥匙是否存在一样。结果,意外地发现这一步骤造成了一定的速度瓶颈。今天,我想借这个机会和大家分享一下这个小小的发现。
二. HashMap.containsKey()
与 HashMap.get()
方法分析
我们先来看一下 HashMap
的 get()
方法。这段代码的功能是返回与指定键关联的值,或者在没有找到该键的情况下返回 null
。下面逐行分析代码,并加上前后关联的注释。
java">/*** 返回与指定键关联的值,* 如果此映射不包含该键的映射,则返回 {@code null}。*/
public V get(Object key) {Node<K,V> e; // 声明一个节点变量 e// 调用 getNode 方法,根据键的哈希值和键本身获取节点return (e = getNode(hash(key), key)) == null ? null : e.value; // 如果节点为 null,返回 null;否则返回节点的值
}
关键方法分析
获取节点:
java">final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {// 检查第一个节点的哈希值和键是否匹配if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))return first; // 如果匹配,返回第一个节点// 后续节点检查if ((e = first.next) != null) {do {if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))return e; // 找到匹配的返回节点} while ((e = e.next) != null); // 遍历链表}}return null; // 没有找到,返回 null
}
主要情况总结
- 直接返回:如果哈希表中存在该键且该键是第一个节点,则直接返回对应的值,不涉及循环。
- 链表查找:如果第一个节点不匹配,且存在后续节点,则通过
while
循环遍历链表查找,性能可能受到影响,特别是在链表较长的情况下。 - 树结构查找:如果哈希表中的冲突节点组织成树,则会调用
getTreeNode()
方法,通过树的结构查找,通常比链表查找更高效,但仍可能涉及多次比较。
循环操作发生的情况
- 链表查找:多个键以链表形式存储时。
- 树查找:链表长度超过阈值并转换为树时。
总结来说,循环操作主要在键冲突的情况下发生,影响获取操作的性能。
同样,containsKey()
也是调用 getNode
方法,当数据量过大时会导致量变引起质变,毕竟相当于在最外层调用了两次方法:
java">public boolean containsKey(Object key) {return getNode(hash(key), key) != null;
}
优化建议
如果我们数据量较大,并且只是为了判断是否为空,建议直接使用 get
方法获取对象,然后判断对象是否为 null
。下面是我写的一个简单测试,虽然未考虑所有边界情况,但可以很好地展示性能差异。
java">import java.util.*;public class TestMain {public static void main(String[] args) {Map<String, String> tmp = new HashMap<>();String prefix = "test_";// 数据准备for (int i = 0; i < 2000000; i++) {tmp.put(prefix + i, UUID.randomUUID().toString());}System.out.println("数据准备完成");List<Long> times = new ArrayList<>();List<Double> efficiencyImprovements = new ArrayList<>();for (int i = 0; i < 10; i++) {System.out.println("================================================");Set<Integer> uniqueNumbers = new HashSet<>();Random random = new Random();// 生成随机数while (uniqueNumbers.size() < 100000) {int num = random.nextInt(2000000);uniqueNumbers.add(num);}System.out.println("数据key值准备完成.... 集合大小" + uniqueNumbers.size());// 直接 get 方法速度测试System.out.println("开始验证直接 get....");long startTimeDirectGet = System.nanoTime();for (Integer uniqueNumber : uniqueNumbers) {String s = tmp.get(prefix + uniqueNumber);}long endTimeDirectGet = System.nanoTime();long s1 = endTimeDirectGet - startTimeDirectGet;System.out.println("直接 get....完成,耗时: " + s1 + " 纳秒");// 测试 containsKey 和 get 方法的速度System.out.println("开始验证 containsKey 和 get....");long startTimeContainsKey = System.nanoTime();for (Integer uniqueNumber : uniqueNumbers) {if (tmp.containsKey(prefix + uniqueNumber)) {String s = tmp.get(prefix + uniqueNumber);}}long endTimeContainsKey = System.nanoTime();long s2 = endTimeContainsKey - startTimeContainsKey;System.out.println("containsKey 和 get....完成,耗时: " + s2 + " 纳秒");times.add((s2 - s1));double efficiencyImprovement = (double)(s2 - s1) / s2;efficiencyImprovements.add(efficiencyImprovement);System.gc();System.out.println("================================================");}// 输出结果for (int i = 0; i < times.size(); i++) {double seconds = times.get(i) / 1_000_000_000.0; // 转换为秒System.out.println("第" + i + "次直接 get 耗时快: " + seconds + "秒");Double v = efficiencyImprovements.get(i);System.out.println("第" + i + "次效率提升:" + v);}}
}
第0次直接get耗时快: 0.007546874秒
第0次效率提升:0.14021435448493608
第1次直接get耗时快: 0.006042667秒
第1次效率提升:0.1539109807056363
第2次直接get耗时快: 0.015829292秒
第2次效率提升:0.3414840057205336
第3次直接get耗时快: 0.008600376秒
第3次效率提升:0.20716517356888364
第4次直接get耗时快: 0.005992541秒
第4次效率提升:0.15560410618574866
第5次直接get耗时快: 0.006126833秒
第5次效率提升:0.1635963413125505
第6次直接get耗时快: 0.009747542秒
第6次效率提升:0.2424615913018364
第7次直接get耗时快: 0.005269542秒
第7次效率提升:0.14335964088961436
第8次直接get耗时快: 0.006652375秒
第8次效率提升:0.1828536284517621
第9次直接get耗时快: 0.008928542秒
第9次效率提升:0.23012867505014814