[자료구조] Set과 Hash set

목차

• Set의 개념
• Set의 주요 특징
• Set이 적합/부적합한 상황
• Set의 시간 복잡도
• Set과 List의 비교
• Set 의 구현체들
• Hash Set

 

Set 이란?

Set(집합)은 중복된 요소를 허용하지 않는 데이터를 저장하는 추상 자료형이다. 주로 빠른 검색, 삽입, 삭제 연산을 위해 사용된다.

Set은 수학적 집합과 유사하게 동작하며, 중복된 값이 없고 순서에 상관없이 요소들이 저장된다.

Set은 해시 테이블이나 이진 탐색 트리와 같은 데이터 구조를 기반으로 구현되며, 내부적으로 어떤 자료구조로 구현되었느냐에 따라 성능이 달라진다.

---

Set의 주요 특징

1. 중복된 요소 허용 안 함: Set은 중복된 값을 저장할 수 없다. 같은 값을 여러 번 추가해도 하나만 저장된다.
2. 순서 없음: Set의 요소들은 특정한 순서가 없으며, 요소를 삽입한 순서대로 저장되지 않는다.
3. 빠른 검색, 삽입, 삭제: 일반적으로 해시 테이블을 사용하여 O(1)에 가까운 시간 복잡도로 삽입, 삭제, 검색 연산이 가능하다.
4. 자동 정렬이 없음: Set은 값들이 자동으로 정렬되지 않는다. (정렬된 집합은 TreeSet과 같은 특수한 자료구조로 구현된다.)
5. 멤버십 테스트: 특정 요소가 집합에 포함되어 있는지 여부를 빠르게 확인할 수 있다. (O(1)에 가까운 성능)
6. 집합 연산 제공: 합집합, 교집합, 차집합, 대칭 차집합 등의 집합 연산을 제공한다.

---

Set이 적합 / 부적합한 상황

[✅ 적합한 상황]

 

1. 중복된 데이터를 허용하지 않으면서 빠른 검색, 삽입, 삭제가 필요한 경우

• 예를 들어, 사용자 ID 목록을 관리할 때, 중복된 ID를 저장하지 않기 위해 Set을 사용할 수 있다.

2. 특정 값이 존재하는지 여부를 빠르게 확인해야 할 때

• 빠른 멤버십 테스트가 필요할 때 Set이 유용하다.

3. 중복된 데이터를 제거해야 할 때

• Set은 중복을 허용하지 않기 때문에 중복된 데이터를 넣어도 최종적으로는 중복되지 않는 데이터만 남게 된다.

 

[❌ 부적합한 상황]

 

1. 순서가 필요할 때 부적합

• 순서가 중요한 경우 Set 대신 List나 배열 같은 자료구조가 적합하다.

2. 중복된 데이터를 허용하지 않음

• 중복된 데이터를 처리해야 하는 경우 Set은 부적합하다.

---

Set의 시간 복잡도

여기서 n은 집합의 크기이며, 해시 기반의 Set을 기준으로 시간 복잡도를 설명하고 있다.

트리 기반 Set의 경우, 검색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)이다.

연산	시간 복잡도 (해시 기반 Set)	설명
삽입	O(1)	요소를 집합에 추가한다.
삭제	O(1)	요소를 집합에서 제거한다.
검색	O(1)	특정 요소가 집합에 있는지 확인한다.
크기 확인	O(1)	집합의 크기를 반환한다.
합집합	O(n)	두 집합의 합집합을 계산한다.
교집합	O(n)	두 집합의 교집합을 계산한다.
차집합	O(n)	두 집합의 차집합을 계산한다.

---

Set과 List 비교

특징	Set	List
중복 허용 여부	허용하지 않음	중복된 값 허용
순서 보장 여부	순서 보장되지 않음	삽입된 순서 유지
검색 시간 복잡도	O(1) (해시 기반) / O(log n) (트리 기반)	O(n)
삽입 시간 복잡도	O(1) (해시 기반) / O(log n) (트리 기반)	O(1) (끝에 삽입할 때) / O(n) (정렬된 경우)
삭제 시간 복잡도	O(1) (해시 기반) / O(log n) (트리 기반)	O(n)

---

Set 의 구현체들

 

HashSet:

• 가장 일반적인 Set 구현체로, 해시 테이블을 기반으로 동작한다.
• 순서를 보장하지 않으며, 중복된 요소를 허용하지 않는다. 빠른 검색, 삽입, 삭제가 가능하다.

TreeSet:

• 이진 탐색 트리(Red-Black Tree)를 기반으로 한 Set 구현체이다.
• 요소들이 자동으로 정렬되며, 중복을 허용하지 않는다. 검색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)이다.

LinkedHashSet:

• HashSet의 변형으로, 요소들이 삽입된 순서를 유지하는 Set이다.
• 해시 테이블을 사용하여 구현되며, 삽입된 순서대로 순회가 가능

---

Hash Set

HashSet은 해시 테이블을 기반으로 요소를 저장하는 Set의 한 구현체이다.

이 Set은 중복을 허용하지 않으며, 요소의 순서가 유지되지 않는다.

해시 함수를 사용하여 요소의 위치를 결정하며, 이를 통해 빠른 접근 시간을 제공한다.

HashSet은 보통 고유한 데이터를 관리할 때 많이 사용된다.

 

HashSet의 특징

1. 중복 허용 안 함: 같은 값을 여러 번 추가하려고 해도 한 번만 저장된다.
2. 순서가 없음: 삽입된 순서를 유지하지 않고, 데이터의 순서는 해시값에 의해 결정된다.
3. 빠른 삽입, 삭제, 검색: 해시 테이블을 기반으로 하여 대부분의 연산에서 O(1)의 시간 복잡도를 가진다.
4. null 값 허용: HashSet은 null 값을 허용한다. 다만, 한 번만 추가할 수 있다.

 

HashSet의 시간 복잡도

특징	평균 시간 복잡도	최악의 시간 복잡도
삽입	O(1)	O(n)
삭제	O(1)	O(n)
검색	O(1)	O(n)

• 만약 해시 충돌이 빈번하게 발생해 모든 요소가 동일한 버킷에 들어가면, 각 요소는 연결 리스트나 트리 형태로 관리되며, 이 경우에는 순차적으로 요소를 검색해야 하므로 O(n)의 시간 복잡도가 된다.

 

 

HashSet의 활용 사례

• 중복 제거:
  • 문자열이나 숫자 목록에서 중복을 제거하고 고유한 값만 유지할 때 사용된다.
  • 예를 들어, 사용자 ID 목록에서 중복된 ID를 걸러낼 때 유용하다.
• 고유 데이터 저장: 고유한 요소들(예: 학번, 제품 코드 등)을 저장하는 데 적합하다.
• 멤버십 테스트: 특정 값이 존재하는지 빠르게 확인하는 작업에서 사용된다.

---