해시 충돌과 참조 지역성: 자바 HashMap 성능 저하 케이스
HashMap O(1)을 믿고 시간초과를 맞았다#
백준 7453번 문제를 풀 때였습니다. 4개 배열에서 원소를 하나씩 골라 합이 0이 되는 조합의 수를 구하는 문제인데, 접근 방식은 간단했습니다. A+B 쌍과 C+D 쌍을 각각 계산한 뒤, 한쪽을 HashMap에 넣고 보수가 존재하는지 탐색하면 됩니다.
탐색 길이는 4000×4000 = 16,000,000. HashMap이 O(1)이라면 충분히 통과할 수 있는 크기입니다. C/C++에서는 실제로 이 방법으로 통과됩니다. 그런데 자바에서는 시간초과가 났습니다.
원인은 해시 충돌이었습니다. 자바 HashMap의 해시 함수 특성상, 특정 입력 패턴에서 충돌이 집중적으로 발생합니다. 충돌이 8회를 넘으면 버킷이 Red-Black Tree로 변환되어 O(log N)으로 동작하는데, 1600만 건에서 이 오버헤드가 누적되면 시간초과로 이어집니다.
결국 이분탐색이나 투포인터로 접근해야 했습니다. 이 경험을 계기로 HashMap의 해시 충돌이 실제로 얼마나 성능에 영향을 주는지, 그리고 CPU 캐시의 참조 지역성과 어떻게 결합되는지를 정리해봤습니다.
HashMap은 정말 O(1)인가#
자바 HashMap의 put, get, containsKey는 평균적으로 O(1)입니다. 해시 함수가 키를 버킷에 고르게 분산시키는 한, 하나의 버킷에 하나의 엔트리만 들어가고 배열 인덱스 접근처럼 동작합니다.
문제는 해시 충돌이 심해질 때입니다. 여러 키가 같은 버킷에 몰리면, 그 버킷 안에서 선형 탐색이 필요해집니다.
Java 8의 충돌 처리 개선#
Java 8부터는 충돌 처리 방식이 개선됐습니다. (OpenJDK HashMap 소스)
- 초기에는 충돌된 엔트리를 LinkedList로 체이닝합니다
- 같은 버킷에 8개 이상의 엔트리가 들어가면 Red-Black Tree로 변환합니다 (
TREEIFY_THRESHOLD = 8)
이 개선 덕분에 최악의 경우가 O(N)에서 O(log N)으로 줄었습니다. 하지만 O(log N)도 O(1)과는 다릅니다. 1600만 건에서 충돌이 빈번하면, 트리 변환 비용 + 트리 탐색 비용이 누적되면서 전체 시간 복잡도가 O(N² log N) 수준까지 올라갈 수 있습니다.
복잡도 비교: 해시 vs 이분탐색 vs 투포인터#
백준 7453번 기준으로 비교하면:
| 접근 방식 | 시간 복잡도 | 비고 |
|---|---|---|
| HashMap | 평균 O(N²), 최악 O(N² log N²) | 충돌 시 트리화 비용 포함 |
| 이분탐색 | O(N² log N) | 정렬 + 이분탐색, 충돌 없음 |
| 투포인터 | O(N² log N) | 정렬 + 투포인터, 충돌 없음 |
이론상 HashMap이 빠르지만, 해시 충돌이 발생하면 이분탐색/투포인터보다 느려집니다. 충돌 없는 O(N² log N)이 충돌 있는 O(N²)보다 실제로 빠른 역설적인 상황입니다.
직접 확인: 해시 충돌 벤치마크#
모든 키가 같은 해시코드를 반환하도록 강제해서 최악의 충돌을 만들어봤습니다.
public class ExtremeHashCollision {
static class BadKey {
private final int value;
public BadKey(int value) {
this.value = value;
}
@Override
public int hashCode() {
return 42; // 모든 객체가 동일한 해시 코드
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof BadKey)) return false;
BadKey other = (BadKey) o;
return this.value == other.value;
}
}
public static void main(String[] args) {
int N = 500_000;
Map<BadKey, Integer> map = new HashMap<>(N);
long start = System.nanoTime();
for (int i = 0; i < N; i++) {
map.put(new BadKey(i), i);
}
long afterPut = System.nanoTime();
long sum = 0;
for (int i = 0; i < N; i++) {
sum += map.get(new BadKey(i));
}
long afterGet = System.nanoTime();
System.out.printf("Insertion took: %.3f ms\n", (afterPut - start) / 1e6);
System.out.printf("Lookup took: %.3f ms\n", (afterGet - afterPut) / 1e6);
System.out.println("Sum check = " + sum);
}
}50만 건 전부 같은 해시키로 넣는 극단적인 테스트입니다. 정상적인 HashMap이라면 50만 건 삽입/조회는 수백ms면 끝나지만, 모든 키가 충돌하면 삽입에 수십 초, 조회에도 수십 초가 걸립니다. O(1)이 아니라 사실상 O(N)으로 동작하는 것을 체감할 수 있습니다.
참조 지역성이 문제를 키운다#
해시 충돌이 성능을 떨어뜨리는 건 시간 복잡도만의 문제가 아닙니다. CPU 캐시의 참조 지역성(Reference Locality)까지 깨지면서 실제 체감 성능은 이론보다 더 나빠집니다.
참조 지역성이란, 프로그램이 메모리를 접근할 때 최근에 사용한 주소나 인접한 주소를 다시 참조하는 경향을 말합니다. CPU는 이 패턴을 이용해 캐시에 데이터를 미리 올려놓고 재활용합니다.
- 시간적 지역성: 한 번 참조된 데이터는 곧 다시 참조될 가능성이 높습니다
- 공간적 지역성: 어떤 주소가 참조되면, 인접 주소도 곧 사용될 가능성이 높습니다
배열은 연속된 메모리에 데이터가 나란히 놓여 있어서 공간적 지역성이 극대화됩니다. 반면 해시 충돌이 발생하면 LinkedList나 Red-Black Tree 노드를 따라가야 하는데, 이 노드들은 힙 메모리에 산재해 있습니다. 노드를 하나 방문할 때마다 캐시 미스가 발생하고, 메인 메모리에서 데이터를 가져오는 시간이 추가됩니다.
HashMap vs TreeMap vs ArrayList 벤치마크#
public class LocalityTest {
public static void main(String[] args) {
final int[] SIZES = {10_000, 100_000, 1_000_000, 10_000_000};
for (int SIZE : SIZES) {
System.out.println("Testing with SIZE: " + SIZE);
Map<Integer, Integer> hashMap = new HashMap<>(SIZE);
for (int i = 0; i < SIZE; i++) hashMap.put(i, i);
Map<Integer, Integer> treeMap = new TreeMap<>();
for (int i = 0; i < SIZE; i++) treeMap.put(i, i);
List<Integer> arrayList = new ArrayList<>(SIZE);
for (int i = 0; i < SIZE; i++) arrayList.add(i);
int sum = 0;
System.gc();
long startHash = System.nanoTime();
for (int i = 0; i < SIZE; i++) sum += hashMap.get(i);
long endHash = System.nanoTime();
System.out.println("HashMap 조회 시간(ms): " + (endHash - startHash) / 1e6);
long startTree = System.nanoTime();
for (int i = 0; i < SIZE; i++) sum += treeMap.get(i);
long endTree = System.nanoTime();
System.out.println("TreeMap 조회 시간(ms): " + (endTree - startTree) / 1e6);
long startList = System.nanoTime();
for (int i = 0; i < SIZE; i++) sum += arrayList.get(i);
long endList = System.nanoTime();
System.out.println("ArrayList 조회 시간(ms): " + (endList - startList) / 1e6);
System.out.println();
}
}
}데이터 크기별 조회 성능 경향:
| 자료구조 | 시간 복잡도 | 참조 지역성 | 특징 |
|---|---|---|---|
| ArrayList | O(1) | 최상 (연속 메모리) | 인덱스 기반, 데이터 커져도 성능 거의 일정 |
| HashMap | 평균 O(1) | 보통 (버킷 배열은 연속, 체이닝은 분산) | 충돌 없으면 빠르지만, 충돌 시 급격히 저하 |
| TreeMap | O(log N) | 낮음 (트리 노드 분산) | 항상 O(log N)으로 예측 가능, 정렬 유지 |
ArrayList가 압도적으로 빠른 건 연속 메모리 덕분입니다. HashMap은 충돌이 없을 때 ArrayList에 근접하지만, TreeMap은 항상 O(log N)이라 데이터가 커질수록 차이가 벌어집니다. 다만 TreeMap은 최악의 경우에도 성능이 예측 가능하다는 장점이 있습니다.
정리#
HashMap의 O(1)은 해시 함수가 키를 고르게 분산시킬 때의 이야기입니다. 충돌이 심하면 O(log N)까지 떨어지고, 참조 지역성 파괴로 인한 캐시 미스까지 겹치면 이론적 복잡도 이상으로 느려집니다.
백준 7453번으로 돌아가면, HashMap 대신 정렬 + 이분탐색을 택한 이유가 여기에 있습니다. 정렬된 배열은 연속 메모리에서 순차 접근하므로 캐시 친화적이고, 충돌이라는 변수가 없어서 성능이 안정적입니다.
실무에서 HashMap을 쓸 때도 마찬가지입니다. 키의 hashCode() 분포가 고르지 않거나, 외부 입력을 키로 쓰는 경우에는 충돌 가능성을 고려해야 합니다. 초기 용량(capacity)을 넉넉하게 잡아 재해시를 줄이고, 해시 함수의 품질을 점검하는 것이 기본적인 방어입니다. 그래도 불안하면 TreeMap처럼 최악 O(log N)이 보장되는 자료구조를 검토하는 것도 방법입니다.