ChainingHashTable 구현 정리
ChainingHashTable 구현
1. 학습 목표
SimpleHashTable은 충돌이 발생하면 예외를 던지지만, ChainingHashTable은 같은 버킷에 들어온 키를 연결 리스트(Chain)에 저장하여 충돌을 해결한다.
이번 구현에서는 버킷별 연결 리스트를 사용하여 키와 값을 저장하고, 탐색·삽입·삭제·리사이징 기능을 구현한다.
2. SimpleHashTable과 달라진 점
| 항목 | SimpleHashTable | ChainingHashTable |
|---|---|---|
| 저장 공간 | table[] + occupied[] | LinkedList<KeyValuePair<TKey, TValue>>[] buckets |
| 빈 슬롯 | occupied로 구분 | 버킷이 null |
| 충돌 | 예외 발생 | 같은 버킷의 연결 리스트에 추가 |
| 탐색 | 슬롯 하나 확인 | 버킷의 체인 순회 |
| 삭제 | 슬롯 비우기 | 연결 리스트 노드 제거 |
| 중복 검사 | 해당 슬롯 확인 | ContainsKey()로 체인 전체 확인 |
| Resize | 새 배열로 직접 이동 | count = 0 후 Add()로 재삽입 |
3. 전체 구현 코드
파일 경로: Assets/Scripts/HashTable/ChainingHashTable.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
// 충돌 해결 = 버킷별 LinkedList 체인
public class ChainingHashTable<TKey, TValue> : IDictionary<TKey, TValue>
{
private const int DefaultCapacity = 16;
private const double LoadFactor = 0.75;
private LinkedList<KeyValuePair<TKey, TValue>>[] buckets;
private int size;
private int count;
public ChainingHashTable()
{
buckets = new LinkedList<KeyValuePair<TKey, TValue>>[DefaultCapacity];
size = DefaultCapacity;
count = 0;
}
private int GetHash(TKey key)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
int hash = key.GetHashCode();
// 부호 비트만 제거해 항상 0 이상.
// Math.Abs는 int.MinValue에서 음수를 그대로 돌려주므로 쓰지 않는다.
return (hash & 0x7fffffff) % size;
}
public TValue this[TKey key]
{
get
{
if (TryGetValue(key, out TValue value))
{
return value;
}
throw new KeyNotFoundException();
}
set
{
if (key == null)
throw new ArgumentNullException(nameof(key));
if ((double)count / size > LoadFactor)
{
Resize();
}
int index = GetHash(key);
// ⑤ 기존 키가 있으면 값을 갱신하고, 없으면 새로 추가한다.
if (buckets[index] == null)
{
buckets[index] = new LinkedList<KeyValuePair<TKey, TValue>>();
}
LinkedListNode<KeyValuePair<TKey, TValue>> node = buckets[index].First;
while (node != null)
{
if (EqualityComparer<TKey>.Default.Equals(node.Value.Key, key))
{
node.Value = new KeyValuePair<TKey, TValue>(key, value);
return;
}
node = node.Next;
}
buckets[index].AddLast(new KeyValuePair<TKey, TValue>(key, value));
count++;
}
}
public ICollection<TKey> Keys
{
get
{
var keys = new List<TKey>();
for (int i = 0; i < size; i++)
{
if (buckets[i] != null)
{
foreach (var kvp in buckets[i])
{
keys.Add(kvp.Key);
}
}
}
return keys;
}
}
public ICollection<TValue> Values
{
get
{
var values = new List<TValue>();
for (int i = 0; i < size; i++)
{
if (buckets[i] != null)
{
foreach (var kvp in buckets[i])
{
values.Add(kvp.Value);
}
}
}
return values;
}
}
public int Count => count;
public int Capacity => size;
public bool IsReadOnly => false;
private void Resize()
{
var oldBuckets = buckets;
var oldSize = size;
size *= 2;
buckets = new LinkedList<KeyValuePair<TKey, TValue>>[size];
// ④ 기존 원소를 새 배열에 다시 삽입한다.
count = 0;
for (int i = 0; i < oldSize; i++)
{
if (oldBuckets[i] != null)
{
foreach (var kvp in oldBuckets[i])
{
Add(kvp.Key, kvp.Value);
}
}
}
}
public void Add(TKey key, TValue value)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
if (ContainsKey(key))
throw new ArgumentException("키 중복");
if ((double)count / size > LoadFactor)
{
Resize();
}
int index = GetHash(key);
// ① 버킷이 없으면 생성하고 체인 끝에 추가한다.
if (buckets[index] == null)
{
buckets[index] = new LinkedList<KeyValuePair<TKey, TValue>>();
}
buckets[index].AddLast(new KeyValuePair<TKey, TValue>(key, value));
count++;
}
public void Add(KeyValuePair<TKey, TValue> item)
{
Add(item.Key, item.Value);
}
public void Clear()
{
buckets = new LinkedList<KeyValuePair<TKey, TValue>>[size];
count = 0;
}
public bool Contains(KeyValuePair<TKey, TValue> item)
{
int index = GetHash(item.Key);
if (buckets[index] == null)
return false;
foreach (var kvp in buckets[index])
{
if (EqualityComparer<TKey>.Default.Equals(kvp.Key, item.Key)
&& EqualityComparer<TValue>.Default.Equals(kvp.Value, item.Value))
{
return true;
}
}
return false;
}
public bool ContainsKey(TKey key)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
int index = GetHash(key);
if (buckets[index] == null)
return false;
foreach (var kvp in buckets[index])
{
if (EqualityComparer<TKey>.Default.Equals(kvp.Key, key))
{
return true;
}
}
return false;
}
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
if (array == null)
throw new ArgumentNullException(nameof(array));
if (arrayIndex < 0)
throw new ArgumentOutOfRangeException(nameof(arrayIndex));
if (array.Length - arrayIndex < count)
throw new ArgumentException("배열 크기 부족");
int index = arrayIndex;
foreach (var kvp in this)
{
array[index++] = kvp;
}
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
for (int i = 0; i < size; i++)
{
if (buckets[i] != null)
{
foreach (var kvp in buckets[i])
{
yield return kvp;
}
}
}
}
public bool Remove(TKey key)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
int index = GetHash(key);
// ③ 체인에서 키가 일치하는 노드를 찾아 삭제한다.
if (buckets[index] == null)
{
return false;
}
LinkedListNode<KeyValuePair<TKey, TValue>> node = buckets[index].First;
while (node != null)
{
if (EqualityComparer<TKey>.Default.Equals(node.Value.Key, key))
{
buckets[index].Remove(node);
count--;
return true;
}
node = node.Next;
}
return false;
}
public bool Remove(KeyValuePair<TKey, TValue> item)
{
// ③ 키와 값이 모두 일치하는 노드를 삭제한다.
int index = GetHash(item.Key);
if (buckets[index] == null)
{
return false;
}
LinkedListNode<KeyValuePair<TKey, TValue>> node = buckets[index].First;
while (node != null)
{
if (EqualityComparer<TKey>.Default.Equals(node.Value.Key, item.Key)
&& EqualityComparer<TValue>.Default.Equals(node.Value.Value, item.Value))
{
buckets[index].Remove(node);
count--;
return true;
}
node = node.Next;
}
return false;
}
public bool TryGetValue(TKey key, out TValue value)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
int index = GetHash(key);
// ② 버킷의 체인을 순회하여 키를 찾는다.
if (buckets[index] != null)
{
foreach (var kvp in buckets[index])
{
if (EqualityComparer<TKey>.Default.Equals(kvp.Key, key))
{
value = kvp.Value;
return true;
}
}
}
value = default;
return false;
}
public IEnumerable<BucketView> GetBucketViews()
{
for (int i = 0; i < size; i++)
{
if (buckets[i] == null || buckets[i].Count == 0)
{
yield return new BucketView(i, BucketState.Empty, null, null, null);
continue;
}
// ⑥ 체인의 키와 값을 문자열 튜플 리스트로 변환한다.
var chain = new List<(string Key, string Value)>();
foreach (var kvp in buckets[i])
{
chain.Add((
kvp.Key?.ToString() ?? "null",
kvp.Value?.ToString() ?? "null"
));
}
yield return new BucketView(i, BucketState.Occupied, null, null, chain);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
4. 빈칸별 구현 정리
| 빈칸 | 구현 위치 | 핵심 동작 |
|---|---|---|
| ① | Add() | 버킷 생성 → AddLast() → count++ |
| ② | TryGetValue() | 체인 순회 → 키 비교 → 값 반환 |
| ③ | Remove() 2개 | 노드 순회 → 조건 확인 → 노드 삭제 → count-- |
| ④ | Resize() | count = 0 → 기존 원소를 Add()로 재삽입 |
| ⑤ | 인덱서 set | 기존 키 갱신 또는 새로운 키 추가 |
| ⑥ | GetBucketViews() | 키와 값을 문자열 튜플 리스트로 변환 |
5. 핵심 구현 원리
5.1 버킷과 체인
buckets는 연결 리스트를 저장하는 배열이다.
private LinkedList<KeyValuePair<TKey, TValue>>[] buckets;
배열의 각 칸은 하나의 버킷이며, 충돌한 키들은 해당 버킷의 연결 리스트에 저장된다.
버킷이 비어 있다면 null이고, 데이터가 들어오면 연결 리스트를 생성한다.
if (buckets[index] == null)
{
buckets[index] = new LinkedList<KeyValuePair<TKey, TValue>>();
}
5.2 Add와 인덱서의 차이
Add()는 기존 키가 존재하면 중복 키 예외를 발생시킨다.
인덱서 set은 기존 키가 존재하면 값을 갱신하고, 없으면 새로운 키를 추가한다.
| 기능 | Add | 인덱서 set |
|---|---|---|
| 기존 키 | 예외 | 값 갱신 |
| 신규 키 | 추가 | 추가 |
| count 증가 | 신규 추가 시 | 신규 추가 시 |
| 기존 키 갱신 시 count | 해당 없음 | 증가하지 않음 |
5.3 LinkedListNode를 이용한 삭제
연결 리스트를 foreach로 순회하면서 원소를 삭제하면 컬렉션 변경 문제가 발생할 수 있다.
따라서 LinkedListNode를 이용하여 직접 노드를 이동한다.
LinkedListNode<KeyValuePair<TKey, TValue>> node = buckets[index].First;
while (node != null)
{
if (node.Value.Key.Equals(key))
{
buckets[index].Remove(node);
count--;
return true;
}
node = node.Next;
}
node.Next를 이용해 다음 노드로 이동하며, 삭제 대상 노드를 찾으면 Remove(node)로 제거한다.
5.4 Resize와 재해싱
배열 크기가 바뀌면 해시 인덱스도 달라질 수 있으므로 기존 데이터를 새 배열에 다시 저장해야 한다.
count = 0;
foreach (var kvp in oldBuckets)
{
Add(kvp.Key, kvp.Value);
}
Add()를 이용해 재삽입하면 새로운 배열 크기를 기준으로 해시 인덱스를 계산하고, 충돌이 발생하면 체인에 추가한다.
6. 검증 코드
private void TestChainingHashTable()
{
Debug.Log("=== Chaining Hash Table Test ===");
var hashTable = new ChainingHashTable<string, int>();
hashTable.Add("하나", 1);
hashTable.Add("둘", 2);
hashTable.Add("셋", 3);
foreach (var kvp in hashTable)
{
Debug.Log($"[{kvp.Key}, {kvp.Value}]");
}
Expect(hashTable.Count, 3, "Count");
Expect(hashTable["둘"], 2, "값 둘");
Expect(hashTable.ContainsKey("하나"), true, "탐색 하나");
Expect(hashTable.Remove("하나"), true, "삭제 하나");
Expect(hashTable.ContainsKey("하나"), false, "탐색 하나 (삭제 후)");
Expect(hashTable.Count, 2, "Count (삭제 후)");
Debug.Log("충돌 · 중복 키 · 리사이즈:");
var collision = new ChainingHashTable<int, int>();
collision.Add(1, 10);
collision.Add(17, 170); // 1과 17은 % 16이 같아 같은 버킷에 들어간다
Expect(collision[17], 170, "충돌한 키 17의 값");
Expect(collision.Remove(1), true, "같은 버킷의 키 1 삭제");
Expect(collision.ContainsKey(17), true, "삭제 후 키 17 탐색");
ExpectThrows<ArgumentException>(() => collision.Add(17, 0), "중복 키 Add");
for (int key = 100; key < 120; ++key)
{
collision.Add(key, key);
}
Expect(collision.Capacity > 16, true, $"리사이즈 발생 (Capacity {collision.Capacity})");
Expect(collision.Count, 21, "리사이즈 후 Count");
Expect(collision[17], 170, "리사이즈 후 키 17의 값");
Debug.Log("인덱서 set:");
collision[17] = 171;
Expect(collision[17], 171, "인덱서로 기존 키 값 갱신");
Expect(collision.Count, 21, "갱신 후 Count");
collision[49] = 490;
Expect(collision[49], 490, "인덱서로 새 키 추가");
Expect(collision.Count, 22, "추가 후 Count");
}
7. 주의사항
Add()는 중복 키를 허용하지 않는다.- 인덱서
set은 기존 키를 갱신할 수 있다. - 기존 키를 갱신할 때
count를 증가시키면 안 된다. Remove()는 삭제 성공 시에만count를 감소시킨다.Remove(KeyValuePair)는 키와 값이 모두 일치해야 삭제한다.- 충돌한 키들은 동일한 버킷의 연결 리스트에서 관리한다.
- 리사이징 시 기존 원소를 재해싱해야 한다.
LinkedListNode를 이용하면 삭제할 노드를 직접 관리할 수 있다.
8. 시간 복잡도
| 연산 | 평균 | 최악 |
|---|---|---|
| 탐색 | O(1 + α) | O(n) |
| 삽입 | O(1 + α) | O(n) |
| 삭제 | O(1 + α) | O(n) |
| 순회 | O(size) | O(size) |
α는 로드팩터이며, 평균 체인 길이를 나타내는 지표로 사용한다.
충돌이 적고 로드팩터를 적절히 유지하면 평균적으로 O(1)에 가까운 성능을 제공한다.
9. 최종 정리
ChainingHashTable은 해시 충돌을 예외로 처리하는 SimpleHashTable과 달리, 동일한 버킷에 들어온 원소를 연결 리스트에 저장하여 충돌을 해결한다.
각 버킷은 필요할 때만 연결 리스트를 생성하며, 탐색·삽입·삭제 과정에서 해당 버킷의 체인을 순회한다.
핵심은 해시 인덱스 계산은 동일하지만, 충돌이 발생했을 때 하나의 슬롯만 사용하는 것이 아니라 연결 리스트를 이용해 여러 원소를 관리한다는 점이다.



