왜 해시 테이블이란? — O(1)의 마법이 필요한가? 실무에서 이 개념 없이는 문제를 해결할 수 없습니다. 핵심 동기와 배경을 먼저 이해합시다.
해시 테이블(Hash Table)은 키(key)를 값(value)에 매핑하는 자료구조로, 평균 O(1)에 검색, 삽입, 삭제가 가능합니다.
핵심 아이디어:
1. 키를 해시 함수에 넣어 숫자(인덱스)로 변환
2. 그 인덱스의 배열 위치에 값을 저장
3. 검색 시 같은 해시 함수로 인덱스를 계산 → 바로 접근!
예시:
hash("apple") → 3 → table[3] = "사과"
hash("banana") → 7 → table[7] = "바나나"
// 검색: hash("apple") → 3 → table[3] = "사과" — O(1)!
연산 복잡도:
| 연산 | 평균 | 최악 |
|------|------|------|
| 검색 | O(1) | O(n) |
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
왜 최악이 O(n)?
모든 키가 같은 인덱스로 해시되면 (충돌) → 하나의 리스트가 됨 → O(n)
하지만 좋은 해시 함수를 쓰면 이런 일은 거의 발생하지 않습니다.
실생활의 해시 테이블:
- JavaScript: Object, Map
- Python: dict
- Java: HashMap
- DB: 해시 인덱스