GM 오락실
← 개인 공부 · Java
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
thresholdcapacity × load factor. 원소 수가 이를 넘으면 배열을 2배로 확장12
TREEIFY_THRESHOLD노드가 이 값 이상인 버킷에 또 추가되면 트리 변환 검토8
MIN_TREEIFY_CAPACITY트리화하려면 배열 크기가 최소 이 값이어야 함 (작으면 대신 확장)64
UNTREEIFY_THRESHOLD확장 후 트리 노드 수가 이 값 이하로 줄면 다시 리스트로6

2. put과 get의 흐름

  1. key.hashCode()를 구한다.
  2. 상위 16비트를 하위 16비트에 섞는다: hash = h ^ (h >>> 16). 배열 크기가 작으면 인덱스 계산에 하위 비트만 쓰이므로, 상위 비트 정보도 반영하려는 것이다.
  3. 인덱스를 구한다: index = (n - 1) & hash. n이 2의 거듭제곱이라 나머지 연산(%)과 같은 결과를 비트 연산으로 빠르게 얻는다.
  4. 그 버킷의 노드를 차례로 보며 해시값이 같고 equals()가 true인 키를 찾는다.
  5. 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. 실제로 어떻게 적용되나

  1. 초기 용량 지정: 넣을 개수를 미리 안다면 new HashMap<>(expected / 0.75f + 1)처럼 잡아 확장과 재배치를 줄인다. 수십 개 수준이면 신경 쓸 필요 없다.
  2. DTO를 키로 쓸 때: 상품 ID와 옵션 ID 조합으로 그룹핑하려고 키 클래스를 만들었다면 equals·hashCode를 반드시 함께 정의하거나 record로 만든다. 롬복이라면 @EqualsAndHashCode나 @Value를 쓴다.
  3. JPA 엔티티의 equals: 영속화 전에는 ID가 null이었다가 저장 후 채워지는 엔티티를 ID 기준 hashCode로 HashSet에 넣으면, 저장 후 해시가 바뀌어 찾지 못할 수 있다. 엔티티의 동등성 기준은 신중하게 정한다.

9. 면접 질문으로 정리

  1. Q. HashMap의 동작 원리는? 키의 hashCode로 버킷 인덱스를 계산해 배열에 저장하고, 같은 버킷 안에서는 equals로 키를 찾는다. 평균 O(1)이고, 원소 수가 capacity × 0.75를 넘으면 배열을 2배로 늘린다.
  2. Q. 해시 충돌은 어떻게 처리하나? 자바 HashMap은 같은 버킷의 노드를 연결 리스트로 잇는 체이닝을 쓰고, 한 버킷이 8개를 넘고 배열이 64 이상이면 레드-블랙 트리로 바꿔 O(log n)을 보장한다.
  3. Q. equals와 hashCode를 같이 재정의해야 하는 이유는? equals가 같은 두 객체는 hashCode도 같아야 같은 버킷에서 찾을 수 있다. equals만 재정의하면 HashMap이나 HashSet에서 같은 키를 찾지 못한다.
  4. Q. load factor가 0.75인 이유는? 너무 낮으면 메모리를 낭비하고 너무 높으면 충돌이 늘어난다. 0.75는 시간과 공간 사이의 절충값이다.
  5. Q. HashMap과 ConcurrentHashMap의 차이는? HashMap은 동기화가 없어 동시 수정 시 데이터가 깨질 수 있고, ConcurrentHashMap은 버킷 단위 락과 CAS로 스레드 안전성을 보장하며 null 키·값을 허용하지 않는다.
Gunmo Lee
since 2021.07
HashMap 동작 원리 정리: 해시 충돌, 체이닝, 트리화, equals와 hashCode 규약 | GM 오락실