[C#] 해시셋 (HashSet)

 

 

1. 해시셋(HashSet)이란?

 

해시셋(HashSet)은 C#의 'System.Collections.Generic' 네임스페이스에 포함된 컬렉션 클래스 중 하나로, 해시 테이블을 기반으로 구현된 집합 데이터 구조입니다. 해시셋은 중복되지 않은 요소들의 모임을 관리하는데 최적화되어 있으며, 빠른 탐색, 추가 및 삭제 작업을 제공합니다. 이는 특히 고유한 값들만을 유지해야 하는 경우에 유용합니다.

 

 

 

---

2. 내부 작동 구조

해시셋의 내부 구조는 해시 테이블을 기반으로 합니다. 해시 테이블은 키-값 쌍을 저장하는 데이터 구조로, 키를 해시 함수에 의해 해시 코드로 변환하고, 이 해시 코드를 인덱스로 사용하여 요소를 저장합니다. 해시 셋의 작동 원리는 다음과 같습니다.

 

1. 해시 함수: 해시 함수는 객체의 고유한 해시 코드를 생성합니다. 이 해시 코드는 요소를 저장할 버킷을 결정하는데 사용합니다. 해시 함수는 객체의 상태를 기반으로 고유한 정수 값을 반환하는 함수 입니다. 예를 들어, 문자열 객체의 해시 코드는 문자열의 각 문자 ASCII 값을 더하거나 곱한 값으로 계산될 수 있습니다.
   
   
2. 버킷: 해시 테이블은 여러 버킷으로 구성됩니다. 각 버킷은 동일한 해시 코드를 가진 요소들의 목록을 저장합니다. 버킷은 배열의 인덱스로 참조됩니다. 해시 코드를 배열의 길이로 모듈러 연산하여 해당 버킷의 인덱스를 결정합니다.
   
   
3. 충돌 해결: 해시 충돌이 발생하면, 즉 두 요소가 동일한 해시 코드를 가지게 되면, 체이닝(Chaining) 또는 오픈 어드레싱(Open Addressing) 등의 방법으로 충돌을 해결합니다. C#의 해시셋은 주로 체이닝을 통해 충돌을 해결합니다.
   해시 충돌에 대한 자세한 설명은 (https://unity-programming-study.tistory.com/28)에서 확인하실 수 있습니다.
   
   
4. 재해싱: 해시셋의 요소가 많아지면, 해시 테이블의 크기를 늘리고 요소들을 재배치하는 재해싱 작업을 수행하여 성능을 유지합니다. 재해싱은 새로운 배열을 생성하고 기존 요소들을 새로운 배열로 옮기며, 해시 코드를 다시 계산하여 새로운 인덱스를 할당합니다.

 

 

 

---

3. 주요 메서드

 

• Add(T item):
  해시셋에 요소를 추가합니다. 요소가 이미 존재하면 추가되지 않습니다. 새로운 요소의 해시 코드를 계산하고, 해당 해시 코드의 버킷에 요소를 추가합니다. 만약 이미 존재하는 요소라면 추가되지 않고 false를 반환합니다.

// 해시셋 생성 및 요소 추가
HashSet<int> numbers = new HashSet<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);

// 중복 요소 추가 시도
bool added = numbers.Add(2); // 이미 존재하므로 추가되지 않음
Console.WriteLine("Attempt to add 2 again: " + added);

 

• Remove(T item):
  해시셋에서 특정 요소를 제거합니다. 제거에 성공하면 true를 반환하고, 실패하면 false를 반환합니다. 제거할 요소의 해시 코드를 계산하여 해당 버킷을 찾아 요소를 제거합니다.

// 해시셋 생성 및 요소 추가
HashSet<int> numbers = new HashSet<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);

//요소 삭제
bool removed = numbers.Remove(2);
Console.WriteLine("After removing 2: " + string.Join(", ", numbers));

 

• Contains(T item):
  해시셋에 특정 요소가 포함되어 있는지 확인합니다. 요소의 해시 코드를 계산하여 해당 버킷을 검사합니다. 만약 버킷에 요소가 존재하면 true를 반환합니다.

// 해시셋 생성 및 요소 추가
HashSet<int> numbers = new HashSet<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);
        
// 요소 존재 여부 확인
bool contains = numbers.Contains(3);
Console.WriteLine("Contains 3: " + contains);

 

• Clear():
  해시셋의 모든 요소를 제거합니다. 내부 배열을 새로 생성하여 모든 요소를 제거합니다.

// 해시셋 생성 및 요소 추가
HashSet<int> numbers = new HashSet<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);

// 해시셋 초기화
numbers.Clear();
Console.WriteLine("After clearing: " + string.Join(", ", numbers));

 

• IsSubsetOf(IEnumerable<T> other):
  현재 해시셋에 지정된 컬렉션의 부분집합인지 확인합니다.
  즉 모든 요소가 다른 컬렉션에 포함되는지 검사합니다.

HashSet<int> set1 = new HashSet<int>() { 1, 2, 3, 4 };
HashSet<int> set2 = new HashSet<int>() { 2, 3 };
HashSet<int> set3 = new HashSet<int>() { 1, 2, 3, 4, 5 };

//set2가 set1의 부분 집합인지 확인
Console.WriteLine("set2 is subset of set1: " + set2.IsSubsetOf(set1));

 

• IsSupersetOf(IEnumerable<T> other):
  현재 해시셋이 지정된 컬렉션의 슈퍼셋인지 확인합니다.
  즉 다른 컬렉션의 모든 요소가 현재 해시셋에 포함되는지 검사합니다.

HashSet<int> set1 = new HashSet<int>() { 1, 2, 3, 4 };
HashSet<int> set2 = new HashSet<int>() { 2, 3 };
HashSet<int> set3 = new HashSet<int>() { 1, 2, 3, 4, 5 };

//set1의 요소가 set2에 모두 있는지 확인
Console.WriteLine("set1 is superset of set2: " + set1.IsSupersetOf(set2));

 

• Count:
  해시셋에 포함된 요소의 수를 반환하는 속성입니다.

// 해시셋 생성 및 요소 추가
HashSet<int> numbers = new HashSet<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);

//해시셋의 현재 요소의 갯수 확인
Console.WriteLine(numbers.Count);

 

 

 

 

---

4. 시간복잡도

 

• 추가(Add): 평균적으로 O(1), 최악의 경우 O(n). 해시 충돌이 적고 해시 테이블이 적절히 크기가 조정되면 평균적으로 O(1)의 시간복잡도를 유지합니다. 최악의 경우는 모든 요소가 동일한 해시 코드를 가지는 경우로, 이 경우 요소를 추가하는 데 O(n)의 시간이 소요됩니다.

 

• 삭제(Remove): 평균적으로 O(1), 최악의 경우 O(n). 마찬가지로 해시 충돌이 적고 해시 테이블이 적절히 크기가 조정되면 평균적으로 O(1)의 시간복잡도를 유지합니다.

 

• 탐색(Contains): 평균적으로 O(1), 최악의 경우 O(n). 해시 함수의 품질에 따라 평균적으로 O(1)의 시간복잡도를 유지합니다.

 

• 접근: N/A. 해시셋은 인덱스를 사용하여 특정 요소에 접근하는 기능이 없습니다. 해시셋은 집합 데이터 구조로, 특정 위치에 있는 요소를 가져오는 것이 아니라 요소의 존재 여부를 빠르게 확인하고 추가 및 삭제하는 데 최적화되어 있습니다. 따라서 인덱스를 통한 접근이 없기 때문에 시간복잡도를 정의할 수 없습니다.

 

평균적인 시간복잡도는 해시 함수의 품질과 충돌 해결 방식에 크게 의존합니다. 해시 함수가 고르게 분포되고 충돌이 적다면, 대부분의 작업이 O(1) 시간에 수행됩니다.

 

 

 

---

5. 핵심 정리

 

1. 해시셋은 해시 테이블을 기반으로 구현된 컬렉션 클래스로, 중복되지 않은 요소들을 효율적으로 관리합니다.
2. 해시 함수와 버킷을 사용하여 요소들을 저장하고, 체이닝을 통해 충돌을 해결합니다.
3. 주요 메서드로는 요소 추가, 삭제, 탐색 등이 있으며, 대부분의 작업이 평균적으로 O(1) 시간복잡도를 가집니다.
4. 재해싱을 통해 성능을 유지하며, 많은 요소가 추가되면 해시 테이블의 크기를 늘리고 요소들을 재배치합니다.
5. 해시셋은 대량의 데이터를 효율적으로 관리할 수 있으며, 특히 고유한 값들을 유지해야 하는 경우에 유용합니다.

 

 

 

---

6. 결론

 

해시셋은 중복 없는 데이터를 관리하고 빠르게 탐색, 추가 및 삭제하는 작업에 유용한 자료구조입니다. 해시 테이블의 효율적인 구조 덕분에 대부분의 작업이 평균적으로 상수 시간에 수행됩니다. 해시셋을 잘 활용하면 데이터 처리의 성능을 향상시킬 수 있습니다. 이를 이해하고 적절히 사용하는 것이 중요하며, 특히 대량의 데이터를 다루는 상황에서 해시셋의 이점을 최대한 활용할 수 있습니다.

 

 

 

---

지금까지 해시셋에 대해 알아보았습니다.

현재 글의 내용 중 틀린 부분이나, 지적하실 내용이 있으시다면 언제든지 알려주세요! 읽어주셔서 감사합니다.