[Java] HashMap 은 뭐고 어떻게 동작 하는 걸까?

HashMap은 Java를 쓰다 보면 자연스럽게 자주 마주치는 자료구조다. 회사 프로젝트 진행 중에 WebSocket 프록시 서버를 구현할 일이 있었는데, 브라우저 클라이언트 세션과 외부 CCTV 스트리밍 서버 쪽 세션을 1:1로 매핑해서 보관해야 하는 상황이었다.

처음에는 HashMap을 쓰려고 했는데, WebSocket 특성상 여러 클라이언트가 동시에 연결되고 끊기는 일이 발생하다 보니 멀티스레드 환경에서 HashMap을 그냥 쓰면 안 된다는 걸 알게 됐다. 결국 ConcurrentHashMap을 썼는데, 정작 HashMap 자체를 제대로 정리한 적이 없다는 생각이 들어서 이번 기회에 HashMap부터 차근차근 정리해보려 한다.

---

HashMap을 쓰는 이유

단순하다. 조회가 빠르다.

리스트에서 원하는 값을 찾으려면 처음부터 하나씩 돌아야 한다. 데이터가 만 개면 최악의 경우 만 번 비교한다. O(n).

// 리스트 - O(n)
for (User user : users) {
    if (user.getId().equals(targetId)) { ... }
}

// HashMap - O(1)
User user = userMap.get(targetId);

HashMap은 Key만 알면 데이터 수에 상관없이 거의 즉시 꺼낼 수 있다. 그 이유가 내부 구조에 있다.

---

내부 구조: 배열 + 연결리스트

HashMap 내부는 Node<K,V> 배열이다. 이 배열의 각 칸을 버킷(bucket) 이라고 부른다.

// HashMap 내부 (JDK 소스)
transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // 충돌 시 연결리스트로 이어짐
}

put("userId", "kwanghyuk")을 호출하면 내부에서 이런 순서로 동작한다.

1. "userId".hashCode() 계산
2. 내부 hash() 함수로 한 번 더 가공
3. 배열 인덱스 결정
4. 해당 버킷에 Node 저장

버킷 배열 (기본 크기 16)
┌─────┬─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │ ... │ 15  │
└─────┴─────┴──┬──┴─────┴─────┴─────┘
               │
               └─ Node { hash, "userId", "kwanghyuk", next=null }

get("userId")도 마찬가지다. "userId"의 해시를 계산해서 인덱스를 구하고, 그 버킷에 바로 접근한다. 배열 인덱스 접근이니까 O(1)이 나오는 것.

---

hash() 함수가 하는 일

Java의 모든 객체는 hashCode()를 가진다. HashMap은 이걸 그대로 쓰지 않고 내부 hash() 함수로 한 번 가공한다.

// JDK 내부 hash() 함수
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

hashCode()의 상위 16비트를 하위 16비트에 XOR 연산한다. hashCode 값이 배열 크기보다 훨씬 클 때 하위 비트만 쓰면 충돌이 많아지기 때문에 비트를 섞어서 충돌 확률을 낮추는 것이다.

 

 

---

해시 충돌과 처리 방식

두 키의 해시가 같은 인덱스로 떨어지면 해시 충돌(Hash Collision) 이 발생한다. HashMap은 이걸 Chaining 방식으로 처리한다. 같은 버킷에 연결리스트로 이어 붙이는 것.

버킷[2]
  └─ Node { "userId", "kwanghyuk" }
       └─ Node { "nickname", "fkqlaus" }  ← 충돌, 체이닝으로 연결

조회할 때도 체이닝이 있으면 연결리스트를 순회해서 Key가 일치하는 노드를 찾는다. 충돌이 많아질수록 리스트가 길어지고 최악의 경우 O(n)까지 떨어진다. O(1)이라고 믿었던 HashMap이 O(n)이 되는 첫 번째 케이스다.

Java 8부터 달라진 점이 있다? : 트리화

Java 8 이전까지는 충돌이 아무리 많아도 그냥 연결리스트였다고 한다. 알아보니까 Java 8부터 한 버킷의 체이닝이 8개를 넘으면 자동으로 Red-Black Tree로 전환된다.

static final int TREEIFY_THRESHOLD = 8;   // 이 이상이면 트리로 전환
static final int UNTREEIFY_THRESHOLD = 6; // 이 이하면 다시 리스트로

충돌 적을 때 (< 8)      충돌 많을 때 (>= 8)
버킷[2]                  버킷[2]
  └─ A                     └─ (Red-Black Tree)
       └─ B                        A
            └─ C               B       C
O(n) 조회                  O(log n) 조회

 

---

resize와 load factor

기본 capacity는 16이다. 데이터가 계속 들어오면 언젠가 꽉 차는데, 이걸 방지하려고 load factor라는 임계치가 있다. 기본값은 0.75.

load factor = 현재 데이터 수 / 배열 크기

capacity 16, load factor 0.75
→ 16 * 0.75 = 12
→ 데이터가 12개 들어오는 순간 resize 발생

resize가 일어나면 배열 크기를 2배로 늘리고, 기존 데이터를 전부 새 배열로 옮긴다. 이 과정을 rehashing이라고 한다. 모든 데이터를 다시 해싱해서 새 인덱스를 계산하고 옮기는 거라 비용이 크다.

초기에 들어올 데이터 크기를 어느 정도 예측할 수 있다면 capacity를 미리 지정해두는 게 성능에 유리하다.

// 데이터가 1000개 들어올 예정이라면
// 1000 / 0.75 ≈ 1334 → 올림해서 2의 거듭제곱인 2048로 지정
Map<String, String> map = new HashMap<>(2048);

load factor를 낮추면 충돌은 줄지만 메모리를 더 쓰고 resize가 자주 일어난다. 높이면 메모리는 아끼지만 충돌이 늘어서 성능이 나빠진다. 0.75는 그 트레이드오프에서 나온 기본값이다.

---

주요 특성

지금까지 내부 동작을 보면서 이미 특성이 대부분 나왔는데, 한 번에 정리하면 이렇다.

순서를 보장하지 않는다. 버킷 인덱스 기준으로 저장되기 때문에 삽입 순서가 유지되지 않는다. 순서가 필요하면 LinkedHashMap을 쓴다.

null을 허용한다. Key는 null 1개, Value는 null 여러 개 허용한다. Key가 null이면 항상 버킷 0에 들어간다.

thread-safe하지 않다. 멀티스레드 환경에서 HashMap을 공유하면 데이터 유실이 생기거나 Java 8 이전에는 resize 중에 실제로 무한루프 버그가 있었다. 멀티스레드 환경에서는 ConcurrentHashMap을 써야 한다.

// 멀티스레드 환경
Map<String, String> map = new ConcurrentHashMap<>();

Collections.synchronizedMap()도 있지만 ConcurrentHashMap이 성능이 낫다. synchronizedMap은 Map 전체를 잠그지만, ConcurrentHashMap은 버킷 단위로 잠그기 때문이다.

---

O(1)이 보장되는 조건, O(n)이 되는 경우

O(1)이 나오려면 hashCode()가 데이터를 버킷에 골고루 분산시켜줘야 한다. 충돌이 적어야 한다는 뜻이다.

O(n)이 되는 경우는 이렇다.

hashCode()를 잘못 구현해서 모든 키가 같은 해시값을 반환하면 HashMap이 사실상 연결리스트가 된다.

@Override
public int hashCode() {
    return 1;  // 모든 키가 같은 버킷 → O(n)
}

이런 극단적인 경우는 없더라도, hashCode()와 equals()를 잘못 구현한 객체를 Key로 쓰면 비슷한 상황이 생긴다. Key로 사용할 클래스는 hashCode()와 equals()를 반드시 함께 재정의해야 한다.

또 하나는 mutable 객체를 Key로 쓰는 경우다. HashMap에 저장한 후 Key 객체의 내부 값이 바뀌면 hashCode가 달라져서 꺼낼 수 없게 된다.

List<String> key = new ArrayList<>(Arrays.asList("a"));
map.put(key, "value");

key.add("b");  // Key 변경!
map.get(key);  // null 반환 - hashCode가 바뀌었기 때문

Key는 String, Integer처럼 불변 객체를 쓰는 게 원칙이다!!

---

어떤 걸 구현할 때 자주 쓰는가

실제로 코드 짜다 보면 HashMap이 자연스럽게 손에 잡히는 상황들이 있다.

가장 흔한 건 중복 체크다. 어떤 값이 이미 나왔는지 확인할 때 리스트로 하면 매번 순회해야 하는데, HashMap에 넣어두면 containsKey()로 O(1)에 끝난다.

Map<String, Boolean> visited = new HashMap<>();
visited.put("user1", true);

System.out.println(visited.containsKey("user1")); // true
System.out.println(visited.containsKey("user2")); // false

빈도 카운팅도 자주 쓴다. 문자열에서 각 문자가 몇 번 나왔는지, 투표 결과 집계처럼 특정 값이 몇 번 등장했는지 셀 때.

String[] votes = {"A", "B", "A", "C", "B", "A"};

Map<String, Integer> count = new HashMap<>();
for (String vote : votes) {
    count.put(vote, count.getOrDefault(vote, 0) + 1);
}

System.out.println(count); // {A=3, B=2, C=1}

Key로 빠르게 조회하는 것도 단골 패턴이다. 유저 ID로 유저 정보 꺼내기, 상품 코드로 상품 정보 꺼내기처럼 리스트를 순회하지 않고 바로 찾아야 할 때.

Map<String, String> userMap = new HashMap<>();
userMap.put("user1", "김철수");
userMap.put("user2", "이영희");

System.out.println(userMap.get("user1")); // 김철수
System.out.println(userMap.get("user3")); // null

그룹핑도 있다. 같은 조건을 가진 데이터들을 묶을 때 Map<Key, List<Value>> 형태로 쓴다. 같은 학년 학생 묶기, 같은 카테고리 상품 묶기 같은 것들.

// computeIfAbsent: 해당 Key가 없으면 빈 리스트 만들고, 있으면 기존 리스트에 바로 add
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent("1학년", k -> new ArrayList<>()).add("김철수");
groups.computeIfAbsent("2학년", k -> new ArrayList<>()).add("이영희");
groups.computeIfAbsent("1학년", k -> new ArrayList<>()).add("박민준");

System.out.println(groups);
// {1학년=[김철수, 박민준], 2학년=[이영희]}

 

중복 체크, 빈도 카운팅, Key 기반 조회, 그룹핑. 이 네 가지 중 하나에 해당하면 HashMap부터 떠올리면 될 것 같다!

---

정리

개념 핵심

내부 구조	Node 배열(버킷) + 연결리스트/Red-Black Tree
해시 충돌 처리	Chaining, 버킷당 8개 초과 시 트리 전환
resize 비용	전체 rehashing — 초기 capacity 지정으로 줄일 수 있음
O(1) 조건	hashCode()가 충돌 없이 잘 분산될 때
thread-safe	멀티스레드 환경에서는 사용 금지
주사용환경	중복체크, 빈도 카운팅, Key 기반 조회, 그룹핑 등

 

---

다음 글에서는 HashMap의 형제들을 비교 해볼까 한다. LinkedHashMap, TreeMap, ConcurrentHashMap이 HashMap 대비 뭘 추가했고 언제 어떤 걸 선택해야 하는지. HashMap 내부를 이해하고 나면 나머지는 "HashMap에 이런 특성을 얹었다" 정도로 파악하면 되려나.. 필요할 때 잘 써먹으려고 정리해본다!