STUDY NOTE · 개념 정리
HashMap 동작 원리 정리: 해시 충돌, 체이닝, 트리화, equals와 hashCode 규약
Java
HashMap은 키의hashCode()로 배열의 칸(버킷)을 계산해 저장하므로 평균 O(1)로 조회한다. 같은 칸에 여러 키가 몰리는 해시 충돌은 연결 리스트로 잇는 체이닝으로 처리하고, 자바 8부터는 한 칸이 길어지면 레드-블랙 트리로 바꿔 최악을 O(log n)으로 줄인다. 키 객체는 반드시equals()와hashCode()를 함께 재정의해야 한다.
1. 내부 구조
table (Node 배열, 기본 크기 16)
[0] → null
[1] → (key=A, hash, value, next) → (key=Q, ...) → null ← 충돌: 체이닝
[2] → null
[3] → (key=B, ...)
...
| 용어 | 의미 | 기본값 |
| capacity | 버킷 배열의 크기 (항상 2의 거듭제곱) | 16 |
| load factor | 배열이 얼마나 차면 늘릴지의 비율 | 0.75 |
| threshold | capacity × load factor. 원소 수가 이를 넘으면 배열을 2배로 확장 | 12 |
| TREEIFY_THRESHOLD | 노드가 이 값 이상인 버킷에 또 추가되면 트리 변환 검토 | 8 |
| MIN_TREEIFY_CAPACITY | 트리화하려면 배열 크기가 최소 이 값이어야 함 (작으면 대신 확장) | 64 |
| UNTREEIFY_THRESHOLD | 확장 후 트리 노드 수가 이 값 이하로 줄면 다시 리스트로 | 6 |
2. put과 get의 흐름
key.hashCode()를 구한다.- 상위 16비트를 하위 16비트에 섞는다:
hash = h ^ (h >>> 16). 배열 크기가 작으면 인덱스 계산에 하위 비트만 쓰이므로, 상위 비트 정보도 반영하려는 것이다. - 인덱스를 구한다:
index = (n - 1) & hash. n이 2의 거듭제곱이라 나머지 연산(%)과 같은 결과를 비트 연산으로 빠르게 얻는다. - 그 버킷의 노드를 차례로 보며 해시값이 같고
equals()가 true인 키를 찾는다. - put이면 찾은 노드의 값을 바꾸거나, 없으면 새 노드를 추가한다. 원소 수가 threshold를 넘으면 배열을 2배로 늘리고 노드를 재배치한다.
null 키는 해시를 0으로 취급해 0번 버킷에 저장한다. 그래서 HashMap은 null 키를 하나 가질 수 있다.
3. 해시 충돌 처리 방식
| 방식 | 동작 | 장점 | 단점 | 사용 예 |
| 체이닝 (Separate Chaining) | 같은 버킷의 원소를 연결 리스트(또는 트리)로 연결 | 구현 단순, load factor가 높아도 동작 | 노드마다 추가 메모리, 포인터 따라가기 | Java HashMap |
| 개방 주소법 (Open Addressing) | 충돌하면 비어 있는 다른 칸을 찾아 저장 (선형·이차 탐사, 이중 해싱) | 배열 하나라 캐시 효율이 좋음 | 삭제 처리가 까다롭고, 꽉 찰수록 급격히 느려짐 | Python dict 등 |
4. 자바 8의 트리화
모든 키가 같은 버킷에 몰리면 체이닝 리스트를 끝까지 훑어야 해서 O(n)이 된다. 공격자가 일부러 충돌하는 키를 대량으로 보내는 해시 DoS도 이 점을 노린다. 자바 8부터는 한 버킷의 노드가 8개를 넘고 배열 크기가 64 이상이면 그 버킷을 레드-블랙 트리로 바꿔 최악의 탐색을 O(log n)으로 제한한다.
정상적인 해시 함수라면 한 버킷에 8개가 쌓일 확률은 극히 낮다. 트리화는 평소 성능을 위한 것이 아니라 나쁜 해시나 의도적 충돌에 대한 안전장치다.
5. equals와 hashCode 규약
| 규칙 | 의미 |
| equals가 true면 hashCode도 같아야 한다 | 필수. 어기면 같은 키를 다른 버킷에서 찾게 됨 |
| hashCode가 같아도 equals는 false일 수 있다 | 이것이 해시 충돌. 허용되지만 많으면 느려짐 |
| equals에 쓰는 필드가 바뀌지 않는 한 hashCode는 일관돼야 한다 | 같은 객체가 매번 다른 버킷을 가리키면 안 됨 |
class Member {
private final String email;
Member(String email) { this.email = email; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Member)) return false;
return email.equals(((Member) o).email);
}
// hashCode를 재정의하지 않으면?
}
Map<Member, Integer> points = new HashMap<>();
points.put(new Member("a@b.com"), 100);
points.get(new Member("a@b.com")); // null — 기본 hashCode가 달라 다른 버킷을 봄
equals만 재정의하면 논리적으로 같은 두 객체가 Object의 기본 hashCode(객체마다 다름)를 써서 다른 버킷으로 간다. @Override public int hashCode() { return Objects.hash(email); }를 함께 정의해야 찾을 수 있다. 자바의 record는 모든 필드 기준으로 둘을 자동 생성한다.
6. 가변 객체를 키로 쓰면 안 되는 이유
List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "value");
key.add("b"); // 키의 내용(=hashCode)이 바뀜
map.get(key); // null — 저장할 때와 다른 버킷을 찾는다
map.containsKey(key); // false, 하지만 map.size()는 1
키는 String, Integer, record처럼 불변 객체를 쓴다. 불변 객체는 hashCode를 캐시할 수도 있다(String이 그렇다).
7. 스레드 안전성
| 구현체 | 동기화 | null 키·값 | 비고 |
| HashMap | 없음 | 키 1개, 값 여러 개 허용 | 단일 스레드 또는 읽기 전용 공유 |
| Hashtable | 모든 메서드 synchronized | 불가 | 레거시 |
| Collections.synchronizedMap | 맵 전체에 락 하나 | 원본 따름 | 순회 시 직접 동기화 필요 |
| ConcurrentHashMap | 버킷 단위 락 + CAS | 불가 | 멀티스레드 기본 선택 |
HashMap을 여러 스레드가 동시에 수정하면 데이터가 유실되거나 크기가 틀어질 수 있다. 자바 7까지는 확장 중 리스트가 순환 구조가 돼 무한 루프에 빠지는 문제도 알려져 있었다. 동시 수정이 있으면 ConcurrentHashMap을 쓴다.
8. 실제로 어떻게 적용되나
- 초기 용량 지정: 넣을 개수를 미리 안다면
new HashMap<>(expected / 0.75f + 1)처럼 잡아 확장과 재배치를 줄인다. 수십 개 수준이면 신경 쓸 필요 없다. - DTO를 키로 쓸 때: 상품 ID와 옵션 ID 조합으로 그룹핑하려고 키 클래스를 만들었다면
equals·hashCode를 반드시 함께 정의하거나record로 만든다. 롬복이라면@EqualsAndHashCode나@Value를 쓴다. - JPA 엔티티의 equals: 영속화 전에는 ID가 null이었다가 저장 후 채워지는 엔티티를 ID 기준
hashCode로HashSet에 넣으면, 저장 후 해시가 바뀌어 찾지 못할 수 있다. 엔티티의 동등성 기준은 신중하게 정한다.
9. 면접 질문으로 정리
- Q. HashMap의 동작 원리는? 키의 hashCode로 버킷 인덱스를 계산해 배열에 저장하고, 같은 버킷 안에서는 equals로 키를 찾는다. 평균 O(1)이고, 원소 수가 capacity × 0.75를 넘으면 배열을 2배로 늘린다.
- Q. 해시 충돌은 어떻게 처리하나? 자바 HashMap은 같은 버킷의 노드를 연결 리스트로 잇는 체이닝을 쓰고, 한 버킷이 8개를 넘고 배열이 64 이상이면 레드-블랙 트리로 바꿔 O(log n)을 보장한다.
- Q. equals와 hashCode를 같이 재정의해야 하는 이유는? equals가 같은 두 객체는 hashCode도 같아야 같은 버킷에서 찾을 수 있다. equals만 재정의하면 HashMap이나 HashSet에서 같은 키를 찾지 못한다.
- Q. load factor가 0.75인 이유는? 너무 낮으면 메모리를 낭비하고 너무 높으면 충돌이 늘어난다. 0.75는 시간과 공간 사이의 절충값이다.
- Q. HashMap과 ConcurrentHashMap의 차이는? HashMap은 동기화가 없어 동시 수정 시 데이터가 깨질 수 있고, ConcurrentHashMap은 버킷 단위 락과 CAS로 스레드 안전성을 보장하며 null 키·값을 허용하지 않는다.