Set 계열: 중복 없는 고유 원소 집합

HashSet

해시 테이블 기반의 집합으로, 내부적으로 HashMap을 사용합니다
HashSet은 요소의 순서를 보장하지 않습니다

성능

평균적으로 삽입(add), 검색(contains), 삭제(remove) 모두
평균 O(1) 시간복잡도로 매우 효율적인 자료 구조입니다
자바 8부터 HashSet에 일정 수 이상 노드가 쌓이면 Red-Black Tree로 변환하여
최악 성능을 O(log n)으로 개선했습니다. (자바 7까지는 최악 O(n))

장점

중복 없이 빠른 검색이 필요한 상황에 적합합니다
집합 연산이나 포함 여부 검사에 유리하며, 평균 성능이 뛰어납니다

단점

저장 순서가 유지되지 않아 순회 결과의 예측이 불가능합니다

기타

thread-unsafe하기때문에, 멀티스레드에서는 ConcurrentHashMap 기반의 동시성 Set이 필요합니다

LinkedHashSet

HashSet을 확장하며, 이중 연결 리스트로 요소의 삽입 순서를 유지합니다
내부적으로 LinkedHashMap을 사용합니다.

성능

기본 동작은 HashSet과 동일하게 평균적인 상황에서 시간복잡도 O(1) 성능을 가집니다
순회는 삽입 순서대로 진행됩니다.

메모리

각 노드가 앞뒤를 연결하는 포인터를 추가로 가져 HashSet보다 메모리 사용이 높습니다

장점

입력 순서를 유지해야 하는 Set이 필요할 때 사용하기 좋습니다
빠른 검색과 순서 유지를 모두 제공합니다.

단점

HashSet 대비 약간의 메모리/연산 오버헤드가 있습니다
정렬 순서는 지원하지 않고 삽입된 순서만 보존합니다

TreeSet

레드-블랙 트리 기반의 정렬 이진트리로 구현됩니다
NavigableSet/SortedSet 인터페이스를 구현하여 요소들이 정렬된 상태로 저장됩니다

성능

삽입(add), 검색(contains), 삭제(remove)가 모두 O(log n)의 시간이 걸립니다
이는 트리 높이에 비례하는 탐색이 필요하기 때문입니다

HashSet보다는 느리지만 정렬된 순서를 유지하기 위해 사용되며, 반복은 오름차순으로 진행됩니다

메모리

각 요소를 노드로 가지는 트리 구조로, 포인터(부모, 자식) 및 균형 트리 유지 정보를 포함하여
HashSet보다 요소당 메모리 오버헤드가 높습니다.

장점

자동 정렬의 장점을 가지며, 삽입과 동시에 정렬이 필요할 때 유용합니다,
NavigableSet API를 통해 범위 검색(subSet)이나 이진 탐색 유사 조회(higher(), lower()) 기능을 제공합니다

단점

동일한 작업에서 HashSet보다 느립니다
데이터 양이 방대하고 순서가 필요 없을 경우 비효율적입니다

기타

Comparator를 전달하여 사용자 정의 순서를 적용할 수 있습니다
멀티스레드 환경에서는 thread-unsafe하므로 ConcurrentSkipListSet 등을 고려해야 합니다

참고

• 자바 성능 튜닝 이야기 - 4챕터