hash table이란 무엇이며, 어떻게 O(1) 조회를 달성하나요?

Question

Accepted Answer

**hash table(해시 테이블, hash map)**은 **key → value** 쌍을 저장하며 **평균 O(1)**의 삽입, 조회, 삭제를 제공합니다. 각 key를 **해시 함수(hash function)**에 통과시켜 내부 array의 인덱스("버킷(bucket)")로 매핑하는 방식으로 동작합니다.

## 동작 방식

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## 예시

```python
phone = {}
phone['alice'] = 555_1234   # 삽입 -> 'alice'를 버킷으로 해싱
num = phone['alice']        # 조회 -> 다시 해싱하여 버킷으로 점프
del phone['alice']          # 삭제
'bob' in phone              # 멤버십 -> 평균 O(1)
```

## 복잡도

| 연산 | 평균 | 최악 |
|---|---|---|
| 삽입 | O(1) | O(n) |
| 조회 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |

**최악의 경우** O(n)은 많은 key가 같은 버킷으로 충돌할 때 발생합니다.

## 트레이드오프

- **강점:** key 기반 접근이 극도로 빠름; 유연한 key.
- **약점:** key의 순서가 없음; 추가 메모리; O(n) 최악의 경우; 좋은 해시 함수가 필요함.

## 왜 중요한가

hash table은 실무에서 가장 많이 쓰이는 구조라 할 수 있습니다. 딕셔너리, 집합, 캐시, 데이터베이스 인덱스, 중복 제거의 뒤에 있습니다.

선형 스캔을 hash 조회로 바꾸는 것은 O(n²) 알고리즘을 O(n)으로 바꾸는 가장 흔한 방법 중 하나입니다.