Java의 HashMap

📌 해시란 무엇인지, 해시 충돌은 왜 일어나고 어떻게 방지할 수 있는지 알고 있어야 한다. 잘 모른다면 이 글을 읽고 돌아오는 것을 추천한다.

Java의 HashMap에서 사용하는 방식은 Separate Chaining이다. Open Addressing 대신 Separate Chaining을 사용하는 이유는 크게 두 가지이다.

• HashMap에서 remove()는 빈번하게 호출될 수 있는 메서드인데, Open Addressing은 데이터 삭제 연산을 효율적으로 처리하기 어렵다. Link
• Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아지지만 Separate Chaining은 보조 해시 함수를 이용해 Worst Case 발생 상황을 줄일 수 있다.

Java 7과 Java 8에서 HashMap이 어떻게 구현되었는지 살펴보자.

Java 7

아래는 Java 7 HashMap의 put() 메서드 구현부이다.

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {  
        inflateTable(threshold);    // table 배열 생성
    }
    if (key == null)   // null을 키로 사용한 경우
        return putForNullKey(value);

    // hashCode()를 사용하는 것이 아니라 보조 해시 함수를 이용하는 변형된 해시 함수를 사용한다.    
    int hash = hash(key);    

    // i 값이 해시 버킷의 인덱스이다.
    // indexFor()는 hash % table.length와 같은 의도의 메서드이다.
    int i = indexFor(hash, table.length);

    // 해시 버킷에 있는 Linked List를 순회한다.
    // 만약 같은 키가 이미 저장되어 있다면 교체한다.
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

     modCount++;

    // 버킷의 마지막 Entry 참조값, key, value, hash를 저장하는 새로운 Entry를 생성해 저장한다. 
    addEntry(hash, key, value, i);
    return null;
}

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

    // ... 
}

여기서 몇 가지 중요한 부분을 짚고 넘어가면,

• hashCode()를 사용하는 것이 아니라 hash()라는 변형된 해시 함수를 사용한다.
• 해시 버킷의 인덱스는 hash % table.length와 같이 계산한다.
• Entry 클래스를 통해 Linked List 구조를 이룬다.

put() 메서드를 충분히 이해했다면 아래 코드를 실행시켰을 때 어떤 결과가 나올지 예측해보자.

public static void main(String[] args) {

    HashMap<Book, String> map = new HashMap<>();
    Book book1 = new Book(1, "오브젝트");
    Book book2 = new Book(1, "객체 지향의 사실과 오해");
    Book book3 = new Book(2, "토비의 스프링 Vol.1");

    map.put(book1, "First Input");
    map.put(book2, "Second Input");
    map.put(book3, "Third Input");

    System.out.println(map.get(book1));  
    System.out.println(map.get(book2));   
}

static class Book {

    private int category;
    private String title;

    public Book(int category, String title) {
        this.category = category;
        this.title = title;
    }

    @Override
    public int hashCode() {
        return category;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Book key = (Book) o;
        return category == key.category && Objects.equals(title, key.title);
    }
}

Book 클래스의 hashCode()가 category 값을 리턴하도록 재정의했기 때문에 book1과 book2는 동일한 해시값을 갖게 된다. 해시 충돌이 발생했지만 두 객체는 동일한 해시 버킷에 Linked List 형태로 저장되기 때문에 아래와 같이 First Input이 누락되지 않고 출력된다.

Java 8

Java 7과 달리 Java 8에서는 데이터의 개수가 많아지면 Linked List 대신 Tree를 사용한다. 실제 해시 값은 균등 분포가 아니며, 균등 분포를 따른다고 하더라도 birthday problem처럼 일부 해시 버킷 몇 개에 데이터가 집중될 수 있다. 따라서, 데이터가 일정 개수 이상일 때 Linked List 대신 Tree를 사용하면 성능상 이점이 있다. 이때 사용하는 트리는 Red-Black 트리이다.

Linked List를 사용할지, Tree를 사용할지는 하나의 해시 버킷에 할당된 키-값 쌍의 개수에 따라 달라진다. Java 8은 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 Linked List를 Tree로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 Linked List로 변경한다

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

Java 8에서는 Entry 클래스 대신 Node 클래스를 사용한다. 또한, Tree 구조로 값을 저장할 수 있도록 Node의 하위 클래스인 TreeNode가 존재한다.

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
    
    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    		
    // ...
}
    
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
    TreeNode<K, V> parent;
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;
    boolean red;
    
    TreeNode(int hash, K key, V val, Node<K, V> next) {
        super(hash, key, val, next);
    }
    
    // ...
}    

해시 버킷 동적 확장

해시 버킷 개수의 기본값은 16이고, 데이터의 개수가 임계점에 이를 때마다 해시 버킷 개수의 크기를 두 배씩 증가시킨다. 임계점은 현재의 데이터 개수가 (load factor x 현재의 해시 버킷 개수)에이를 때이다. load factor의 기본값은 0.75이다

버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 한다. 따라서, HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 생성자로 버킷 개수를 지정해 불필요한 Separate Chaining 재구성이 일어나지 않도록 할 수 있다.

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    
    // 새 해시 버킷을 생성한 다음 기존 데이터를 새 해시 버킷에 저장한다.
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
    
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 모든 해시 버킷에 있는 Linked List를 순회한다.
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
             if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
}

그러나, 이렇게 해시 버킷 크기를 2배로 확장하면 해시 버킷의 개수 M이 2의 거듭제곱 형태가 되기 때문에 해시 버킷의 인덱스를 X.hashCode() % M로 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다.

아래 예시를 보자. 2의 거듭제곱으로 나머지 연산을 하면 지수만큼의 하위 비트를 사용한다는 것을 알 수 있다.

// 지수가 2일 때 하위 2개의 비트만 사용함. 
18 % 4 = 10010 % 2^2 = 10 = 2
20 % 4 = 10100 % 2^2 = 00 = 0

// 지수가 3일 때 하위 3개의 비트만 사용함. 
25 % 8 = 11001 % 2^3 = 001 = 1
43 % 8 = 101011 % 2^3 = 011 = 3

즉, 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 거듭제곱으로 나누면 해시 충돌이 쉽게 발생할 수 있다.

보조 해시 함수

index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있다. 그러나 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 해야 한다.

Java 7

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // 상위 비트의 값이 해시 버킷의 인덱스 값을 결정할 때 반영될 수 있도록
	// shift 연산과 XOR 연산을 사용한다.
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Java 8

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

Java 8의 보조 해시 함수는 Java 7에 비해 꽤나 단순한 형태의 보조 해시 함수를 사용한다. 그 이유는 두 가지인데

• Java 8에서는 해시 충돌이 많이 발생하면 Linked List 대신 Tree를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화되었기 때문이다.
• 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다.

Reference

• https://d2.naver.com/helloworld/831311
• https://www.itqit.com/programming/230.html
• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jihyoseok&logNo=221186189902