들어가며
알고리즘 공부 중 HashSet / LinkedHashSet / TreeSet 을 비교 정리했습니다.
HashSet
특징
Set인터페이스 구현체 → 중복 요소 허용 X
- 내부적으로 HashMap을 이용해 구현됨 (값은 key로 저장, value는 dummy)
- 저장 순서를 보장하지 않음 (출력할 때 삽입한 순서와 다를 수 있음)
null값 저장 가능 (단, 하나만)
시간 복잡도
- 평균적으로
add,remove,contains모두 O(1)
- 해시 충돌이 많으면 성능 저하 가능 (최악의 경우 O(n))
활용
- 중복 없는 데이터 집합 필요할 때
- 순서 상관없이 빠른 검색이 필요할 때
LinkedHashSet
특징
HashSet을 상속해서 구현됨
- 내부적으로 HashMap + 이중 연결 리스트(Doubly Linked List) 구조 사용
- 요소의 삽입 순서를 유지 (iteration 시 저장된 순서대로 출력됨)
null값 저장 가능 (단, 하나만)
시간 복잡도
HashSet과 동일 → 평균 O(1)
활용
- 중복 없는 집합 + 저장 순서를 유지해야 하는 경우
- 캐시(cache) 구현 시 종종 사용 (예: LRU 알고리즘)
TreeSet
특징
NavigableSet인터페이스 구현체
- 내부적으로 Red-Black Tree(이진 탐색 트리) 로 구현됨
- 요소가 자동 정렬됨 (자연 순서 or Comparator 지정 가능)
null값 저장 불가 (NullPointerException 발생)
시간 복잡도
add,remove,contains모두 O(log n) (트리 탐색 기반)
활용
- 정렬된 순서로 데이터를 관리해야 할 때
- 범위 검색, 정렬 기반 탐색이 필요한 경우
HashSet vs LinkedHashSet vs TreeSet
| 구분 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 중복 허용 여부 | ❌ (불가) | ❌ (불가) | ❌ (불가) |
| 순서 보장 | ❌ (불규칙) | ✅ (삽입 순서 유지) | ✅ (정렬 순서 유지) |
| 내부 구조 | HashMap | HashMap + LinkedList | Red-Black Tree |
| null 저장 | 가능 (1개) | 가능 (1개) | 불가 |
| 시간 복잡도 | 평균 O(1), 최악 O(n) | 평균 O(1), 최악 O(n) | O(log n) |
| 특징/활용 | 중복 없는 집합, 빠른 검색 | 중복 없는 집합 + 삽입 순서 유지 | 중복 없는 집합 + 정렬 필요 |
요약
- HashSet → 순서 신경 안 쓰고, 중복 없는 빠른 집합 필요할 때
- LinkedHashSet → 순서를 유지하면서도 중복 없는 집합 필요할 때
- TreeSet → 자동 정렬이 필요하고, 범위 검색/정렬 탐색이 중요한 경우
마치며
읽어주셔서 감사합니다.
참고자료
HashSet, LinkedHashSet, TreeSet의 특성과 차이
자바[JAVA] : Set - HashSet / TreeSet / LinkedHashSet 알아보기.
Set이란? HashSet, TreeSet, LinkedHashSet
