list.contains和map.containsKey哪个性能更好，效率更高？

IT 文章4年前 (2022)发布小编

最近遇到一个问题，由于需要遍历匹配的数据量比较大，纠结于使用List集合contains还是Map集合containsKey方法去判断是否存在某个字符串，这就涉及到list.contains和map.containsKey哪个性能更好，效率更高的问题，选择对了，对整个系统的性能可能都会产生非常大的影响。

一、说明下任务需求-可以忽略，直接看第二点

集合A和集合B，A和B的数据量都在十万级别，A中每个元素对象的某个属性值和B中的某个元素对象的属性值存在对应关系，现在就是要将这两个集合进行匹配，然后整合成一个新的对象集合。

这种需求，最常才想到的方法就是两个List集合，两个for循环嵌套，循环体内判断A和B的每个元素的该属性匹配，知道匹配到为止，最极端的情况，会导致10W*10W次的循环，这性能估计高不到哪去。

程序员导航

优网导航旗下整合全网优质开发资源，一站式IT编程学习与工具大全网站

立即访问

于是考虑将相同属性作为map的key去判断会不会更快点？或者取出来全存到List中使用contains去判断更快些？

二、list.contains和map.containsKey哪个性能更好，效率更高

[v_act]先说结论：[/v_act]1、千万级及以上：map.containsKey > map.containsValue > list.cantains
2、百万级及以下：map.containsKey > list.cantains > map.containsValue

总之经过测试，map.containsKey效率远远高于list.cantains的效率，性能差距很大。

说说原因

这就取决于list集合和map集合的底层结构，和这两个方法的实现源码了，我们一起看下具体原因分析：

AI 工具导航

优网导航旗下AI工具导航，精选全球千款优质 AI 工具集

立即访问

ArrayList使用的是数组来存储元素，而HashMap使用哈希表来存储元素。ArrayList的contains方法是通过调用自己的index of方法来判断的，源码如下：

public boolean contains(Object o) {
	return indexOf(o) >= 0;
}

public int indexOf(Object o) {
	if (o == null) {
		for (int i = 0; i < size; i++)
			if (elementData[i]==null)
				return i;
	} else {
		for (int i = 0; i < size; i++)
			if (o.equals(elementData[i]))
				return i;
	}
	return -1;
}

可以看到，在源码中，index方法把整个数组顺序遍历了一遍，这种查找方法无疑是效率最低的。

在HashMap里，key被存储到hash表中，查找时是在hash表上进行查找，关于hash表的查找方法这里就不赘述了，具体看下源码。

public boolean containsKey(Object key) {
	return getNode(hash(key), key) != null;
}

final Node getNode(int hash, Object key) {
	Node[] tab; Node first, e; int n; K k;
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(first = tab[(n - 1) & hash]) != null) {
		if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		if ((e = first.next) != null) {
			if (first instanceof TreeNode)
				return ((TreeNode)first).getTreeNode(hash, key);
			do {
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

总之，如果要用contains方法，用HashMap性能比ArrayList要高非常多，如果要遍历的话还是用ArrayList比较适合。