해시 테이블 정리
1. 해시의 핵심
- Key → Index로 매핑하여 빠른 탐색을 제공하는 자료구조
- 평균 시간 복잡도: O(1)
- 최악의 경우: O(N) (충돌 발생 시)
2. 버킷 기반 해시 테이블
해시 테이블은 데이터를 직접 한 칸에 저장하는 것이 아니라,
여러 개의 **버킷(bucket)**으로 나누어 관리한다.
전체 흐름:
키 → 해시값 → 버킷 번호 → 버킷 내부에서 원소 관리
인덱스 계산:
index = hash(key) % bucket_count
3. 충돌 (Collision)
서로 다른 key가 같은 버킷으로 매핑되는 현상
충돌은 필연적이며, 이를 어떻게 처리하느냐가 성능을 결정한다.
4. 충돌 해결 방식
4.1 Open Addressing
테이블 내부에서 충돌 해결
선형 조사 (Linear Probing)
- h(k), h(k)+1, h(k)+2 …
- 구현 단순, 캐시 효율 좋음
- Primary Clustering 발생
이차 조사 (Quadratic Probing)
- h(k)+1², h(k)+2² …
- 선형 조사보다 클러스터링 완화
- Secondary Clustering 존재
- 테이블 크기 설계 중요
이중 해싱 (Double Hashing)
- h(k) + i * h2(k)
- 두 번째 해시 함수로 이동 간격 결정
- 클러스터링 최소화
- h2(k) ≠ 0
- 테이블 크기와 서로소 관계 필요
다항 해싱 (Polynomial Hashing)
- 문자열이나 배열을 숫자로 변환하는 해시 방식
- 형태:
- hash(s) = s[0] * B^(n-1) + s[1] * B^(n-2) + … + s[n-1]
- B는 보통 31, 37 같은 값 사용
- mod 연산과 함께 사용하여 overflow 방지
특징:
- 문자열 순서를 반영
- 충돌을 줄이기 위한 해시 함수로 사용됨
- Rolling Hash로 확장 가능
주의:
- 다항 해싱은 충돌 “해결 방법”이 아니라 Open Addressing에서 사용할 수 있는 “해시 함수”이다
4.2 Chaining
버킷 내부에 리스트 형태로 저장
- 구현 직관적
- 테이블이 꽉 차도 동작 가능
- 메모리 오버헤드 존재
- 캐시 비효율
5. Load Factor
load factor = 저장된 원소 수 / 테이블 크기
영향
- 값이 커질수록 충돌 증가
- 탐색 / 삽입 비용 증가
- 평균 O(1) 성능이 깨짐
특징
- Open Addressing: 매우 민감
- Chaining: 상대적으로 덜 민감
6. Rehashing
테이블 크기를 늘리고 모든 원소를 다시 배치하는 과정
필요한 이유
- 충돌 감소
- 성능 회복
- Load Factor 감소
중요한 포인트
- 단순 복사가 아니라 재삽입 필요
- 이유: hash(key) % table_size가 바뀌기 때문
비용
- O(N)
- 하지만 드물게 발생 → 평균 O(1) 유지
7. unordered_map
- C++ 해시 기반 컨테이너
- 버킷 기반 구조
- 평균 O(1) 성능
- 정렬되지 않음
동작:
- key 해시 계산
- 버킷 선택
- 버킷 내부에서 탐색
8. Rolling Hash
문자열의 부분 구간 해시를 빠르게 갱신하는 방식
특징:
- 이전 해시를 재사용
- 부분 문자열 비교에 사용
- 문자열 검색 알고리즘에서 활용
목적:
- 저장 위치가 아니라 “부분 문자열 비교”
질문 사항
기본
1. unordered_map의 평균 O(1)은 어떤 전제에서 성립하나요?
- 해시 함수가 균등 분포를 만든다
- Load Factor가 낮다
- 충돌이 적다
2. 충돌이 많아지면 왜 O(N)이 되나요?
- 한 버킷에 모든 데이터가 몰릴 수 있음
- 버킷 내부 탐색이 선형 탐색이 되기 때문
3. 체이닝과 Open Addressing의 차이는?
- 체이닝: 버킷 내부에 리스트 저장
- Open Addressing: 테이블 내부에서 이동하며 저장
4. Load Factor가 높아지면 왜 성능이 떨어지나요?
- 충돌 증가
- 탐색 길이 증가
- 삽입 비용 증가
5. Rehashing은 왜 필요한가요?
- 성능 저하 방지
- 충돌 감소
- 평균 O(1) 유지
6. map 대신 unordered_map을 쓰면 안 되는 경우는?
- 정렬 필요
- 범위 탐색 필요
- worst-case 보장 필요
7. 사용자 정의 타입을 key로 쓰려면?
- hash 함수 정의
- equality 연산자 정의
8. operator[] vs find()
- operator[]: 없으면 생성
- find(): 없으면 end() 반환
심화
1. Primary Clustering이 발생하는 이유
- 선형 조사에서 충돌 시 연속된 위치에 저장
- 데이터가 한 곳에 몰리며 클러스터 형성
2. Open Addressing에서 삭제를 단순히 비우면 안 되는 이유
- 탐색 경로가 끊김
- 뒤에 있는 데이터 탐색 불가
- Tombstone 필요
3. Rehash 시 재삽입이 필요한 이유
- 테이블 크기 변경 → 해시 결과 변경
4. 테이블 크기를 소수로 잡는 이유
- 해시 패턴 충돌 방지
- 분포 균등화
5. 좋은 해시 vs 빠른 해시
- 좋은 해시: 충돌 적음, 계산 비용 큼
- 빠른 해시: 계산 빠름, 충돌 가능성 증가
6. 문자열 해시 방식
- 다항식 해시 사용
- base^i 형태로 계산
7. 정렬이 필요한 경우 해시 사용 가능?
- 부적합
- 순서 보장 없음
8. 메모리 제한 환경에서 유리한 방식
- Open Addressing (포인터 없음)
9. 삭제가 많은 경우 적합한 방식
- Chaining (삭제 간단)
10. 선형 조사법이 캐시 효율이 좋은 이유
- 연속 메모리 접근
- 캐시 적중률 증가