Java HashMap의 구조

Java HashTable과 HashMap

• HashTable은 Java 1부터 있었고 HashMap은 1998년 Java 2에서 소개됨
• HashMap과 HashTable이 제공하는 기능은 동일함
• 차이점

• HashMap은 보조해시함수(Additional Hash Function)를 사용하기 때문에 그렇지 않은 HashTable에 비해 충돌 (hash collision)이 덜 발생하여 성능상의 이점이 있다. 
• 그 외에도 구현상 거의 변화가 없는 HashTable에 비해 HashMap은 지속적으로 성능 개선의 노력들이 있어 왔다. (HashTable은 하위호환성 보장용이라고 보면 된다. 사실상 성능 비교 무의미)
• HashTable은 synchronized되어 있다. (여기에 또한 성능상의 패널티 있다)
• HashTable은 key와 value에 null을 허용하지 않는다.

• HashMap과 HashTable을 한줄로 설명하자면 "키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array"라고 할 수 있다. Associate array를 지칭하는 또 다른 용어로서 Map, Directory, Symbol Table등이 있는데 HashTable은 Directory를 상속하고 있고 HashMap은 Map을 상속(구현)하고 있다. 

해시함수와 충돌회피

• 서로 다른 객체에 대해서 서로 다른 해시값을 생성해내는 해시함수를 완전한 해시 함수(perfect hash function)라고 한다. Primative type이면 몰라도 String이나 POJO 클래스에 대해서 완전한 해시 함수를 만든다는 것은 사실상 불가능하다. 게다가 저장할 수 있는 메모리의 제약사항으로 인해서 해시함수에서 충돌은 불가피하다. 

int index = X.hashCode() % M;

• 충돌에 대응하는 방법으로 두 가지가 있는데 Open Addressing과 Separate Chaining 이다.

(Open Addressing)

 

(Separate Chaining)

• 위의 그림에서 "John Smith"의 index가 152이고 하필 "Sandra Dee"의 index도 152로써 동일하다면 Open Addressing에서는 연속된 다른 bucket에 순차적으로 입력하는데 Separate Chaining에서는 index로부터 리스트의 형태로 추가한다. 
• Open Addressing에서 "Ted Baker"는 index가 153으로 원래는 충돌이 없었는데 "Sandra Dee"가 "John Smith"와 충돌나는 바람에 index를 침범하였다. 그래서 결국 "Ted Baker"도 충돌이 나게 된다. 
• 둘다 worst case에서 O(M)이다. Open Addressing은 기존 공간을 활용하므로 캐시 효율이 좋고 버켓 크기에 비해 데이터 개수가 충분히 적다면 Separate Chaining보다 효율적이다. 
• 반면 키-값 개수가 늘어나 충돌이 많아지면 일반적으로 Open Addressing이 Separate Chaining보다 느리다. Open Addressing이 캐시 효율이 좋지만 밀도가 높아 충돌 가능성을 더 높이기 때문이다. 또 Separate Chaining은 보조해시함수를 사용하면 충돌이 잘 발생하지 않도록 '조절'할 수 있다. 
• Java HashMap의 경우 Separate Chaining 방식을 사용하는데 위의 이유도 있고 추가로 Open Addressing이 원소의 삭제에 대해 효율적으로 구현하기 어렵다는 이유도 있다. HashMap은 remove() 호출이 빈번할 수 있기 때문이다. 

Java 8에서의 HashMap Separate Chaining의 성능 개선

• Java 8에서 Separate Chaining를 구현할 때 리스트 대신 트리를 사용한다. 정확하게는 개수가 8개까지는 리스트를 사용하고 그것을 넘은 경우 트리로 전환한다. (다시 6개 보다 작아지면 리스트로 전환)
• 이때 사용하는 트리는 Red-Black Tree인데 TreeMap의 구현과 거의 동일하다. 

해시 버킷의 동적 확장

• 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다.
• 버킷의 최대 개수는 2³⁰개다. 그런데 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다. 따라서 초기 사이즈를 적당하게 지정해주면 좋다.
• 두배로 확장하는 시점의 결정은 밀도가 임계치(75%)를 넘어설 때이다. 
• 두배로 확장할 때의 문제점이 크기가 2ⁿ, 즉 2의 지수승으로 커지면서 hash code의 하위 n 비트만 사용하게 된다. 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.
• 이 때문에 보조해시함수가 필요하다.

보조 해시 함수

• index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있다. 그러나 M 값이 소수가 아니기 때문에 index 값의 분포가 가급적 균등하도록 보조 해시 함수를 이용한다.
• 즉, 보조 해시 함수는 키의 해시값을 변형하여 해시 충돌 가능성을 줄이는 역할을 한다. 
• Java 8에서의 보조 해시 함수이다. 

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

• 비교적 단순한데 Java 7까지는 이보다 복잡했다. 그 이유는 Java 8에서 충돌시 chain으로 리스트대신 tree를 사용하기 때문에 성능문제가 완화된 것도 있고, 최근의 해시 함수들이 균등분포가 잘되는 경향이 많아서 그렇다. (후자의 이유가 더 크다)

String 객체의 해시 함수

• 해시함수는 문자열 길이에 비례하여 계산량이 늘어나기 때문에 16자리가 넘어서면 (최소 하나) 문자들을 건너서 계산했다. 그러나 이러한 방식은 웹 URL과 같이 앞부분이 거의 같은 유형의 문자열에서 문제를 야기시킨다. 

• 따라서 Java 8에서는 아래와 같은 코드가 사용된다. 

public int hashCode() {  
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
 
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

• 문자 마다 31을 계속 곱해서 모두 더하는 방식인데, 31은 소수이고, 31을 곱하는 것은 bit연산으로 빠르게 최적화되기 때문이다. 참고로 N에 31을 곱하는 것은 (N << 5) - N과 같다.

HashMap Code

• Java 1.2에서는 Open Addressing 방식인데, Java 7에서는 Separate Chaining이다. 
• Java 8에서 Separate Chaining의 구현이 TreeNode를 사용하는 트리 구조로 바뀌었다.
• Java 1.2

public class HashMap<K,V> extends AbstractMap<K,V>
           implements Map<K,V>, Cloneable, java.io.Serializable
{
    ...
    // 'transient'는 이 변수는 메모리 안에서만 사용되어야 한다는 뜻
    // 주로 직렬화할 때 상태가 저장되거나 복원되지 않는다는 뜻으로 사용된다
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    transient Entry[] table;
    transient int size;
    int threshold;
    final float loadFactor;
    transient volatile int modCount;
 
    public HashMap(int initialCapacity, float loadFactor) {
        ...
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
 
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        ...
    }
 
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }
 
    // 보조 hash 함수
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
 
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
 
    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
 
    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }
 
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        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;
    }
 
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
 
    public boolean containsValue(Object value) {
        if (value == null)
            return containsNullValue();
 
        Entry[] tab = table;
        for (int i = 0; i < tab.length ; i++)
            for (Entry e = tab[i] ; e != null ; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    }
...
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
 
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
...

대표 출처

• http://d2.naver.com/helloworld/831311