hash table은 충돌, 적재율(load factor), 리사이징을 어떻게 처리하나요?

Question

Accepted Answer

서로 다른 두 key가 **같은 버킷**으로 해싱될 수 있는데, 이를 **충돌(collision)**이라 합니다. hash table은 충돌을 해결하고 버킷이 혼잡해지기 전에 **리사이징(resizing)**함으로써 평균 O(1)을 유지하며, 이는 **적재율(load factor)**로 제어됩니다.

## 충돌 해결

```text
분리 연결법(separate chaining): 각 버킷이 리스트를 가짐
  [3] -> ("cat",9) -> ("rat",2)   # 둘 다 3으로 해싱됨

개방 주소법(open addressing): 다음 빈 슬롯으로 탐사
  hash=3 점유됨 -> 4 시도 -> 5 시도 ... (선형 탐사)
```

## 적재율과 리사이징

```text
적재율 α = 항목 수 / 버킷 수
α 증가 -> 충돌 증가 -> 조회 느려짐
α가 임계값(예: 0.75)을 초과하면:
  -> 더 큰 array를 할당(보통 2배)
  -> 기존 모든 key를 새 버킷으로 REHASH
```

```python
# 개념적 리사이즈
def _resize(self):
    old = self.buckets
    self.buckets = [None] * (len(old) * 2)
    for entry in all_entries(old):
        self._insert(entry.key, entry.value)   # 새 array로 rehash
```

## 복잡도

| 연산 | 평균 | 최악 |
|---|---|---|
| 조회 / 삽입 / 삭제 | O(1) | O(n) |
| 단일 리사이즈 | — | O(n) |
| 삽입(리사이징 포함, amortized) | O(1) | — |

리사이즈는 O(n)이지만 드물게 일어나므로 삽입당 **O(1)로 amortize됩니다**.

## 트레이드오프

- **연결법(chaining):** 단순하고 우아하게 성능이 저하되지만, 추가 포인터를 사용하고 캐시 지역성이 나쁨.
- **개방 주소법:** 캐시 친화적이고 컴팩트하지만, 높은 적재율에 민감하며 삭제 시 주의(tombstone)가 필요함.

## 왜 중요한가

이러한 내부 동작은 hash map이 *왜* 평균적으로 빠르면서도 O(n)으로 치솟을 수 있는지를 설명합니다. 성능에 민감한 코드와 적대적 입력(hash-flooding) 방어에 중요합니다.

적재율을 이해하면 실제 라이브러리가 노출하는 메모리/속도 튜닝 노브도 이해할 수 있습니다.

연산	평균	최악
조회 / 삽입 / 삭제	O(1)	O(n)
단일 리사이즈	—	O(n)
삽입(리사이징 포함, amortized)	O(1)	—