Set

Set의 주요 특징

1. 중복된 데이터를 허용하지 않음: Set은 중복된 요소를 저장하지 않으며, 데이터의 유일성을 보장한다. 동일한 값을 여러 번 저장하려고 시도해도 단 하나의 값만 저장된다.
2. 순서 보장 안 됨: Set은 요소의 순서를 보장하지 않는다. 데이터의 삽입 순서와 상관없이 요소들이 저장되며, 순서가 중요한 경우에는 다른 컬렉션을 사용하는 것이 좋다.
3. 빠른 조회 성능: Set은 데이터를 검색할 때 평균적으로 O(1)의 시간 복잡도를 가진다. 이는 해시 테이블을 사용하기 때문이다. 다만, TreeSet의 경우에는 O(log n)의 시간 복잡도를 가진다.
4. 메모리 사용: Set은 해시 테이블을 사용하여 데이터의 유일성을 보장하는데, 이는 추가적인 메모리 오버헤드를 발생시킬 수 있다. 특히, LinkedHashSet은 순서를 유지하기 위해 추가적인 메모리를 사용하고, TreeSet은 트리 구조를 유지하기 위한 포인터와 같은 추가적인 메모리 사용이 발생한다.

 

Set을 사용해야 할 때

1. 중복 제거: 데이터 컬렉션에서 중복된 값을 제거해야 할 때 적합하다.
2. 빠른 검색: 값의 존재 여부를 빠르게 확인해야 할 때 사용한다.
3. 집합 연산: 교집합, 합집합, 차집합 등의 집합 연산을 수행해야 할 때 유용하다.

 

Set의 주요 구현체

1. HashSet
   • 특징: 해시 테이블을 사용하여 데이터를 저장하는 가장 일반적인 Set 구현체이다. 값을 해시 테이블의 key로 넣는다.
   • 장점: 매우 빠른 조회와 추가, 삭제 성능을 제공한다.
   • 단점: 데이터의 순서가 유지되지 않으며, 삽입 순서도 보장하지 않는다.
   • 사용 시기: 빠른 검색과 중복 제거가 중요한 경우에 적합하다.
2. TreeSet
   • 특징: 이진 탐색 트리(일반적으로 Red-Black Tree)를 사용하여 데이터를 저장한다.
   • 장점: 데이터를 정렬된 상태로 유지하여 순서에 따라 접근할 수 있다.
   • 단점: HashSet보다 느린 성능(O(log n))을 가진다.
   • 사용 시기: 데이터의 정렬된 순서가 필요하거나 범위 검색이 필요한 경우에 적합하다.
3. LinkedHashSet
   • 특징: 해시 테이블과 링크드 리스트를 결합한 구조로 구현된다.
   • 장점: 삽입된 순서를 유지하면서도 HashSet과 유사한 성능을 제공한다.
   • 단점: 해시 테이블에 링크드 리스트를 추가하기 때문에 약간의 메모리 오버헤드가 발생할 수 있다.
   • 사용 시기: 삽입 순서를 유지해야 하면서 HashSet의 성능을 유지하고 싶은 경우에 적합하다.

 

CPython의 set과 Java의 HashSet 비교

구현	CPython의 set	Java의 HashSet
해시 충돌 해결 방법	Open addressing	Separate chaining
초기 capacity	8	16
데이터 접근 시간	capacity와 상관없이 O(1)	capacity와 상관없이 O(1)
리사이징 타이밍	capacity의 2/3 이상 사용 시	capacity의 3/4 이상 사용 시
리사이즈 규모	유효 데이터 > 50,000 ? 2배 : 4배	2배
capacity 축소 가능성	리사이징 시 더미 데이터가 많다면 새로운 capacity가 이전보다 작을 수 있음	없음
capacity	2의 승수