HashMap해시맵

해시맵(HashMap)은 키(Key)→값(Value) 쌍을 저장하는 자료구조로, 해시 함수를 이용해 키를 배열의 인덱스(버킷)로 변환해 데이터를 저장·조회한다. 평균 O(1)의 삽입·검색·삭제 성능을 제공한다.

핵심 원리

키(Key) → 해시 함수 → 해시값(정수) → 버킷 인덱스 → 값(Value)

예시:
"apple"  → hash() → 3 → bucket[3] → 1500
"banana" → hash() → 7 → bucket[7] → 1200
"cherry" → hash() → 3 → bucket[3] → 충돌 발생!

시간 복잡도

해시 충돌 해결 방법

1. 체이닝(Chaining) — 각 버킷에 연결 리스트로 충돌 요소를 저장

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)에 가깝게
• •눈사태 효과: 입력이 조금만 달라도 출력이 크게 달라짐

언어별 구현

실전 활용 예시

• •캐시(Cache): URL → 응답 데이터
• •빈도 카운팅: 단어 → 등장 횟수
• •중복 제거: 집합(Set)의 내부 구현
• •그래프 인접 리스트: 노드 → 이웃 목록
• •메모이제이션(DP 최적화): 입력 → 계산 결과

관련 개념

• •해시 — 해시맵의 핵심 함수
• •스택 — 대표적인 선형 자료구조
• •큐 — 대표적인 선형 자료구조
• •동적 프로그래밍 — 해시맵으로 메모이제이션 구현