해시 함수 설계 — 좋은 해시 함수의 조건과 충돌 해결
HashMap의 get()이 O(1)이라고 하는데, 정말 항상 O(1)일까요? 그 뒤에 숨어있는 해시 함수와 충돌 해결의 세계를 들여다봅니다.
해시 함수란
해시 함수는 임의 크기의 데이터를 고정 크기의 값으로 변환 하는 함수입니다.
해시 함수: "hello" → 5 (0~9 범위의 인덱스)
해시 함수: "world" → 2
해시 함수: "java" → 7
해시 테이블에서 해시 함수는 키를 배열의 인덱스로 변환 하는 역할을 합니다.
좋은 해시 함수의 조건
1. 균등 분포 (Uniform Distribution)
키들이 버킷에 고르게 분포 되어야 합니다. 특정 버킷에만 몰리면 충돌이 많아져 성능이 떨어집니다.
나쁜 해시 함수: 버킷 0: ████████ 버킷 1: 버킷 2: █
좋은 해시 함수: 버킷 0: ███ 버킷 1: ███ 버킷 2: ███
2. 결정성 (Deterministic)
같은 입력에 대해 항상 같은 출력 을 내야 합니다.
3. 효율성
해시 값 계산이 O(1) 또는 키 길이에 비례하는 시간 내에 이루어져야 합니다.
4. 눈사태 효과 (Avalanche Effect)
입력이 조금만 바뀌어도 출력이 크게 달라져야 합니다.
"cat" → 42738
"cat" → 42738 (같은 입력, 같은 출력 — 결정성)
"bat" → 91025 (한 글자 차이인데 출력은 완전히 다름 — 눈사태)
Java의 hashCode()
Java에서 모든 객체는 hashCode() 메서드를 가집니다.
String의 hashCode
// String.hashCode() 구현
public int hashCode() {
int h = hash; // 캐싱된 값
if (h == 0 && !hashIsZero) {
for (int i = 0; i < value.length; i++) {
h = 31 * h + value[i]; // 다항식 해시
}
// s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
}
return h;
}
31을 곱하는 이유는 다음과 같습니다.
- 홀수 소수: 짝수를 곱하면 하위 비트가 0이 되어 정보가 손실됩니다
31 * h는(h << 5) - h로 최적화 가능합니다- 경험적으로 문자열에 대해 좋은 분포를 보입니다
hashCode()와 인덱스 변환
HashMap에서 hashCode를 배열 인덱스로 변환하는 과정:
// HashMap 내부 (간략화)
static int hash(Object key) {
int h = key.hashCode();
return h ^ (h >>> 16); // 상위 16비트를 하위에 섞음
}
// 인덱스 계산 (capacity가 2의 거듭제곱)
int index = hash & (capacity - 1); // hash % capacity와 동일
상위 비트를 하위에 섞는 이유는, 배열 크기가 작을 때 상위 비트가 무시되는 문제를 방지하기 위해서입니다.
충돌 해결 — 체이닝 (Separate Chaining)
같은 인덱스에 여러 키가 매핑될 때, 각 버킷을 연결 리스트 로 만드는 방법입니다.
버킷 0: → [Alice, 100] → [Eve, 400] → null
버킷 1: → [Bob, 200] → null
버킷 2: → [Charlie, 300] → null
// 간단한 체이닝 해시 테이블
public class ChainingHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private LinkedList<Entry<K, V>>[] buckets;
private int size;
@SuppressWarnings("unchecked")
public ChainingHashMap() {
buckets = new LinkedList[DEFAULT_CAPACITY];
}
public void put(K key, V value) {
int index = hash(key) & (buckets.length - 1);
if (buckets[index] == null) {
buckets[index] = new LinkedList<>();
}
// 기존 키가 있으면 값 갱신
for (Entry<K, V> entry : buckets[index]) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
buckets[index].add(new Entry<>(key, value));
size++;
}
public V get(K key) {
int index = hash(key) & (buckets.length - 1);
if (buckets[index] == null) return null;
for (Entry<K, V> entry : buckets[index]) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
private int hash(K key) {
int h = key.hashCode();
return h ^ (h >>> 16);
}
static class Entry<K, V> {
K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
}
Java 8+ HashMap의 트리화
Java 8부터 하나의 버킷에 항목이 8개 이상 쌓이면 연결 리스트를 Red-Black 트리로 변환 합니다.
버킷 3: [LinkedList] → 항목 7개 이하: O(n) 탐색
버킷 3: [Red-Black Tree] → 항목 8개 이상: O(log n) 탐색
이를 트리화(treeification) 라고 합니다. 항목이 6개 이하로 줄어들면 다시 연결 리스트로 복귀합니다.
충돌 해결 — 개방 주소법 (Open Addressing)
모든 항목을 배열 자체에 저장하는 방법입니다. 충돌 시 다른 빈 슬롯을 찾아 저장합니다.
선형 탐사 (Linear Probing)
충돌 시 바로 다음 슬롯을 확인합니다.
// 선형 탐사 해시 테이블
public void put(K key, V value) {
int index = hash(key) % capacity;
while (table[index] != null && !table[index].key.equals(key)) {
index = (index + 1) % capacity; // 다음 슬롯으로
}
table[index] = new Entry<>(key, value);
}
단점은 **1차 클러스터링 **: 충돌이 발생한 근처에 데이터가 뭉쳐서 연쇄 충돌이 발생합니다.
삽입 전: [ A | | B | | | ]
해시(C) = 2 (B와 충돌)
삽입 후: [ A | | B | C | | ] ← C가 옆으로 밀림
해시(D) = 2 (또 충돌, B와 C를 지나가야 함)
삽입 후: [ A | | B | C | D | ] ← 클러스터 커짐
이차 탐사 (Quadratic Probing)
충돌 시 1, 4, 9, 16, ... 칸씩 건너뜁니다.
int index = hash(key) % capacity;
int i = 0;
while (table[index] != null) {
i++;
index = (hash(key) + i * i) % capacity;
}
1차 클러스터링은 줄어들지만, 2차 클러스터링 이 발생할 수 있습니다.
이중 해싱 (Double Hashing)
두 번째 해시 함수로 탐사 간격을 결정합니다.
int index = hash1(key) % capacity;
int step = hash2(key); // 두 번째 해시로 간격 결정
while (table[index] != null) {
index = (index + step) % capacity;
}
클러스터링을 가장 잘 방지하지만, 해시 함수가 2개 필요합니다.
Load Factor와 리해싱
Load Factor = 저장된 항목 수 / 버킷 수
// Java HashMap의 기본 설정
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_INITIAL_CAPACITY = 16;
// load factor가 0.75를 넘으면 리해싱
// 16 * 0.75 = 12개가 차면 32개로 확장
리해싱(Rehashing) 과정:
- 새로운 배열(기존의 2배 크기)을 할당합니다
- 모든 항목의 해시 값을 재계산합니다
- 새 배열에 재배치합니다
이 과정이 O(n)이지만, ArrayList와 마찬가지로 amortized O(1) 입니다.
체이닝 vs 개방 주소법 비교
| 특성 | 체이닝 | 개방 주소법 |
|---|---|---|
| 구현 | 간단 | 보통 |
| 메모리 | 포인터 오버헤드 | 배열 내 저장 |
| 캐시 효율 | 낮음 | 높음 |
| Load Factor > 1 | 가능 | 불가능 |
| 삭제 | 쉬움 | 복잡 (tombstone 필요) |
| 클러스터링 | 없음 | 발생 가능 |
- Java HashMap: 체이닝 (트리화 포함)
- Python dict: 개방 주소법
- Go map: 체이닝
해시 함수의 실무 활용
일관성 해싱 (Consistent Hashing)
분산 시스템에서 서버를 추가/제거할 때 데이터 재분배를 최소화합니다.
// 개념적 예시
// 해시 링 위에 서버와 키를 배치
// 키는 시계방향으로 가장 가까운 서버에 할당
int keyHash = hash("user:1001");
int serverHash = findNextServer(keyHash); // 해시 링에서 탐색
비밀번호 해싱
비밀번호는 단방향 해시 함수(bcrypt, scrypt)로 저장해야 합니다. HashMap의 해시 함수와는 목적이 다릅니다.
정리
- 좋은 해시 함수는 ** 균등 분포, 결정성, 효율성, 눈사태 효과 **를 만족해야 합니다.
- 충돌 해결의 두 가지 방법: ** 체이닝 **(연결 리스트/트리)과 ** 개방 주소법 **(선형/이차/이중 해싱).
- Java HashMap은 ** 체이닝 + 트리화 **를 사용하며, load factor 0.75에서 리해싱합니다.
- Load Factor가 성능에 직접적인 영향을 미치므로, 예상 데이터 크기에 맞는 초기 용량 설정이 중요합니다.
- hashCode()와 equals()는 반드시 함께 재정의해야 합니다.