서론

위의 알고리즘 문데에서 ArraysList의 contains 메소드를 호출해 해당 데이터가 들어있는지 확인하였고 해당 부분에서 시간 초과가 되었다.

해당 문제로 ArrayList의 contains는 시간복잡도가 O(n)이고 HashSet의 경우 시간 복잡도가 O(1)이라는 사실을 알게 되었다.

ArrayList의 contians 동작 방식

ArrayList의 contains 메소드 이다.

public boolean contains(Object o) {
		return indexOf(o) >= 0;
}

indexOf를 호출하며 indexOf메소드는 아래와 같다

public int indexOf(Object o) {
		return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
		Object[] es = elementData;
	  if (o == null) {
	      for (int i = start; i < end; i++) {
	          if (es[i] == null) {
	              return i;
	          }
	      }
	  } else {
	      for (int i = start; i < end; i++) {
	          if (o.equals(es[i])) {
	              return i;
	          }
	      }
	  }
	  return -1;
}

ArrayList의 데이터를 가지고 있는 배열인 elementData에서 인덱스를 0부터 시작해 해당 객체의 값이 몇 번째 인덱스에 존재하는 지 확인 한 후 인덱스가 0보다 클 경우 true를 반환한다.

이는 순차적으로 모든 인덱스를 확인하여, 만약 뒤쪽 인덱스에 저장되어 있는 데이터일 수록 성능이 나빠진다.

HashSet의 contains

HahsSet은 HashMap으로 구현되어서 HashMap의 containsKey 메소드를 호출한다.

public boolean contains(Object o) {
     return map.containsKey(o);
}

containsKeys는 HashMap의 get메서드랑 거이 동일하다.

public boolean containsKey(Object key) {
    return getNode(key) != null;
}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(key)) == null ? null : e.value;
}