Java HashMap은 어떻게 동작하는가?

Java HashMap은 어떻게 동작하는가?(NAVER D2)

NAVER D2

• 해시맵과 테이블은 기능은 동일하다
  1. 다만 보조해시 함수를 사용하는 해시맵이 충돌이 덜 발생할 수 있어 상대적으로 성능상 이슈가 있다.
  2. 해시 테이블은 거의 변화가 없지만 해시 맵은 버전을 거치면서 변화가 많다
  • 어떤 변화?

// 해시맵의 선언부 
public class java/util/HashMap extends java/util/AbstractMap implements java/util/Map java/lang/Cloneable java/io/Serializable {

// 해시 테이블의 선언부
public class java/util/Hashtable extends java/util/Dictionary implements java/util/Map java/lang/Cloneable java/io/Serializable {

• Dictionary 가 하는 역할은?

• 해시맵은 왜 Map을 implements 한 AbstractMap을 extends 하고, Map을 implements 했을까?

• 객체가 나타내려는 값 자체를 해시 값으로 사용할 때는 완전한 해시 함수 , 그러나 String이나 Object는 완전 해시 함수 불가능

• 해시 판별은 각 객체가 hashCode() 메서드가 반환하는 값을 사용함, 길어봐야 자료형 int, 32비트 정수 자료형이다 → 완전 해시 함수 불가능

• 실제 해시 함수의 표현 정수 범위보다 작은 M개의 원소 배열을 사용함

• int index = X.hashCode() % M → 1/M 확률로 같은 버킷을 사용함

• 충돌이 발생해도 잘 저장하고 조회할 수 있는 대표 방식이 Open Addressing / Separate Chaining

• Open Addressing : 충돌 → 다음 빈 공간

  • 삭제시 문제가 많음, 해시값이 1인 A 가 들어가고 동알한 해시값을 가진 AA 가 삽입될 경우 충돌 발생 → 다음 해시값 2에 넣어둠
  • 만약 1인 A를 삭제하고 AA도 삭제하려고 할 경우 AA 해시값인 1 자리에는 비어있게 됨 → 추가로 더미노드를 작성하여 넣어두어야 함
  • 해시 밀도가 높아지면 워스트 케이스 발생 빈도가 높아짐

• Separate Chaining : 충돌 → 선형적으로 리스트를 만듦

  • 1.8 이상에서는 8개 이상이면 트리로 구현하여 시간복잡도를 낮춤

• 자바 1.7에서는 버킷의 구현이 아래와 같이 되어 있다.

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
..

// 버킷을 구성하는 Entry(노드) class
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {...}

        public final int hashCode() {...}

        public final String toString() {...}

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {...}

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {...}
    }

• Separate Chaining 방식을 사용하는 java 7 에서 put 메서드는 아래와 같다.

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null) // hashmap 에서는 키값이 null 가능
            return putForNullKey(value);
        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++; // ConcurrentModificationException 을 발생시킬지 확인하기위해

                // 새로운 값이면 삽입, 이때 threshold와 loadFactor 에 의해서
        // 지정된 크기 만큼 커진다면 newCapacity * loadFactor (0.75) 값으로 새롭기 설정하고
        // 리사이징이 일어남
        addEntry(hash, key, value, i);
        return null;
    }

• java 8 에서는 조금 다르게 구현함
• Separate Chaining에서 동일 키가 특정 개수 이상이면 링크드 리스트를 대신해서 트리 형식으로 사용함

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

• 또한 Entry 클래스를 대신해서 Node를 사용하는 TreeNode 클래스를 사용함

• 이때 사용하는 방식은 레드 블랙트리

• 해시 크기는 항상 2의 승수로 늘어남

• 그렇기 때문에 index = X.hashCode() % M 공식에서 index는 2의 승수만큼의 비트 개수만 사용하게 됨

• 2의 승수로만 나누면 해시 출동이 쉽게 일어남

• 그래서 보조 해시 함수가 필요함

// java 7 버전 보조 해시 함수
final int hash(Object k) {  
        // Java 7부터는 JRE를 실행할 때, 데이터 개수가 일정 이상이면
        // String 객체에 대해서 JVM에서 제공하는 별도의 옵션으로
        // 해시 함수를 사용하도록 할 수 있다.
        // 만약 이 옵션을 사용하지 않으면 hashSeed의 값은 0이다.
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        // 해시 버킷의 개수가 2a이기 때문에 해시 값의 a비트 값만을 
        // 해시 버킷의 인덱스로 사용한다. 따라서 상위 비트의 값이 
        // 해시 버킷의 인덱스 값을 결정할 때 반영될 수 있도록
        // shift 연산과 XOR 연산을 사용하여, 원래의 해시 값이 a비트 내에서 
        // 최대한 값이 겹치지 않고 구별되게 한다.
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

// 8버전 보조 해시 함수 
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

• 이렇게 간단해진 이유는 링크드 리스트 대신에 트리를 쓰는 것과 해시 함수들이 발전한 결과다