纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

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

zhulj625   2021-05-26 我要评论
想了解Java集合中contains方法的效率对比分析的相关内容吗zhulj625在本文为您仔细讲解Java contains效率对比的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Java集合,contains方法,效率对比下面大家一起来学习吧。

最近让部门技术大佬帮忙代码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序列化对象的时候这个属性就不会被序列化。
    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    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的吧。

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


相关文章

猜您喜欢

  • swagger用法与swagger-ui使用 Spring项目中swagger用法与swagger-ui使用

    想了解Spring项目中swagger用法与swagger-ui使用的相关内容吗上善若水在本文为您仔细讲解swagger用法与swagger-ui使用的相关知识和一些Code实例欢迎阅读和指正我们先划重点:swagger用法,swagger-ui使用下面大家一起来学习吧。..
  • C++职工管理系统 C++实现职工管理系统

    想了解C++实现职工管理系统的相关内容吗培培不是我小宝贝在本文为您仔细讲解C++职工管理系统的相关知识和一些Code实例欢迎阅读和指正我们先划重点:C++职工管理系统,C++管理系统,C++职工管理下面大家一起来学习吧。..

网友评论

Copyright 2020 www.Videogametimes.com 【视游时光】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式