文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java集合中contains方法的效率对比分析

2024-04-02 19:55

关注

最近让部门技术大佬帮忙代码review的时候,他给我指出了一个小的技术细节,就是对于集合的contains方法尽量选用Set而不是List,平时没怎么注意,仔细看了下源码,大佬就是大佬,技术细节也把握的死死的。

Java集合List、Set中均有对集合中元素是否存在的判断方法contains(Object o);Map中有对key及value是否存在的判断方法containsKey(Object key)和containsValue(Object value)。

1.ArrayList

在ArrayList中contains方法通过遍历list中的元素,利用==或equals来判断是否存在目标元素,复杂度为O(N)


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;
}

2.HashSet

HashSet中元素以Key的形式存于HashMap中,判断元素是否存在即是判断对应Map中key是否存在。


HashSet:
    private transient HashMap<E,Object> map; //将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会被序列化。
    
    public HashSet() {
        map = new HashMap<>();
    }
public boolean contains(Object o) {
    return map.containsKey(o);
}

3.HashMap

HashMap中有两个contains方法,一个判断key是否存在,一个判断value是否存在。

HashMap的底层主要是基于数组和链表(散列表或者叫哈希表)来实现的,它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。

所以containsKey通过key的哈希值直接查找key是否存在,时间复杂度为O(1),响应的HashSet查找元素的时间复杂度也是O(1)。

对于containsValue方法判断map中是否存在value的判断,其方法为将map中的Node数组进行遍历,然后判断是否存在。


transient Node<K,V>[] table;
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;
}
public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
}

4.总结

集合各方法的时间复杂度 contains containskey containsValue
ArrayList O(N)
HashSet O(1)
HashKey O(1) O(N)

对于这种技术细节需要平时注意和积累,不断学习和记录,应用于实际开发中,不断提高运行效率。后续也会将这些技术细节记录下来,在日常开发中加以运用。

补充:ArrayList的contains方法的效率果然不高

看代码吧~

之前做的一个项目,数据库抽出了40多万条数据,然后从csv文件抽出了大概也是40多万条数据,进行对比分析 之前代码如下:


List<String> keys = new ArrayList<String>();
   int isize = msTaiyousr.size();
   for (int i=0;i<isize;i++) {
    Map<String, Object> msyaiyousr = msTaiyousr.get(i);
    String id = (String) msyaiyousr.get("taiyousrid");
    String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn");
    keys.add(usrtorokukbn+":"+id);
   }   
  
   int jsize = wkTaiyousr.size();
   for (int j=0;j<jsize;j++) {
    Map<String, Object> wktaiyousr = wkTaiyousr.get(j);
    String id = (String) wktaiyousr.get("taiyousrid");
    String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");
    if (keys.contains(usrtorokukbn+":"+id)) {
      updateList.add(wktaiyousr);
     } else {
      insertList.add(wktaiyousr);
    }
   }

由于 第二个for循环使用了 ArrayList的contains方法,跑完第二个for循环使用了 12分钟左右,我的个天,第一个循环不到1秒。然后使用了 HashSet 代替 ArrayList 代码如下:


Set<String> keys = new HashSet<String>();
   int isize = msTaiyousr.size();
   for (int i=0;i<isize;i++) {
    Map<String, Object> msyaiyousr = msTaiyousr.get(i);
    String id = (String) msyaiyousr.get("taiyousrid");
    String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn");
    keys.add(usrtorokukbn+":"+id);
   }
  
   int jsize = wkTaiyousr.size();
   for (int j=0;j<jsize;j++) {
    Map<String, Object> wktaiyousr = wkTaiyousr.get(j);
    String id = (String) wktaiyousr.get("taiyousrid");
    String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");
    if (keys.contains(usrtorokukbn+":"+id)) {
      updateList.add(wktaiyousr);
     } else {
      insertList.add(wktaiyousr);
    }
   }

结果不到1秒,两个for循环瞬间跑完。果然大数据的时候还是不要用到ArrayList的contains方法,改用HashSet的吧。

以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程网。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯