자바 집합 에서 contains 방법의 효율 비교 분석

최근 에 부서 기술 자 에 게 코드 review 를 도와 달라 고 했 을 때 그 는 나 에 게 작은 기술 디 테 일 을 지적 했다.즉,집합 하 는 contains 방법 에 대해 리스트 가 아 닌 Set 을 사용 하 는 것 이다.평소에 별로 주의 하지 않 고 소스 코드 를 자세히 보 았 다.큰 사람 은 큰 사람 이 고 기술 디 테 일 도 꽉 잡 았 다.
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)입 니 다.
contains Value 방법 에 대해 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)
이런 기술 세부 사항 에 대해 평소에 주의 하고 축적 하 며 계속 공부 하고 기록 하 며 실제 개발 에 응용 하여 운영 효율 을 계속 향상 시 켜 야 한다.후속 적 으로 도 이런 기술 세부 사항 을 기록 하여 일상적인 개발 에서 활용 할 것 이다.
보충:Array List 의 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 순환 은 Array List 의 contains 방법 을 사 용 했 기 때문에 두 번 째 for 순환 을 마치 고 12 분 정도 사 용 했 습 니 다.제 하루,첫 번 째 순환 은 1 초 도 안 됩 니 다.그리고 ArrayList 코드 대신 HashSet 을 사 용 했 습 니 다.다음 과 같 습 니 다.

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 순환 이 순식간에 끝났다.역시 빅 데 이 터 는 Array List 의 contains 방법 을 사용 하지 말고 HashSet 로 바 꾸 세 요.
이상 은 개인 적 인 경험 이 므 로 여러분 에 게 참고 가 되 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.