# 해시 테이블

해시 테이블은 키와 값을 매핑하는 자료 구조다. 해시 함수로 키를 인덱스로
변환해 평균 상수 시간에 조회·삽입·삭제한다.

## 해시 충돌

두 개 이상의 서로 다른 키가 같은 인덱스로 매핑될 때 해시 충돌이 발생한다.
해시 충돌은 잘 설계된 해시 함수에서도 피할 수 없으며, 적재율이 올라갈수록
충돌 빈도가 증가한다.

### 해시 충돌 해결법

- **체이닝**: 같은 버킷에 연결 리스트로 충돌한 항목들을 묶는다. 구현이
  단순하고 적재율이 1을 넘어도 동작한다.
- **개방 주소법**: 빈 버킷을 찾아 다음 위치에 저장한다. 선형 탐사, 제곱
  탐사, 이중 해싱이 있다.

## 적재율과 재해싱

적재율은 저장된 항목 수를 버킷 수로 나눈 값이다. 임계 적재율을 넘으면
테이블을 키워 재해싱한다 — 모든 항목을 새 테이블에 다시 매핑한다.

## 응용

캐시, 색인, 중복 제거, 데이터베이스 인덱스, 컴파일러의 심볼 테이블 등
광범위하게 쓰인다.
