Java를 공부하다 보면 가장 자주 사용하는 자료구조 중 하나가 HashMap이다.
키를 이용해 데이터를 저장하고 조회할 수 있으며, 평균적인 조회 시간복잡도는 O(1)이라고 배운다.
Map<String, Integer> scores = new HashMap<>();
scores.put("Kim", 100);
scores.put("Lee", 90);
System.out.println(scores.get("Kim"));키를 전달하기만 하면 원하는 값을 빠르게 찾을 수 있다.
그런데 여기서 의문이 생긴다.
정말 데이터가 100개든 100만 개든 항상 O(1)로 값을 찾을 수 있을까?
그렇지는 않다.
HashMap은 평균적으로 O(1)의 성능을 기대할 수 있지만, 항상 일정한 시간 안에 동작한다고 보장되는 자료구조는 아니다.
그 이유를 이해하려면 해시 함수와 해시 충돌을 살펴봐야 한다.
1. HashMap은 어떻게 데이터를 찾을까?
배열을 생각해 보자.
배열은 인덱스를 이용해 원하는 위치에 직접 접근할 수 있다.
int[] numbers = {10, 20, 30};
System.out.println(numbers[1]); // 20인덱스를 이미 알고 있다면 처음부터 모든 데이터를 순회할 필요가 없다.
HashMap은 여기서 한 단계 더 나아간다.
숫자 인덱스 대신 문자열이나 객체를 키로 사용하고, 해시 함수를 이용해 저장 위치를 결정한다.
"Kim"
|
▼
hashCode()
|
▼
해시값 계산
|
▼
버킷 인덱스 결정
|
▼
해당 버킷에서 값 탐색이 덕분에 모든 데이터를 순차적으로 탐색하지 않아도 된다.
그런데 문제가 있다.
서로 다른 키가 항상 서로 다른 버킷에 저장되는 것은 아니다.
2. 서로 다른 키가 같은 위치를 가리킨다면?
해시 충돌(Hash Collision)은 서로 다른 키가 같은 해시값을 갖거나, 서로 다른 해시값이더라도 최종적으로 같은 버킷에 배치되는 상황을 말한다.
예를 들어 다음과 같은 상황을 가정하자.
Key A ──┐
|
Key B ──┼──→ Bucket 3
|
Key C ──┘서로 다른 키 세 개가 같은 버킷에 들어가야 한다.
HashMap은 이런 상황을 어떻게 처리할까?
Java의 HashMap에서는 버킷 내부의 항목들을 연결 리스트 형태로 관리할 수 있다.
Bucket 3
|
▼
[Key A] → [Key B] → [Key C]이제 특정 키를 찾으려면 버킷 안에서 키를 비교해야 한다.
충돌한 데이터가 많아질수록 탐색에 시간이 더 걸릴 수 있다.
연결 리스트의 길이가 n이라면 해당 버킷에서 최악의 경우 O(n)에 가까운 탐색이 필요하다.
그러면 HashMap의 시간복잡도가 O(1)이라는 설명은 틀린 것일까?
아니다.
O(1)은 적절한 해시 분포와 일반적인 사용 조건에서 기대할 수 있는 평균적인 시간복잡도를 설명한 것이다.
3. Java HashMap은 충돌이 많아지면 트리로 바뀐다
Java 8 이후의 HashMap에는 해시 충돌로 인해 하나의 버킷에 항목이 과도하게 몰리는 문제를 완화하기 위한 기능이 존재한다.
연결 리스트를 트리 구조로 전환하는 것이다.
Java HashMap 구현에서는 연결 리스트가 길어지면 Red-Black Tree 기반의 트리화를 고려한다.
Red-Black Tree는 스스로 균형을 유지하는 이진 탐색 트리의 일종이다.
따라서 트리 탐색을 효율적으로 수행할 수 있는 상황에서는 연결 리스트보다 나은 성능을 기대할 수 있다.
관련 구현에는 다음과 같은 상수가 존재한다.
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;TREEIFY_THRESHOLD는 버킷 내 항목 수가 많아질 때 트리화를 검토하는 기준이다.
하지만 항목이 8개에 도달했다고 무조건 트리로 변경되는 것은 아니다.
HashMap 내부 배열의 용량이 충분하지 않다면 트리화보다 배열 크기를 확장하는 작업이 우선될 수 있다.
MIN_TREEIFY_CAPACITY = 64는 이러한 동작과 관련된 기준이다.
여기서 두 가지를 알 수 있다.
첫째, Java HashMap은 해시 충돌을 단순히 방치하지 않는다.
둘째, 그렇다고 모든 상황에서 반드시 O(log n)이 보장된다고 단정해서는 안 된다.
해시 계산과 키 비교 비용, 키의 특성, 내부 구조 등에 따라 실제 성능은 달라질 수 있다.
4. 의도적으로 해시 충돌을 발생시켜 보자
실제로 여러 키가 같은 해시값을 반환하도록 만들어보자.
Java의 record를 사용하면 간단하게 실험할 수 있다.
record BadKey(int id) {
@Override
public int hashCode() {
return 42;
}
}모든 객체의 hashCode()가 42를 반환한다.
이제 HashMap에 데이터를 저장해 보자.
Map<BadKey, Integer> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
map.put(new BadKey(i), i);
}
System.out.println(map.get(new BadKey(999)));서로 다른 키가 동일한 해시값을 사용하도록 만든 것이다.
이렇게 되면 많은 항목이 같은 버킷에 몰리게 된다.
Java HashMap은 내부적으로 충돌을 처리하므로 조회 자체는 가능하지만, 해시값이 적절하게 분포된 경우와는 다른 성능 특성을 보일 수 있다.
실험할 때는 정상적인 hashCode()를 사용하는 키와 비교해 보는 것이 좋다.
단, 아주 작은 데이터에서는 JIT 컴파일, JVM 워밍업, 측정 오차 등의 영향이 크기 때문에 단순 실행 시간 한 번만 비교해서 성능을 단정해서는 안 된다.
정확한 Java 마이크로벤치마크에는 JMH 같은 도구를 사용하는 편이 적절하다.
5. HashMap의 성능에는 또 다른 변수가 있다
해시 충돌 외에도 알아둘 부분이 있다.
바로 Load Factor와 Resizing이다.
HashMap의 기본 Load Factor는 0.75다.
기본 초기 용량은 16이다.
기본 설정에서 내부 배열의 크기가 16이라면, 저장된 항목 수가 임계값인 12를 초과할 때 배열 확장이 발생할 수 있다.
초기 버킷 수: 16
로드 팩터: 0.75
16 × 0.75 = 12
저장 항목 수가 임계값을 넘으면
배열 확장 및 항목 재배치Resizing은 비용이 드는 작업이다.
따라서 한 번의 put() 연산이 항상 O(1)의 실행 시간을 갖는 것은 아니다.
전체 삽입 연산을 장기적으로 분석할 때는 분할상환 분석(Amortized Analysis)을 통해 평균적인 비용을 설명할 수 있다.
또 하나 주의할 점이 있다.
HashMap은 기본적으로 스레드 안전하지 않다.
여러 스레드가 동시에 동일한 HashMap을 수정한다면 별도의 동기화나 ConcurrentHashMap 같은 자료구조를 고려해야 한다.
단순히 조회 시간복잡도만 보고 자료구조를 선택해서는 안 되는 이유다.
6. O(1)이라는 말 뒤에 숨겨진 조건
자료구조를 처음 공부할 때는 시간복잡도를 암기하게 된다.
배열 접근은 O(1), 이진 탐색은 O(log n), HashMap 조회는 평균 O(1)이라고 외운다.
하지만 중요한 것은 그 복잡도가 어떤 조건에서 성립하는지 이해하는 것이다.
HashMap이 평균 O(1)의 성능을 기대할 수 있는 이유는 해시 함수를 통해 키가 적절하게 분산된다는 가정이 있기 때문이다.
충돌이 심하거나, 해시 계산 자체가 비싸거나, 리사이징이 발생한다면 개별 연산의 비용은 달라질 수 있다.
또한 자료구조의 동시성 지원 여부도 실제 선택에 영향을 준다.
시간복잡도는 성능을 이해하기 위한 도구이지, 모든 실행 상황의 속도를 보장하는 약속은 아니다.
자료구조를 제대로 이해한다는 것은 단순히 O(1)을 외우는 것이 아니라, 언제 그 성능이 달라질 수 있는지 설명할 수 있다는 의미일 것이다.
생각해 볼 문제
Q1. HashMap에서 해시 충돌이 발생하면 어떻게 처리할까?
Q2. Java HashMap이 연결 리스트를 트리로 변경하는 이유는 무엇일까?
Q3. HashMap과 ConcurrentHashMap은 어떤 상황에서 구분해 사용해야 할까?