해시 테이블 (Hash Table) 정리
해시 테이블 (Hash Table)
1. 해시 테이블이 필요한 이유
해시 테이블은 키(Key)를 이용해 값(Value)을 빠르게 조회하기 위한 자료구조이다.
이름과 전화번호처럼 특정 키를 이용해 원하는 값을 찾아야 하는 상황에서 활용한다. 배열이나 트리처럼 데이터를 순회하거나 비교하는 과정 대신, 해시 함수를 이용해 저장 위치를 계산한다.
자료구조별 비교
| 자료구조 | 탐색 | 삽입 | 정렬 상태 유지 |
|---|---|---|---|
| 배열 (정렬 안 됨) | O(n) | O(1) | 없음 |
| 배열 (정렬됨) | O(log n) | O(n) | 있음 |
| 이진 탐색 트리 | O(log n) 평균 | O(log n) 평균 | 있음 |
| 해시 테이블 | O(1) 평균 | O(1) 평균 | 없음 |
해시 테이블은 평균적으로 O(1)의 탐색과 삽입 성능을 제공한다.
다만 데이터를 정렬된 상태로 유지하지 않기 때문에, 순서가 필요하지 않고 키를 이용한 빠른 조회가 중요한 상황에 적합하다.
2. 해시 테이블의 핵심 원리
해시 테이블은 해시 함수(Hash Function)를 이용해 키를 배열의 인덱스로 변환한다.
동작 과정
- 키를 입력한다.
- 해시 함수를 이용해 정수 해시값을 생성한다.
- 해시값을 배열 크기에 맞게 변환한다.
- 계산된 인덱스에 키와 값을 저장한다.
해시값과 인덱스
C#의 GetHashCode()는 객체의 해시값을 정수로 반환한다.
하지만 해시값은 배열 인덱스로 바로 사용할 수 없기 때문에, 배열 크기를 이용해 실제 저장 위치를 계산한다.
int hash = key.GetHashCode();
int index = (hash & 0x7fffffff) % size;
GetHashCode(): 키를 정수 해시값으로 변환한다.& 0x7fffffff: 부호 비트를 제거해 음수가 아닌 값으로 만든다.% size: 배열 크기로 나눈 나머지를 구해 인덱스 범위에 맞춘다.
Math.Abs()는 int.MinValue에서 양수로 변환할 수 없기 때문에 이 방식에서는 사용하지 않는다.
저장과 조회
저장
키를 해싱해 인덱스를 계산하고, 해당 위치에 키와 값을 저장한다.
조회
같은 키로 해시값과 인덱스를 계산한 뒤 해당 위치에서 키를 확인한다.
해시 테이블은 키를 이용해 저장 위치를 빠르게 찾지만, 계산된 위치에 다른 키가 이미 존재할 수 있다. 이 문제를 충돌이라고 한다.
3. 충돌 (Collision)
충돌은 서로 다른 키가 동일한 배열 인덱스로 변환되는 현상이다.
"하나" → 인덱스 3
"셋" → 인덱스 3
서로 다른 키가 같은 슬롯을 사용하려고 하기 때문에 충돌이 발생한다.
충돌이 발생하는 이유
가능한 키의 수는 매우 많지만, 배열의 크기는 유한하다.
따라서 서로 다른 키들이 동일한 인덱스로 변환되는 상황은 피할 수 없다. 이는 비둘기집 원리에 의해 설명할 수 있다.
저장할 수 있는 키의 종류가 슬롯 수보다 많다면, 적어도 두 개 이상의 키가 동일한 슬롯에 배정된다.
생일 역설
생일 역설은 해시 충돌이 생각보다 빠르게 발생할 수 있다는 것을 이해하는 데 도움이 된다.
23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘는다. 해시 테이블에서도 충돌은 예상보다 빠르게 발생할 수 있으므로 반드시 충돌 처리 방법이 필요하다.
충돌 처리 전략
| 전략 | 핵심 아이디어 | 구현 클래스 |
|---|---|---|
| 충돌 시 예외 | 충돌 발생 시 예외를 던짐 | SimpleHashTable |
| 체이닝 | 같은 슬롯에 연결 리스트로 저장 | ChainingHashTable |
| 오픈 어드레싱 | 충돌 시 다른 슬롯을 탐색 | OpenAddressingHashTable |
4. 로드팩터 (Load Factor)와 리사이징
로드팩터는 해시 테이블의 슬롯이 얼마나 사용되고 있는지를 나타내는 값이다.
로드팩터 계산
[ \alpha = \frac{count}{size} ]
count: 현재 저장된 원소 수size: 배열의 크기
로드팩터가 높아질수록 충돌이 발생할 가능성이 높아지고, 충돌 처리 과정에서 탐색해야 하는 범위도 증가한다.
프로젝트별 로드팩터 임계값
| 구현 | 임계값 |
|---|---|
SimpleHashTable | 0.75 |
ChainingHashTable | 0.75 |
OpenAddressingHashTable | 0.6 |
프로젝트에서는 다음 조건으로 리사이징 여부를 판단한다.
if ((double)count / size > LoadFactor)
{
Resize();
}
로드팩터가 임계값을 초과하면 배열 크기를 2배로 늘린다.
오픈 어드레싱은 충돌 시 빈 슬롯을 찾아 계속 이동해야 하므로, 체이닝보다 낮은 로드팩터를 기준으로 관리한다.
리사이징 (Resizing)
리사이징은 해시 테이블의 배열 크기를 늘리는 작업이다.
- 기존 배열 크기를 2배로 늘린다.
- 새로운 배열을 생성한다.
- 기존에 저장된 모든 원소를 가져온다.
- 새로운 배열 크기를 기준으로 해시 인덱스를 다시 계산한다.
- 계산된 위치에 원소를 재배치한다.
재해싱이 필요한 이유
기존 배열 크기가 16일 때와 크기가 32일 때는 해시값을 나눈 나머지가 달라질 수 있다.
따라서 기존 배열을 단순히 복사하면 원소가 잘못된 인덱스에 저장될 수 있다.
배열 크기가 변경되면 기존 원소들을 새로운 크기에 맞춰 다시 해싱하고 저장해야 한다. 이를 재해싱(Rehashing)이라고 한다.
5. 체이닝 (Chaining)
체이닝은 충돌이 발생하면 동일한 인덱스에 연결 리스트를 연결하여 원소들을 저장하는 방식이다.
각 배열 슬롯은 연결 리스트의 시작점을 가리키고, 같은 인덱스로 계산된 원소들은 해당 리스트에 연결된다.
구조
동작 방식
삽입
- 키를 해싱해 인덱스를 계산한다.
- 해당 슬롯의 연결 리스트를 확인한다.
- 충돌이 발생하면 연결 리스트에 원소를 추가한다.
탐색
- 키를 해싱해 인덱스를 계산한다.
- 해당 인덱스의 연결 리스트를 순회한다.
- 키가 일치하는 원소를 찾으면 값을 반환한다.
삭제
- 키를 해싱해 인덱스를 계산한다.
- 해당 연결 리스트에서 키가 일치하는 노드를 찾는다.
- 노드를 연결 리스트에서 제거한다.
장점
- 로드팩터가 1을 초과해도 동작할 수 있다.
- 충돌 처리가 직관적이다.
- 삭제가 간단하다.
- 연결 리스트를 이용해 같은 인덱스에 여러 원소를 저장할 수 있다.
단점
- 연결 리스트를 순회해야 한다.
- 노드 간 참조를 따라가는 포인터 추적이 발생한다.
- 노드마다 추가적인 메모리가 필요하다.
- 배열에 비해 캐시 지역성이 좋지 않을 수 있다.
시간 복잡도
| 연산 | 평균 시간 복잡도 |
|---|---|
| 탐색 | O(1 + α) |
| 삽입 | O(1 + α) |
| 삭제 | O(1 + α) |
α는 로드팩터이며, 평균 체인의 길이를 나타내는 지표로 사용한다.
로드팩터를 일정 수준 이하로 유지하면 평균적으로 O(1)에 가까운 성능을 유지할 수 있다.
6. 오픈 어드레싱 (Open Addressing)
오픈 어드레싱은 연결 리스트를 사용하지 않고 배열 내부에서 충돌을 해결하는 방식이다.
충돌이 발생하면 다른 인덱스를 탐색하여 빈 슬롯을 찾는다.
이때 다음 슬롯을 찾는 방법을 프로빙( Probing )이라고 한다.
동작 방식
- 키를 해싱해 첫 번째 인덱스를 계산한다.
- 해당 인덱스가 비어 있으면 저장한다.
- 이미 다른 원소가 존재하면 다음 인덱스를 계산한다.
- 빈 슬롯을 찾을 때까지 반복한다.
프로빙 전략
| 전략 | 수식 | 특징 |
|---|---|---|
| 선형 프로빙 (Linear Probing) | (h + i) % size | 구현이 간단하지만 1차 클러스터링 발생 |
| 이차 프로빙 (Quadratic Probing) | (h + i²) % size | 1차 클러스터링을 완화하지만 2차 클러스터링 발생 가능 |
| 이중 해싱 (Double Hashing) | (h1 + i · h2) % size | 키마다 탐색 간격이 달라져 클러스터링 완화 |
h: 첫 번째 해시값h1: 첫 번째 해시 함수h2: 두 번째 해시 함수i: 프로빙 시도 횟수
선형 프로빙
충돌이 발생하면 다음 슬롯을 순차적으로 확인한다.
h
h + 1
h + 2
h + 3
...
구현이 단순하지만 연속된 슬롯들이 점점 하나의 덩어리로 형성되는 문제가 있다.
이차 프로빙
충돌이 발생할 때마다 이동 거리를 제곱하여 탐색한다.
h
h + 1²
h + 2²
h + 3²
...
선형 프로빙의 연속적인 탐색을 완화하지만, 서로 다른 키들이 동일한 탐색 경로를 공유하는 2차 클러스터링이 발생할 수 있다.
이중 해싱
두 개의 해시 함수를 사용하여 탐색 위치와 이동 간격을 결정한다.
h1 + 1 × h2
h1 + 2 × h2
h1 + 3 × h2
...
키마다 탐색 간격이 달라질 수 있기 때문에 클러스터링을 더욱 줄이는 데 도움이 된다.
7. 클러스터링 (Clustering)
클러스터링은 오픈 어드레싱에서 여러 슬롯이 연속적으로 차 있는 덩어리가 형성되는 현상이다.
1차 클러스터링
선형 프로빙에서 발생하는 대표적인 문제이다.
연속된 슬롯이 차 있으면 새로운 키가 해당 구간을 건너뛰어 빈 슬롯을 찾게 된다.
이 과정에서 기존 클러스터에 새로운 원소가 추가되고, 클러스터가 점점 커지는 눈덩이 효과가 발생한다.
클러스터링의 영향
- 탐색해야 하는 슬롯 수가 증가한다.
- 삽입 시 빈 슬롯을 찾는 시간이 길어진다.
- 삭제 후에도 탐색 경로가 길게 유지될 수 있다.
- 로드팩터가 높아질수록 성능이 급격히 나빠진다.
이차 프로빙과 이중 해싱은 탐색 경로를 다양화하여 클러스터링을 완화한다.
8. 오픈 어드레싱의 삭제 문제와 Tombstone
오픈 어드레싱에서는 원소를 단순히 삭제하고 슬롯을 비워 버리면 문제가 발생한다.
문제 상황
인덱스 3 : A
인덱스 4 : B
인덱스 5 : C
A, B, C가 충돌로 인해 연속된 슬롯에 저장되어 있다고 가정한다.
B를 삭제하고 인덱스 4를 완전히 비워 버리면, C를 탐색할 때 인덱스 4에서 빈 슬롯을 발견하고 탐색을 종료할 수 있다.
그러면 C가 인덱스 5에 존재함에도 찾지 못하게 된다.
해결 방법 : Tombstone
Tombstone은 실제 원소는 삭제했지만, 탐색 경로는 유지하기 위한 논리적 삭제 표시이다.
deleted[index] = true;
슬롯을 완전히 비우지 않고 삭제되었다는 표시를 남긴다.
슬롯 상태
| 상태 | 의미 |
|---|---|
occupied = false | 사용하지 않는 슬롯 |
occupied = true, deleted = false | 정상적으로 사용 중인 슬롯 |
occupied = true, deleted = true | 삭제된 슬롯 (Tombstone) |
탐색 중 Tombstone을 만나면 탐색을 종료하지 않고 다음 슬롯을 계속 확인한다.
삽입 시에는 Tombstone 슬롯을 재사용할 수 있다.
Tombstone의 주의점
삭제가 반복되면 실제 원소는 적어도 Tombstone이 많이 남을 수 있다.
따라서 실제 원소 수만 기준으로 로드팩터를 계산하면 테이블이 얼마나 많이 탐색해야 하는지 정확히 반영하지 못할 수 있다.
Tombstone이 많아지면 리사이징이나 재해싱을 통해 탐색 경로를 정리할 필요가 있다.
9. 오픈 어드레싱의 장점과 단점
장점
- 연결 리스트를 사용하지 않는다.
- 배열만 사용하므로 메모리 구조가 단순하다.
- 캐시 지역성이 좋다.
- 노드 객체 생성에 따른 추가 메모리 오버헤드가 적다.
단점
- 로드팩터가 높아지면 성능이 급격히 나빠질 수 있다.
- 충돌이 발생하면 빈 슬롯을 찾기 위해 계속 탐색해야 한다.
- 삭제 처리가 복잡하다.
- Tombstone 관리가 필요하다.
- 일반적으로 로드팩터를 0.7 이하로 낮게 유지하는 것이 유리하다.
10. 시간 복잡도
| 연산 | 평균 | 최악 |
|---|---|---|
탐색 (TryGetValue) | O(1) | O(n) |
삽입 (Add) | O(1) | O(n) |
삭제 (Remove) | O(1) | O(n) |
순회 (foreach) | O(size) | O(size) |
최악의 경우 O(n)이 되는 이유
모든 키가 동일한 슬롯으로 해싱되거나 해시 함수의 성능이 좋지 않으면 충돌이 계속 발생한다.
체이닝
동일한 슬롯의 연결 리스트가 길어지면서 탐색해야 하는 노드 수가 증가한다.
오픈 어드레싱
충돌이 반복되면 빈 슬롯을 찾기 위해 여러 슬롯을 확인해야 한다.
따라서 평균적으로 O(1)의 성능을 제공하지만 최악의 경우 O(n)이 될 수 있다.
11. 프로젝트의 실제 구현
프로젝트에서는 세 가지 해시 테이블 구현 모두 IDictionary<TKey, TValue>를 구현한다.
public class SimpleHashTable<TKey, TValue>
: IDictionary<TKey, TValue>
{
}
public class ChainingHashTable<TKey, TValue>
: IDictionary<TKey, TValue>
{
}
public class OpenAddressingHashTable<TKey, TValue>
: IDictionary<TKey, TValue>
{
}
IDictionary<TKey, TValue>를 구현하므로 Dictionary와 비슷한 방식으로 키와 값을 관리할 수 있다.
오픈 어드레싱의 프로빙 전략
public enum ProbingStrategy
{
Linear,
Quadratic,
DoubleHash
}
생성자에서 사용할 프로빙 전략을 선택한다.
var ht = new OpenAddressingHashTable<string, int>(
ProbingStrategy.DoubleHash
);
공통 API
세 구현은 공통적으로 다음 멤버를 제공한다.
| 멤버 | 역할 |
|---|---|
GetHash(TKey key) | 키의 해시값을 인덱스로 변환 |
Capacity | 내부 배열의 크기를 반환 |
GetHash()는 Simple과 Chaining에서는 private, OpenAddressing에서는 public으로 제공한다.
Capacity는 현재 해시 테이블의 배열 크기를 확인할 수 있는 프로퍼티이다.
OpenAddressingHashTable 추가 API
| 멤버 | 역할 |
|---|---|
GetSecondaryHash(key) | 이중 해싱에 사용할 두 번째 해시값 계산 |
GetProbeIndex(key, attempt) | 프로빙 전략에 따른 탐색 인덱스 계산 |
12. 세 가지 구현 비교
| 항목 | Simple | Chaining | OpenAddressing |
|---|---|---|---|
| 충돌 처리 | 예외 발생 | 연결 리스트 | 프로빙 |
| 기본 용량 | 16 | 16 | 16 |
| 로드팩터 | 0.75 | 0.75 | 0.6 |
| 리사이징 | 있음 | 있음 | 있음 |
| 삭제 처리 | occupied 해제 | 노드 제거 | deleted 표시 |
| 추가 배열 | occupied[] | 없음 | occupied[], deleted[] |
| 저장 구조 | 배열 | 배열 + 연결 리스트 | 배열 |
| 특징 | 충돌을 허용하지 않음 | 충돌을 연결 리스트로 해결 | 배열 내부에서 충돌 해결 |
SimpleHashTable
충돌이 발생하면 예외를 발생시키는 가장 단순한 방식이다.
리사이징을 통해 충돌 가능성을 낮출 수 있지만, 배열 크기를 늘리는 것만으로 모든 충돌을 해결할 수는 없다.
ChainingHashTable
충돌이 발생한 원소를 연결 리스트에 저장한다.
충돌 처리와 삭제가 비교적 단순하지만, 연결 리스트 탐색과 노드 메모리 오버헤드가 발생한다.
OpenAddressingHashTable
충돌이 발생하면 프로빙을 이용해 다른 슬롯을 탐색한다.
배열만 사용하므로 메모리 구조와 캐시 지역성이 유리하지만, 프로빙과 Tombstone 관리가 필요하다.
13. 전체 구조 정리
해시 테이블은 해시 함수를 이용해 키를 배열 인덱스로 변환하여 빠른 조회를 제공하는 자료구조이다.
해시값을 배열 크기에 맞춰 인덱스를 계산하고, 해당 위치에 키와 값을 저장한다.
하지만 서로 다른 키가 동일한 인덱스를 사용할 수 있으므로 충돌 처리가 필요하다.
프로젝트에서는 세 가지 방식으로 충돌을 처리한다.
SimpleHashTable: 충돌 발생 시 예외를 던진다.ChainingHashTable: 연결 리스트를 이용해 충돌한 원소를 저장한다.OpenAddressingHashTable: 프로빙을 이용해 다른 빈 슬롯을 찾는다.
또한 로드팩터를 관리하고 리사이징 및 재해싱을 수행하여 충돌 가능성과 탐색 비용을 줄인다.
해시 테이블은 정렬이 필요하지 않고 키를 이용한 빠른 조회가 중요한 상황에 적합하며, 평균적으로 O(1)의 탐색·삽입·삭제 성능을 제공한다.



