ArrayList的contains()方法的性能问题及优化方法

背景

今天定位一个接口耗时问题，通过日志定位到在数据库查询完毕后，中间一段逻辑耗时很长有十几秒的样子，发现是循环中使用ArraysList中的contains方法，当循环数量级变得很大时，执行时间变得不可控。

代码示例

// 有5万个门店
        List<Store> storeList = storeMapper.selectAll();

        // 有十万个用户
        List<User> userList = userMapper.selectAll();

        // 最坏情况循环5亿次
        for (user : userList){
            if (storeList.contains(user.getStoreCode())){
                doSth();
            }
        }

1. 原理说明

1.1 ArrayList

ArrayList中contains()方法的实现过程：

contains()方法调用了indexOf()方法，indexOf()具体实现如下。从源码可以看出，该方法通过遍历数据和比较元素的方式来判断是否存在给定元素。当ArrayList中存放的元素非常多时，这种实现方式来判断效率将非常低，后面通过实例来验证。

 1.2 HashSet

既然ArrayList的contains()方法存在性能问题，那么就应该寻找改进的办法。这里推荐使用HashSet来代替ArrayList。
下面介绍HashSet的contains()方法的实现过程： 

HashSet将元素存放在HashMap中（HashMap的key）

contains()方法调用HashMap的containsKey()方法

containsKey()方法调用getEntry()方法。在该方法中，首先根据key计算hash值，然后从HashMap中取出该hash值对应的链表（链表的元素个数将很少），再通过变量该链表判断是否存在给定值。这种实现方式效率将比ArrayList的实现方法效率高非常多。

2. 实例验证

2.1 测试ArrayList

public static void main(String[] args) {
	ArrayList<String> arrayList = new ArrayList<>();
	// 存入100000个数据
	for (int i = 0; i < 100000; i++) {
		arrayList.add("test" + i);
	}
		
	// 验证300000个数据（其中200000不存在）		
	long beginTime = System.currentTimeMillis();		for (int i = 0; i < 300000; i++) {
		arrayList.contains("test" + i);
	}
	long endTime = System.currentTimeMillis();
		
	System.out.println("cost time: " + (endTime - beginTime) + "ms");
}
打印结果：
cost time: 182210ms

 2.2 测试HashSet

public static void main(String[] args) {
		
	Set<String> hashSet = new HashSet<>();
	// 存入100000个数据
	for (int i = 0; i < 100000; i++) {
		hashSet.add("test" + i);
	}
		
	// 验证300000个数据（其中200000不存在）
	long beginTime = System.currentTimeMillis();
	for (int i = 0; i < 300000; i++) {
		hashSet.contains("test" + i);
	}
	long endTime = System.currentTimeMillis();
	
	System.out.println("cost time: " + (endTime - beginTime) + "ms");
}
打印结果：
cost time: 49ms

 3. 总结

通过第二节的实例可以看出，使用ArrayList的contains()耗时是使用HashSet的contains()方法的30多倍。具体原因可以参考第一节中的原理分析。

本篇文章如有帮助到您，请给「翎野君」点个赞，感谢您的支持。

作者：翎野君