Java HashMap 동작 원리와 함정 — 해시 충돌부터 equals/hashCode 계약까지

Java 17 기준으로 HashMap의 버킷 구조, 해시 충돌 처리, equals/hashCode 계약을 실무 관점에서 정리하고 TreeMap과 선택 기준까지 비교합니다.

 

HashMap에 넣어둔 값을 분명히 꺼내야 하는데 get()이 null을 돌려주거나, 특정 상황에서 성능이 갑자기 나빠진 경험이 있으실 수 있어요. “키가 같은데 왜 못 찾지?”, “HashMap은 항상 O(1) 아닌가요?” 같은 질문이 딱 이 지점에서 나옵니다.
이번 글에서는 HashMap이 내부에서 어떻게 동작하는지와, 실무에서 자주 밟는 함정을 함께 정리해 볼게요.

핵심 개념 (Java HashMap 동작 원리, 해시 충돌, equals/hashCode 계약)

HashMap 버킷 배열과 해시 충돌 시 체이닝 및 트리화 개념 다이어그램

HashMap을 “서랍장”에 비유하면 이해가 쉬워요. 키를 해시 함수로 계산해 “몇 번째 서랍(버킷)”에 넣을지 정하고, 그 서랍 안에서 실제로 같은 키인지(equals)를 확인해 값을 찾습니다. 즉, HashMap 조회는 (1) 해시로 버킷 선택 → (2) 버킷 내부에서 equals로 최종 매칭의 2단계예요.

Java HashMap의 버킷과 해시 충돌 처리

HashMap은 내부적으로 Node<K,V>[] table 같은 배열(버킷 배열)을 두고, 인덱스는 대략 아래처럼 결정됩니다.

• hash = spread(key.hashCode()) (비트 섞기)
• index = (table.length - 1) & hash (길이가 2의 거듭제곱일 때 빠른 인덱싱)

서로 다른 키라도 해시 결과가 같은 버킷으로 떨어질 수 있는데, 이게 해시 충돌입니다. 충돌이 나면 그 버킷 안에서 여러 엔트리를 이어 붙여(기본은 연결 리스트 형태) equals로 하나씩 비교합니다.

Java 8+ (따라서 Java 17) HashMap은 충돌이 심해져서 버킷 내부 엔트리가 많아지면, 최악의 O(n)을 줄이기 위해 **버킷을 트리(레드-블랙 트리)로 바꾸는 “treeify”**를 합니다. 다만 무조건 트리로 바뀌는 건 아니고, 테이블이 충분히 커야 하고(일정 용량 이상), 버킷 내 엔트리 수가 임계치를 넘어야 합니다. 핵심은 이거예요:

• 충돌이 적으면: 평균적으로 빠름(상수 시간에 가까움)
• 충돌이 많으면: 버킷 내부 비교 비용이 커짐(리스트 → 트리로 완화)

equals/hashCode 계약이 중요한 이유

HashMap의 “같은 키”는 결국 equals로 결정됩니다. 그런데 버킷 선택은 hashCode로 하죠.
따라서 다음 계약을 깨면 HashMap은 논리적으로 “같은 키”를 다른 서랍에 넣어버릴 수 있습니다.

equals/hashCode 계약(필수)

1. a.equals(b) == true 이면 a.hashCode() == b.hashCode() 여야 합니다.
2. hashCode는 가능하면 분산이 좋아야 합니다(충돌이 적어야 성능이 좋아요).
3. 키로 쓰는 객체는 불변(immutable) 이거나, 적어도 Map에 넣은 뒤 equals/hashCode에 영향을 주는 필드가 바뀌면 안 됩니다.

실무에서 가장 흔한 사고는 이거예요:

• 키 객체를 Map에 넣은 뒤, 키의 필드를 변경
• 그 필드가 hashCode() 계산에 포함되어 버킷 위치가 달라짐
• 결과: get()이 못 찾음(“분명 넣었는데…”)

TreeMap과의 비교: 언제 HashMap이 아닌 TreeMap인가

TreeMap은 해시가 아니라 정렬(Comparable/Comparator) 기반의 트리(Map 전체가 정렬 상태)입니다. 그래서 다음 특성이 있어요.

• get/put/remove는 평균/최악 모두 O(log n)
• 키 순서가 필요하면 TreeMap이 자연스러운 선택
• “같은 키”의 기준이 equals가 아니라 compare 결과(0) 와 더 강하게 연결됨(Comparator가 equals와 불일치하면 혼란)

아래 표로 선택 기준을 빠르게 정리해 볼게요.

항목	HashMap	TreeMap
정렬 보장	X	O (키 정렬)
평균 성능	O(1)	O(log n)
최악 성능	충돌 심하면 비용 증가(트리화로 완화)	O(log n)
동일 키 판정	equals	compare(a,b)==0
사용 시점	빠른 조회/저장, 정렬 불필요	정렬된 순회, 범위 검색(subMap) 필요

flowchart TD
  A["key.hashCode()"] --> B["hash spread"]
  B --> C["index = (n-1) & hash"]
  C --> D["bucket 선택"]
  D --> E["bucket 내부에서 equals 비교"]
  E --> F["value 반환 또는 삽입/갱신"]

HashMap 조회/삽입은 “해시로 버킷 선택 → equals로 최종 확인” 흐름으로 동작합니다.

 

코드 예제 (복붙 실행: 충돌/계약 위반/TreeMap 비교)

아래 코드는 3가지를 한 번에 보여줍니다.

1. equals/hashCode를 올바르게 구현한 키는 정상 동작
2. 키를 가변 객체로 만들어 hashCode에 쓰는 필드를 바꾸면 get()이 실패
3. TreeMap은 정렬 순회가 가능하고, Comparator 기준으로 동작

import java.util.*;

public class HashMapPitfallsDemo {

    // 올바른 키: 불변 + equals/hashCode 일관성
    static final class GoodKey {
        private final String id;

        GoodKey(String id) { this.id = id; }

        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof GoodKey)) return false;
            GoodKey goodKey = (GoodKey) o;
            return Objects.equals(id, goodKey.id);
        }

        @Override public int hashCode() {
            return Objects.hash(id);
        }

        @Override public String toString() { return "GoodKey{id='" + id + "'}"; }
    }

    // 위험한 키: 가변 + hashCode/equals에 사용되는 필드가 바뀜
    static final class MutableKey {
        private String id;

        MutableKey(String id) { this.id = id; }

        void setId(String id) { this.id = id; }

        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof MutableKey)) return false;
            MutableKey that = (MutableKey) o;
            return Objects.equals(id, that.id);
        }

        @Override public int hashCode() {
            return Objects.hash(id);
        }

        @Override public String toString() { return "MutableKey{id='" + id + "'}"; }
    }

    // 충돌 유도용 키: hashCode를 상수로 만들어 모두 같은 버킷으로 몰리게 함(나쁜 예)
    static final class CollidingKey {
        private final String id;

        CollidingKey(String id) { this.id = id; }

        @Override public int hashCode() { return 42; } // 의도적 충돌
        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof CollidingKey)) return false;
            CollidingKey that = (CollidingKey) o;
            return Objects.equals(id, that.id);
        }
    }

    public static void main(String[] args) {
        // 1) 정상 동작
        Map<GoodKey, String> goodMap = new HashMap<>();
        goodMap.put(new GoodKey("A"), "value-A");
        System.out.println("GoodKey get: " + goodMap.get(new GoodKey("A"))); // value-A

        // 2) 키를 변경하면 못 찾는 함정
        Map<MutableKey, String> mutableMap = new HashMap<>();
        MutableKey k = new MutableKey("A");
        mutableMap.put(k, "value-A");

        System.out.println("Before mutate get: " + mutableMap.get(new MutableKey("A"))); // value-A

        k.setId("B"); // hashCode/equals가 바뀌어 버킷 위치가 달라짐
        System.out.println("After mutate get by same instance: " + mutableMap.get(k)); // null 가능
        System.out.println("After mutate get by new key(A): " + mutableMap.get(new MutableKey("A"))); // null

        // 3) 충돌이 많아지면 성능 비용이 증가(개념 시연)
        Map<CollidingKey, Integer> collisionMap = new HashMap<>();
        for (int i = 0; i < 50_000; i++) {
            collisionMap.put(new CollidingKey("K" + i), i);
        }
        System.out.println("Collision map size: " + collisionMap.size());

        // 4) TreeMap: 정렬된 순회 + 범위 조회에 강점
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("banana", 2);
        treeMap.put("apple", 1);
        treeMap.put("cherry", 3);

        System.out.println("TreeMap iteration (sorted): " + treeMap); // {apple=1, banana=2, cherry=3}

        NavigableMap<String, Integer> range = ((TreeMap<String, Integer>) treeMap).subMap("banana", true, "cherry", true);
        System.out.println("TreeMap range [banana..cherry]: " + range); // {banana=2, cherry=3}
    }
}

실무 팁

💡 실무에서는: “키는 불변으로 만들고, record를 적극 고려해요”
Java 17에서는 키를 record로 만들면 불변 + equals/hashCode 자동 생성이라 실수가 크게 줄어듭니다. 특히 DTO를 그대로 키로 쓰는 상황에서 “나중에 필드 추가/변경”이 잦다면, 가변 클래스로 키를 쓰는 순간부터 장애 포인트가 됩니다.

💡 실무에서는: “HashMap 초기 용량을 대충이라도 잡아두면 리사이즈 비용이 줄어요”
대량 데이터를 한 번에 넣는다면 기본 생성자 대신 new HashMap<>(expectedSize * 4 / 3 + 1)처럼 예상 크기를 반영해 보세요. 리사이즈(재해싱) 자체가 틀린 건 아니지만, 트래픽이 몰리는 구간에서 불필요한 CPU 스파이크 원인이 되기도 합니다.

---

핵심 요약: HashMap은 해시로 버킷을 고르고 equals로 최종 매칭합니다.
핵심 요약: equals/hashCode 계약을 깨거나 키를 변경하면 “넣었는데 못 찾는” 문제가 생깁니다.
핵심 요약: 정렬/범위 조회가 필요하면 HashMap 대신 TreeMap을 선택해 보세요.

다음 글: #15 Collections 유틸 활용 팁