[Java] Set

Set, java.util.Set, Java Set, Set interface, 집합

정의

java.util.Set<E> 는 중복을 허용하지 않는 Collection. 수학의 집합 (set) 에 대응. 같은 원소를 두 번 추가하면 두 번째는 무시된다.

Collection 인터페이스의 모든 메서드를 그대로 사용하면서, equals 와 hashCode (또는 compareTo) 로 중복 판단.

핵심 메서드

메서드	의미
add(E)	추가, 이미 있으면 false 반환
contains(Object)	포함 여부
remove(Object)	제거
size()	원소 개수

추가/조회/삭제의 시간 복잡도는 구현체에 따라 다르다.

구현체 비교

구현	백킹	평균 시간	순서
HashSet	HashMap	O(1)	없음
LinkedHashSet	LinkedHashMap	O(1)	삽입 순서
TreeSet	TreeMap	O(log n)	정렬
CopyOnWriteArraySet	CopyOnWriteArrayList	O(n) (선형 검색)	삽입 순서
ConcurrentSkipListSet	ConcurrentSkipListMap	O(log n)	정렬, 동시성
EnumSet	bit vector	O(1)	enum 순서

대부분의 Set 구현은 내부적으로 Map 을 사용, key 만 노출하고 value 는 dummy.

불변 Set

Set<Integer> primes = Set.of(2, 3, 5, 7, 11);

null 비허용, 중복 인자 전달 시 IllegalArgumentException.

자주 쓰이는 set 연산

Set<Integer> a = new HashSet<>(List.of(1, 2, 3));
Set<Integer> b = new HashSet<>(List.of(2, 3, 4));

Set<Integer> union = new HashSet<>(a); union.addAll(b);          // {1,2,3,4}
Set<Integer> inter = new HashSet<>(a); inter.retainAll(b);       // {2,3}
Set<Integer> diff = new HashSet<>(a); diff.removeAll(b);         // {1}

addAll, retainAll, removeAll 의 비용은 인자의 contains 가 빠를수록 좋다.

동기화

Set<Integer> sync = Collections.synchronizedSet(new HashSet<>());
Set<Integer> cow = new CopyOnWriteArraySet<>();       // 읽기 多, 쓰기 少
Set<Integer> csl = new ConcurrentSkipListSet<>();    // 정렬 + 동시성

ConcurrentHashMap 의 keySet() view 도 thread-safe 집합으로 자주 활용.

Set<Integer> set = ConcurrentHashMap.newKeySet();

함정

1. 가변 객체를 원소로

HashMap 과 같은 함정. hashCode/equals 가 변하는 원소는 Set 에서 찾을 수 없게 된다.

2. equals 만 override

Object 의 규약 위반. HashSet, LinkedHashSet 이 잘못 동작.

참고

• Object
• Iterable
• Collection
• Map
• HashSet
• TreeSet
• CopyOnWriteArrayList