快捷導(dǎo)航

Java集合中contains方法的效率對(duì)比分析

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

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

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

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

1.ArrayList

在ArrayList中contains方法通過(guò)遍歷list中的元素，利用==或equals來(lái)判斷是否存在目標(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中，判斷元素是否存在即是判斷對(duì)應(yīng)Map中key是否存在。

HashSet:
    private transient HashMap<E,Object> map; //將不需要序列化的屬性前添加關(guān)鍵字transient，序列化對(duì)象的時(shí)候，這個(gè)屬性就不會(huì)被序列化。
    /**
     * 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中有兩個(gè)contains方法，一個(gè)判斷key是否存在，一個(gè)判斷value是否存在。

HashMap的底層主要是基于數(shù)組和鏈表（散列表或者叫哈希表）來(lái)實(shí)現(xiàn)的，它之所以有相當(dāng)快的查詢(xún)速度主要是因?yàn)樗峭ㄟ^(guò)計(jì)算散列碼來(lái)決定存儲(chǔ)的位置。

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

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

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é)

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

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

補(bǔ)充：ArrayList的contains方法的效率果然不高

看代碼吧~

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

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

由于第二個(gè)for循環(huán)使用了 ArrayList的contains方法，跑完第二個(gè)for循環(huán)使用了 12分鐘左右，我的個(gè)天，第一個(gè)循環(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秒，兩個(gè)for循環(huán)瞬間跑完。果然大數(shù)據(jù)的時(shí)候還是不要用到ArrayList的contains方法，改用HashSet的吧。

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

您可能感興趣的文章: