Hash Map (해시 맵)
Hash Map(해시 맵)은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 이용해 데이터를 빠르게 조회할 수 있습니다.
동작 원리
- 키를 해시 함수에 넣어 인덱스(버킷) 결정
- 같은 인덱스에 여러 값이 들어오면 충돌(collision) 발생 → 체이닝, 오픈 어드레싱 등으로 해결
- 평균적으로 O(1) 시간에 데이터 조회/삽입/삭제 가능
버킷(Bucket)이란?
버킷은 해시 맵에서 실제 데이터를 저장하는 공간입니다. 해시 함수가 키를 인덱스로 변환하면, 그 인덱스에 해당하는 버킷에 데이터가 저장됩니다.
예시:
- 키 "apple" → 해시 함수 → 인덱스 3 → 버킷[3]에 저장
- 키 "banana" → 해시 함수 → 인덱스 7 → 버킷[7]에 저장
해시 충돌 해결 방법
1. 체이닝(Chaining)
같은 버킷에 여러 데이터가 들어올 때, 연결 리스트(또는 다른 자료구조)로 연결하는 방법입니다.
버킷[3]: apple → orange → grape
버킷[7]: banana
- 장점: 구현이 간단하고, 버킷이 가득 차도 계속 저장 가능
- 단점: 특정 버킷에 데이터가 많이 몰리면 성능 저하
2. 오픈 어드레싱(Open Addressing)
같은 버킷에 데이터가 들어올 때, 다른 빈 버킷을 찾아서 저장하는 방법입니다.
주요 방식:
-
선형 탐사(Linear Probing): 다음 버킷을 순차적으로 확인
-
이차 탐사(Quadratic Probing): 제곱수만큼 건너뛰며 확인
-
이중 해싱(Double Hashing): 두 번째 해시 함수로 다음 위치 결정
-
장점: 메모리 효율적, 캐시 지역성 좋음
-
단점: 삭제 시 복잡, 버킷이 가득 차면 저장 불가
장점과 단점
| 장점 | 단점 |
|---|---|
| 빠른 조회/삽입/삭제 | 해시 충돌 가능성 |
| 다양한 키 사용 가능 | 순서 보장 X (언어마다 다름) |
| 구현이 간단 | 메모리 사용량 많을 수 있음 |
언어별 구현
- Python:
dict - JavaScript:
Map,Object - Java:
HashMap - C++:
unordered_map
활용 예시
- 빈도수 집계, 캐시, 데이터베이스 인덱스, 매핑 테이블 등
참고
- 해시 함수의 품질이 성능에 큰 영향
- 충돌 해결 방식에 따라 성능 차이 발생