章
目
录
最近遇到一个问题，由于需要遍历匹配的数据量比较大，纠结于使用List集合contains还是Map集合containsKey方法去判断是否存在某个字符串，这就涉及到list.contains和map.containsKey哪个性能更好，效率更高的问题，选择对了，对整个系统的性能可能都会产生非常大的影响。
一、说明下任务需求-可以忽略，直接看第二点
集合A和集合B，A和B的数据量都在十万级别，A中每个元素对象的某个属性值和B中的某个元素对象的属性值存在对应关系，现在就是要将这两个集合进行匹配，然后整合成一个新的对象集合。
这种需求，最常才想到的方法就是两个List集合，两个for循环嵌套，循环体内判断A和B的每个元素的该属性匹配，知道匹配到为止，最极端的情况，会导致10W*10W次的循环，这性能估计高不到哪去。
于是考虑将相同属性作为map的key去判断会不会更快点？或者取出来全存到List
二、list.contains和map.containsKey哪个性能更好，效率更高
1、千万级及以上：map.containsKey > map.containsValue > list.cantains
2、百万级及以下：map.containsKey > list.cantains > map.containsValue
总之经过测试，map.containsKey效率远远高于list.cantains的效率，性能差距很大。
说说原因
这就取决于list集合和map集合的底层结构，和这两个方法的实现源码了，我们一起看下具体原因分析：
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<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 && // 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<K,V>)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比较适合。
