list.contains和map.containsKey哪个性能更好,效率更高?

Java基础 潘老师 7个月前 (03-11) 348 ℃ (0) 扫码查看

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


版权声明:本站所有文章,如无特殊说明,均为本站原创。转载请务必注明文章来源,谢谢支持。
本文链接:https://www.panziye.com/java/4655.html
喜欢 (0)
请潘老师喝杯Coffee吧!】
分享 (0)
用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi,您需要填写昵称和邮箱!

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】