Java 8 HashMap에서의 Separate Chaining

Java HashMap 은 어떻게 동작하는가? 를 읽던중 HashMap에서 버킷관리 방식으로 채택된 Seperate Chaning 이 내부적으로 어떻게 구현되어있는지 궁금해졌다.

먼저 "해시 충돌" 이란 1) 서로다른 key 값을 가지지만 같은 hashcode를 반환할때 2) 서로다른 hashcode값을 가지지만 같은 index로 매핑이 될때 발생한다.

M이라는 제한된 인덱스 범위 내에서 key값을 사용할수 있기에 해시충돌을 피하는것은 불가능 하다. 따라서 두가지 자료구조가 제안되었다. 그 중 두번째 자료구조가 Separate Chaining 이고 첫번째인 Open Addressing(데이터를 삽입하려는 해시 버킷이 이미 사용중인 경우 다른 해시 버킷에 해당 데이터 삽입) 보다remove()처리가 쉽기에 채택되었다.

다음은 Separate Chaining을 사용해 put()을 구현한 HashMap.Class 의 코드이다. 하나의 버킷이 담는 데이터 개수가 많아질 경우 링크드 리스트 대신 트리구조를 이용하는게 유리하다(N/M -> log(N/M))

  public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    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;
    }

코드에서도 Separate Chaining 에 TreeNode를 이용하는것을 볼 수 있다.

해시버킷동적확장
해시 버킷의 개수는 유한개로 한정되어 있다. 개수를 적게하면 메모리 사용은 아낄수 있겠지만, 해시충돌의 확률이 그만큼 높아진다. 따라서 일정개수 이상이 되면 해시충돌이 발생하지 않게 해시 버킷의 수를 두 배로 늘려주는 방법을 취한다.(16개~2^30)

하지만 이렇게 두배로 확장해나가는 것에 문제가 있다. 해시버킷개수인 M이 2^a의 형태가 되기 때문에, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다는 것이다.즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.
이때문에 보조 해시 함수가 등장했다.

보조 해시 함수의 목적은 '키'의 해시 값을 변형하여 충돌 가능성을 줄이는 것이다.

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