Java集合におけるcontains方法の効率比較分析

最近、部門の技術者にコードreviewを手伝ってもらった時、彼は小さい技術の詳細を指摘してくれました。つまり、集合のcontains方法について、できるだけSetを選んでListではなく、普段はあまり注意していません。
Java集合List、Setは、集合中の要素が存在するかどうかの判断方法contains（Object o）である。Mapにはkey及びvalueが存在するかどうかを判断する方法containsKeyとcontainsValueがあります。
1.ArayList
ArayListにおける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
containsky
contains Value
ArayList
O（N）
ハイセット
O(1)
ハshKey
O(1)
O（N）
このような技術の詳細については、日頃から注意と蓄積を必要とし、絶えず学習と記録を行い、実際の開発に応用し、常に運行効率を向上させる。今後もこれらの技術の詳細を記録し、日常的な開発に活用していきます。
追加：ArayListの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サイクルはアーライリストのcontains方法を使っていますので、第二のforサイクルを走り終えて12分ぐらい使いました。私の一日は、最初のサイクルは1秒未満です。次に、HashSetを使用して、ArayListコードの代わりに次のようにします。

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秒未満で、2つのforサイクルは瞬間的に走り終わります。やはりビッグデータの場合はアラーリストのcontainsを使わずにHashSetに切り替えましょう。
以上は個人の経験ですので、参考にしていただければと思います。