자료구조
HashMap해시맵
해시맵(HashMap)은 키(Key)→값(Value) 쌍을 저장하는 자료구조로, 해시 함수를 이용해 키를 배열의 인덱스(버킷)로 변환해 데이터를 저장·조회한다. 평균 O(1)의 삽입·검색·삭제 성능을 제공한다.
핵심 원리
시간 복잡도
| 연산 | 평균 | 최악 (해시 충돌 다발) |
|---|---|---|
| 삽입 | O(1) | O(n) |
| 검색 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
해시 충돌 해결 방법
1. 체이닝(Chaining) — 각 버킷에 연결 리스트로 충돌 요소를 저장
bucket[3] → ["apple":1500] → ["cherry":2000]
Java의 HashMap, Python의 dict가 이 방식을 사용한다.
2. 오픈 어드레싱(Open Addressing) — 충돌 시 다음 빈 버킷을 찾아 저장
- •선형 탐색(Linear Probing): +1씩 이동
- •이차 탐색(Quadratic Probing): +1², +2², +3²...
- •이중 해싱(Double Hashing): 두 번째 해시 함수로 보폭 결정
Load Factor (로드 팩터)
로드 팩터 = (저장된 키 수) / (버킷 총 개수)
로드 팩터가 임계값(Java HashMap의 경우 0.75)을 초과하면 리해싱(Rehashing)이 발생해 버킷 배열을 2배로 확장한다. 리해싱 시 모든 키를 재배치하므로 O(n) 비용이 발생한다.
좋은 해시 함수의 조건
- •균일 분포: 버킷에 고르게 분산
- •결정론적: 동일 입력 → 동일 출력
- •빠른 계산: O(1)에 가깝게
- •눈사태 효과: 입력이 조금만 달라도 출력이 크게 달라짐
언어별 구현
| 언어 | 클래스/타입 | 순서 보장 |
|---|---|---|
| Java | HashMap | ✗ (LinkedHashMap은 ✓) |
| Python | dict | ✓ (3.7+, 삽입 순서) |
| JavaScript | Map, Object | Map은 ✓ |
| C++ | unordered_map | ✗ |
| Go | map | ✗ |
실전 활용 예시
- •캐시(Cache): URL → 응답 데이터
- •빈도 카운팅: 단어 → 등장 횟수
- •중복 제거: 집합(Set)의 내부 구현
- •그래프 인접 리스트: 노드 → 이웃 목록
- •메모이제이션(DP 최적화): 입력 → 계산 결과