dpdpdndn 블로그

[Java] Map 내부 구조와 구현체 선택

NEW7 min read

[Java] Map 내부 구조와 구현체 선택

개요

Map의 핵심은 해시 함수와 배열 인덱싱이다. key의 hashCode()를 계산해 배열의 특정 인덱스로 변환하고, 그 인덱스에 값을 저장한다. 배열 원소를 찾는 공식(시작 주소에 인덱스와 원소 하나의 크기를 곱한 값을 더한 것)은 인덱스만 알면 곧바로 위치를 계산할 수 있어 O(1) 조회가 가능해진다.

키워드의미주의가 필요한 지점
hash에서 index로key 의 hashCode 를 배열 인덱스로 변환비트 확산 없이 인덱스를 계산한다고 오해
로드 팩터버킷이 얼마나 차면 리사이즈할지 정하는 임계값(기본 0.75)대량 데이터를 넣을 걸 알면서 초기 용량을 지정하지 않음
트리화한 버킷의 충돌 노드가 8개 이상이면 Red-Black Tree 로 전환equals/hashCode 미구현으로 충돌이 특정 버킷에 몰림
구현체 선택HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap멀티스레드 환경에서 HashMap 을 그대로 공유

Map이란 무엇인가

Map은 key-value쌍의 집합이다. key는 중복을 허용하지 않고, key로부터 해시 함수를 거쳐 배열 인덱스를 계산한 뒤 그 인덱스에 value를 저장한다.

원소 주소는 배열 시작 주소에 인덱스와 원소 하나의 크기를 곱한 값을 더한 것이다. 시작 주소가 1000, 인덱스가 10, 원소 크기가 4바이트라면 1000 + 10 * 4 = 1040으로 곧바로 위치를 계산할 수 있다.

PUT 동작: hash에서 인덱스까지

HashMap에 key, value를 저장하는 과정은 네 단계로 진행된다.

  1. key의 hashCode()를 호출해 해시값을 얻는다.
  2. 상위 16비트를 하위 비트와 XOR(Exclusive OR)하는 비트 확산(spread) 을 한 번 더 거쳐 분포를 균일하게 만든다.
  3. (테이블 크기 n - 1) & hash 로 배열 인덱스를 계산한다.
  4. 해당 인덱스 버킷에 노드를 저장한다.

비트 확산이 필요한 이유는 테이블 크기 n이 기본적으로 16, 32처럼 작은 2의 거듭제곱이기 때문이다. n - 1의 이진수는 하위 몇 비트만 1이므로, (n-1) & hash 연산은 결국 hash 값의 하위 비트만 본다. hashCode() 가 상위 비트에서만 차이를 만드는 값이라면 하위 비트가 같아 서로 다른 key가 같은 인덱스로 몰릴 수 있다. HashMap.hash() 는 h ^ (h >>> 16) 로 상위 16비트를 하위 비트에 섞어 넣어 이 문제를 줄인다.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(n - 1) & hash는 hash % n 과 동등한 값을 내지만 비트 연산이라 나눗셈보다 훨씬 빠르다. 이 트릭이 성립하려면 n이 반드시 2의 거듭제곱이어야 하므로, HashMap은 사용자가 지정한 초기 용량을 항상 가장 가까운 2의 거듭제곱으로 올림한다.

해시 충돌과 트리화

서로 다른 key의 해시 결과가 같은 인덱스로 몰리는 경우가 해시 충돌이다. HashMap은 충돌을 LinkedList로 해결한다. 같은 인덱스에 들어가는 노드들을 next 포인터로 연결한다.

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

LinkedList 순회는 최악의 경우 O(n)이다. 특정 버킷에 key가 몰리면 사실상 LinkedList가 되어 조회 성능이 안좋아진다. 자바 8부터 HashMap은 한 버킷의 노드 개수가 TREEIFY_THRESHOLD(8) 이상이 되면 LinkedList를 Red-Black Tree로 전환한다.

트리로 전환되면 같은 버킷 안에서도 O(log n)으로 조회할 수 있다. 반대로 노드 수가 UNTREEIFY_THRESHOLD(6) 이하로 줄면 다시 LinkedList로 되돌아간다.

GET 동작과 equals, hashCode

  1. key의 hash()로 인덱스를 계산한다.
  2. 해당 인덱스 버킷의 첫 노드부터 key를 비교한다. hashCode가 같고 equals()가 true인 노드를 찾을 때까지 탐색한다.

HashMap은 먼저 hashCode()로 인덱스를 찾고, 그다음 같은 버킷 안에서 equals()로 비교한다. equals()만 오버라이드하고 hashCode()를 그대로 두면, 논리적으로 같다고 판단해야 할 두 객체가 서로 다른 버킷에 들어가 영원히 만나지 못한다.

// 잘못된 패턴: equals 만 오버라이드
class User {
    String id;
 
    @Override
    public boolean equals(Object o) {
        return o instanceof User u && u.id.equals(this.id);
    }
    // hashCode() 미구현. Object 기본 구현(객체 식별자 기반)이 그대로 남는다
}
 
Map<User, String> map = new HashMap<>();
map.put(new User("a"), "value");
map.get(new User("a"));  // null. 두 User("a") 인스턴스의 hashCode 가 달라 다른 버킷에 들어갔다
 
// 올바른 패턴: equals 와 hashCode 를 함께 오버라이드
class User {
    String id;
 
    @Override
    public boolean equals(Object o) {
        return o instanceof User u && u.id.equals(this.id);
    }
 
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

그래프 뷰