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

文
章
目
录

• 一、说明下任务需求-可以忽略，直接看第二点
• 二、list.contains和map.containsKey哪个性能更好，效率更高
• 说说原因

最近遇到一个问题，由于需要遍历匹配的数据量比较大，纠结于使用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比较适合。