[자바] Hashmap의 동작 원리에 대해 알아보자

HashMap은 충돌 시 Separate Chaining 방식을 사용한다.

Java 7 이전까지는 LinkedList 자료구조를 사용하고, Java 8 부터는 Red-Black Tree를 이용해 동작한다.

어떠한 차이가 있는지 알아보자.

 

해시 충돌이란?

두 개의 동일하지 않은 객체에 해시 함수를 적용했을때 서로 같은 값이 나와 Key 값이 충돌하는 경우를 말한다.

따라서 이를 해결하기 위한 두 가지 방법이 있다.

1. Open Addessing
2. Seperate Chaining

Open Addressing

해시 버킷이 사용 중인 경우 다른 해시 버켓에 넣는 방식이다.

 

Searate Chaining

이 방식은 충돌이 생기면 해시 버킷을 연결하여 해결하는 방식이다.

 

두 개의 방식 모두 최악의 경우 O(M)이 된다. 그러나 Open Addressing 방법이 체이닝 방식에 비해 캐시 효율이 높다는 장점이 있다.

따라서 데이터 개수가 적다면 Open Addressing 방법을 사용하되, 많다면 캐시 적중율이 낮아지기 때문에 체이닝 방식이 낫다.

 

HashMap

자바의 Hashmap은 Separate Chaining 방식을 사용한다. 빈번하게 remove() 메서드를 호출할 수 있기 때문이다. 또한 데이터가 일정 개수 이상이 되면 더 빠르다는 장점이 있다.

 

자바 7에서의 put() 구현이다. 링크드 리스트로 구현된 방식을 사용한다.

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); // table 배열 생성 } // HashMap에서는 null을 키로 사용할 수 있다. if (key == null) return putForNullKey(value); // value.hashCode() 메서드를 사용하는 것이 아니라, 보조 해시 함수를 이용하여 // 변형된 해시 함수를 사용한다. "보조 해시 함수" 단락에서 설명한다.  
        int hash = hash(key);
        int i = indexFor(hash, table.length);


        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++;

        addEntry(hash, key, value, i);
        return null;
    }

 

Java 8 HashMap의 Separate Chaining

데이터 개수가 많아지게 되면 일부 해시 버켓에 데이터가 집중될 수 있다. 따라서 일정 개수 이상일 때에는 링크드 리스트 자료구조 대신 트리를 사용하는 것이 좋다. 따라서 static 상수로서 트리 자료구조를 바꿀지 안 바꿀지 선택한다.

하나의 해시에 8개 이상 키-값이 모이면 링크드 리스트를 트리 자료 구조로 변경한다.

또한 데이터 삭제가 이뤄져 연결된 키-값이 6개가 되면 다시 링크드 리스트로 동적으로 변경한다.

변경하는 이유는 트리가 메모리 사용량이 많고, 데이터 양이 적을땐 수행 시간 비교가 무의미하기 때문이다.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;

해시 버킷 동적 확장

해시 버킷의 개수가 적다면 메모리를 아낄 수 있지만 충돌로 인한 성능 이점이 사라진다. 따라서 자바는 일정 개수 이상이 되면 해시 버킷 개수를 두 배로 늘린다.

Default Size = 2^4이고, 임계점에 올때마다 2배씩 확장한다. 최대 2^30까지 확장할 수 있다.

이 때 체이닝으로 엮인 데이터들을 다시 재조정해야 하는 문제가 있다. Hashmap은 초기 해시 버킷 개수를 지정할 수 있어 어느정도 예측이 가능한 경우 다시 체이닝을 재구성하지 않아도 된다.

 

String 객체에 대한 해시

String 객체는 문자열 길이에 비례한 함수 수행 시간을 가진다. 따라서 JDK 1.1부터는 빠르게 수행하기 위해 일정 간격의 문자에 대한 해시를 누적한 값을 해시 함수로 사용한다.

만약 길이가 16이 넘으면 최소 하나의 문자를 건너 뛰면서 계산한다. 이런 방식은 해시 충돌 빈도가 높아지게 되어 자바 8에선 다른 방식을 구현한다.

 

정리

자바는 하나의 요청에 많은 Hashmap 객체가 할당되고 GC에 의해 사라진다. 따라서 자바는 Hashmap 성능 향상을 위해 지속적으로 노력해왔다.

자바는 해시 충돌을 위해 Separate Chaining을 사용하고, 자바 8부터는 검색 시간 단축을 위해 리스트 대신 트리 자료구조를 사용한다.

또한 일정 임계점을 기준으로 링크드 리스트와 트리 자료구조를 혼합하여 사용한다. 해시 버킷 동적 확장에 대한 부분도 알아보았다.

 

 

 

 

 

 

 

 

 

참고자료

https://d2.naver.com/helloworld/831311