[20260513] C# ( Hash 기반 자료구조의 주의점과 이를 해결하는 기법)

(1) 해시 기반 자료구조의 주의점

- HashTable, Dictionary, HashSet은 Key를 해시 함수에 넣어서 해시 코드를 만든다.

- 그리고 그 값을 이용해서 데이터를 저장할 위치를 계산하는 방식이다.

- 아래에서 예시로 보이는 HashTable은 C#의 HashTable 클래스를 의미하는 것이 아니라, 해시 기반 자료구조의 동작 원리를 설명하기 위한 일반적인 해시 테이블 구조를 말한다.

Key → Hash Function → Hash Code → 저장 위치

27 → 해시 함수 → 특정 위치 계산 → 해당 위치에 저장

- 이때, 문제가 발생할 수 있다. 아래와 같은 함수가 있다고 가정한다.

- 키 값을 10으로 나눈 나머지로 위치를 정하는 해시 함수다.

hash 함수 = Key % 10;

Key 27 = 27 % 10 = 7
Key 35 = 35 % 10 = 5
Key 42 = 42 % 10 = 2

- 이런 식으로 Key를 이용해 저장 위치를 계산한다.

- 이때, Key 값이 각각 27과 37로 들어간다고 해보자. 

Key 27 → 27 % 10 = 7
Key 37 → 37 % 10 = 7

- 이러면 서로 다른 Key가 같은 저장 위치를 가리키게 된다.

- 이런 상황을 해시 충돌(Hash Collision)이라고 한다.

---

(2) 해시 충돌이 발생하는 이유

- 모든 입력값에 대해 완전히 고유한 저장 위치를 만드는 것은 불가능하다.

- Key의 종류는 매우 많지만, 버킷 배열(공간)은 제한되어 있다.

※ 따라서 서로 다른 Key가 같은 위치를 가리키는 상황은 피할 수 없다.

---

(3) 해시 충돌을 해결 하는 2가지 방법

① 체이닝(Chaining)

(1) 정의

- 체이닝과 같은 위치에 여러 데이터가 들어오면, 그 위치에 데이터를 연결해서 저장하는 방식이다.
- 같은 버킷에 들어온 데이터를 연결 리스트처럼 이어서 관리하는 기법이다..

 

(2) 조회 방법

1. Key로 해시 값을 계산한다.
2. 해당 버킷 위치로 이동한다.
3. 그 안에 연결된 데이터를 하나씩 비교한다.
4. 같은 Key를 찾으면 Value를 반환한다.

 

(3) 정리 

- 체이닝은 충돌이 발생한 데이터를 같은 버킷 안에 연결해서 저장하는 방식이다.
- .NET의 Dictionary도 충돌 처리를 위해 체이닝과 유사한 방식을 사용하고 있다. 

---

② 개방 주소법(Open Addressing)

(1) 정의

- 개방 주소법은 충돌이 발생했을 때, 다른 빈 공간을 찾아 데이터를 저장하는 방식이다.

- 위처럼 충돌이 발생하면, 다른 빈 공간을 찾는 것이다.

- 즉, 충돌이 발생하면 해시 테이블 내부의 다른 위치를 탐색해서 저장하는 방식이다.

(2) 탐색 방법

① 선형 탐사(Linear Probing)
   - 위에서 보여준 다음 칸을 순서대로 확인하는 방법이다.
② 제곱 탐사(Quadratic Probing)
   - 일정 간격을 제곱 형태로 넓히며 확인한다.
③ 이중 해싱(Double Hashing)
   - 다른 해시 함수를 한 번 더 사용해서 다음 위치를 계산하는 기법이다.

 

(3) 정리

- 개방 주소법은 충돌이 발생했을 때 같은 버킷에 연결하지 않는다.
- 테이블 내부의 다른 빈 공간을 찾아 저장하는 방식이다.