[Java] 배열 내 존재여부 확인 시 List와 Set 동작방식 및 성능 차이

Java에서 배열 내 특정 값 존재 여부 확인 시 List와 Set의 성능 차이를 비교하고자 한다.

(10개 정도 검사하는 경우 크게 차이는 안나는데 몇만개 를 넘어 자주 사용하는 경우 성능 차이가 나기 때문에)

 

자료구조	대표 구현체	contains() 시간복잡도	탐색방식
List	ArrayList	O(n)	순차 탐색
Set	HashSet	O(1) 평균 / O(n) 최악	해시 기반
Set	TreeSet	O(log n)	이진 탐색 트리

List(ArrayList) 는 내부적으로 앞에서부터 끝까지 하나씩 비교하며 equals() 를 사용하여 값을 비교한다. 때문에 데이터가 많아질수록 시간이 선형적으로 증가한다.

Set(HashSet) 은 hashCode()로 해시 버킷 위치를 계산하며 동일 버킷 내에서 equals() 로 비교한다. 평균적으로 한번에 접근하며 데이터 수가 커질수록 List대비 압도적으로 빠르다.

Set(TreeSet) 은 이진 탐색 트리 기반 Set 구현체로 HashSet에 비해 느리지만 정렬이 유지된다는 장점이 있다. 

 

List는 전체 순회, Set은 해시 순회로 알고 있었는데 TreeSet이란 선택지가 있다는걸 알게 되었다. TreeSet는 잘 못 본 것 같은데 안쓰는 이유가 있지 않을까 싶어 알아보았다.

 

HashSet은 주소 비교이고, TreeSet은 비교를 반복하는 이진 탐색이기 때문에 Treeset이 느려져 존재여부 확인만이 목적이라면 TreeSet을 사용할 이유가 없는 것이었다. TreeSet은 hashCode()도, equals() 도 거의 사용하지 않는다고 한다. 그리고 비교 비용이 높고 메모리/캐시 효율이 나쁘다고 한다. 그리고 Set을 쓰는 이유는 대부분 중복 제거 / 존재 여부 체크 인데, Hashset을 두고 효율 안좋은 TreeSet을 쓸 이유가 없다... (정렬은 보통 DB에서 하니) 

 

최종 정리

존재여부 검사할때에는 HashSet 쓰자.