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

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

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

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

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

二、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比较适合。