快捷導(dǎo)航

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

更新時間：2021年05月26日 15:13:19 作者：zhulj625

這篇文章主要介紹了Java集合中contains方法的效率對比分析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

最近讓部門技術(shù)大佬幫忙代碼review的時候，他給我指出了一個小的技術(shù)細節(jié)，就是對于集合的contains方法盡量選用Set而不是List，平時沒怎么注意，仔細看了下源碼，大佬就是大佬，技術(shù)細節(jié)也把握的死死的。

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

1.ArrayList

在ArrayList中contains方法通過遍歷list中的元素，利用==或equals來判斷是否存在目標(biāo)元素，復(fù)雜度為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中，判斷元素是否存在即是判斷對應(yīng)Map中key是否存在。

HashSet:
    private transient HashMap<E,Object> map; //將不需要序列化的屬性前添加關(guān)鍵字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的底層主要是基于數(shù)組和鏈表（散列表或者叫哈希表）來實現(xiàn)的，它之所以有相當(dāng)快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。

所以containsKey通過key的哈希值直接查找key是否存在，時間復(fù)雜度為O(1)，響應(yīng)的HashSet查找元素的時間復(fù)雜度也是O(1)。

對于containsValue方法判斷map中是否存在value的判斷，其方法為將map中的Node數(shù)組進行遍歷，然后判斷是否存在。

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.總結(jié)

集合各方法的時間復(fù)雜度	contains	containskey	containsValue
ArrayList	O(N)
HashSet	O(1)
HashKey		O(1)	O(N)

對于這種技術(shù)細節(jié)需要平時注意和積累，不斷學(xué)習(xí)和記錄，應(yīng)用于實際開發(fā)中，不斷提高運行效率。后續(xù)也會將這些技術(shù)細節(jié)記錄下來，在日常開發(fā)中加以運用。

補充：ArrayList的contains方法的效率果然不高

看代碼吧~

之前做的一個項目，數(shù)據(jù)庫抽出了40多萬條數(shù)據(jù)，然后從csv文件抽出了大概也是40多萬條數(shù)據(jù)，進行對比分析之前代碼如下：

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循環(huán)使用了 ArrayList的contains方法，跑完第二個for循環(huán)使用了 12分鐘左右，我的個天，第一個循環(huán)不到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);
    }
   }

結(jié)果不到1秒，兩個for循環(huán)瞬間跑完。果然大數(shù)據(jù)的時候還是不要用到ArrayList的contains方法，改用HashSet的吧。

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: