[DataStructure/Set] Set의 contains() 시간 복잡도 정리: HashSet, TreeSet, LinkedHashSet 비교

 

Set을 공부하던 중, Set.contains() 메서드의 시간 복잡도가 궁금했는데, Set의 자료구조 종류에 따라 contains()의 성능이 달라진다는 것을 알게 되었습니다.

특히, HashSet, TreeSet, LinkedHashSet과 같이 구현 방식이 다른 Set은 각각 다른 자료구조를 사용하기 때문에 contains()의 시간 복잡도도 다르게 동작합니다.

이번 글에서는 Set의 종류별 contains() 성능 차이와 시간 복잡도를 정리해 보겠습니다.

---

1. Set.contains()의 시간 복잡도는 언제 달라질까?

Set.contains(element) 메서드는 Set에 특정 요소가 존재하는지 여부를 확인하는 메서드입니다.
하지만 Set의 내부 자료구조에 따라 검색 속도가 다르게 동작합니다.

• HashSet → 해시 테이블 사용 (O(1), 최악 O(N))
• TreeSet → 이진 탐색 트리 사용 (O(log N))
• LinkedHashSet → 해시 테이블 + 연결 리스트 사용 (O(1), 최악 O(N))

각 Set 구현체별 contains()의 동작 방식과 성능을 자세히 살펴보겠습니다.

---

2. Set 구현체별 contains() 성능 비교

1) HashSet.contains() → 평균 O(1), 최악 O(N)

HashSet은 해시 테이블(Hash Table)을 기반으로 동작합니다.

contains()를 실행하면:

1. 객체의 hashCode()를 계산하여 해시 값 생성
2. 해시 값을 기반으로 적절한 버킷(bucket)에서 요소 검색
3. 해당 버킷 내에서 equals() 비교를 수행하여 요소 확인

따라서 평균적으로 O(1)의 시간 복잡도를 가지지만, 해시 충돌이 발생하면 최악의 경우 O(N)까지 증가할 수 있습니다.

시간 복잡도 정리

• 평균: O(1)
• 최악: O(N) (해시 충돌이 심할 경우)

 

2) TreeSet.contains() → O(log N)

TreeSet은 이진 탐색 트리(Red-Black Tree)를 기반으로 동작합니다.

contains()를 실행하면:

1. 트리의 루트에서 시작하여 이진 탐색 수행
2. 현재 노드와 찾는 값 비교 (<, > 연산 수행)
3. 값을 찾을 때까지 log N 단계만큼 내려감

따라서 트리의 균형이 유지되므로 항상 O(log N)의 시간 복잡도를 보장합니다.

시간 복잡도 정리

• 항상 O(log N)

 

3) LinkedHashSet.contains() → 평균 O(1), 최악 O(N)

LinkedHashSet은 HashSet과 유사하지만, 추가적으로 이중 연결 리스트(Linked List)를 유지합니다.
따라서 HashSet과 동일하게 평균 O(1), 최악 O(N)의 성능을 가집니다.

contains()를 실행하면:

1. HashSet처럼 해시 테이블을 기반으로 검색
2. 요소가 저장된 순서를 유지하기 위해 연결 리스트를 활용

다만, 해시 충돌이 많을 경우에는 최악의 경우 O(N)까지 증가할 수 있습니다.

시간 복잡도 정리

• 평균: O(1)
• 최악: O(N) (해시 충돌이 심할 경우)

---

3. Set.contains() 시간 복잡도 비교 정리

Set 종류	내부 자료구조	contains() 평균 시간 복잡도	최악의 시간 복잡도
HashSet	해시 테이블	O(1)	O(N) (해시 충돌 심할 경우)
TreeSet	이진 탐색 트리	O(log N)	O(log N)
LinkedHashSet	해시 테이블 + 연결 리스트	O(1)	O(N) (해시 충돌 심할 경우)

---

5. 결론

• Set.contains()의 시간 복잡도는 Set의 구현체(HashSet, TreeSet, LinkedHashSet)에 따라 다릅니다.
• 가장 빠른 contains()를 원하면 HashSet을 사용하지만, 최악의 경우 O(N)이 될 수 있습니다.
• 트리 구조(TreeSet)는 O(log N)이지만, 정렬된 데이터를 유지하는 장점이 있습니다.
• LinkedHashSet은 입력 순서를 유지하면서도 HashSet과 유사한 O(1) 성능을 제공합니다.

Set을 선택할 때 정렬이 필요한가, 입력 순서가 중요한가, 빠른 검색이 필요한가 등을 고려하면 적절한 구현체를 선택할 수 있습니다.

이번 글을 통해 Set의 contains() 시간 복잡도가 자료구조에 따라 달라질 수 있다는 점을 정리할 수 있었습니다.