[JAVA] HashMap 은 어떻게 동작할까

신명철·2022년 7월 27일
HashMapHashTableJava
0

JAVA

목록 보기
11/14

들어가기 전

본 포스트는 NAVER D2 - Java HashMap은 어떻게 동작하는가?를 참고해 HashMap이 어떻게 충돌 가능성을 줄이는지에 대해 구체적으로 다룰 것이다.

HashMap 과 HashTable

HashMap과 HashTable은 둘 다 '키에 대한 해시 값을 사용해 값을 저장하고 조회하며 키-값 쌍 개수에 따라 동적으로 증가하는 자료구조'이지만 서로 다른 점이 많다. 현재는 다양한 이유로 HashTable은 거의 사용되지 않는다.

HashMapHashTable
해시 보조함수 사용OX
동기화XO
value null 허용OX
Hash 충돌 빈도상대적으로 적음상대적으로 높음

해시 분포와 해시 충돌

Boolean 같이 서로 구분되는 종류가 적거나, Integer,Long,Double 같은 Number 객체는 객체가 나타내려는 값 자체를 해시 값으로 사용할 수 있어서 완전한 해시 함수 대상으로 삼을 수 있다. 하지만, String이나 POJO에 대해 완전한 해시 함수를 제작하는 것은 사실상 불가능하다.

완전한 해시 함수(perfect hash function)
X.equals(Y)가 false 일 때, X.hashCode()!=Y.hashCode() 라면 이 때 사용하는 해시 함수를 완전한 해시 함수라고 한다.

hashCode()의 return type은 int이기 때문에 2^32개의 서로 다른 hash가 발생할 수 있다. 32bit의 정수 자료형으로는 완전한 해시 함수를 만들 수 없다. 그 이유는 다음과 같다.

  1. 논리적으로 생성 가능한 객체의 수가 2^32보다 많을 수 있다.
  2. HashMap 객체는 O(1)를 보장하기 위해서 랜덤 접근이 가능하게 하려면 원소가 2^32인 배열을 모든 HashMap이 가지고 있어야 하기 때문이다.

HashMap은 associative array 이다

HashMap를 비롯한 많은 해시 함수를 이용하는 associative array 구현체에서는 메모리를 절약하기 위해 정수 범위(|N|) 보다 적은 M개의 원소가 있는 배열만을 사용한다. 따라서 다음과 같이 객체에 대한 해시 코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.

int index = X.hashCode() % M;

이 결과 확률로 서로 다른 해시값을 가진 서로 다른 객체가 1/M 의 확률로 같은 해시 버킷을 사용하게 된다.

해시 충돌 극복

같은 버킷 인덱스를 사용하게 되는 해시 충돌이 발생했을 때 사용하는 방법은 크게 두 가지다.

  1. Open Addressing
    • 충돌 발생 시 사용할 다른 버킷을 찾는다.
    • 버킷 탐색 시 Linear Probing, Quadratic Probing 등의 방법을 사용한다.
  2. Separate Chaining
    • JAVA HashMap에서 사용하는 방법이다.
    • 충돌한 객체들을 LinkedList의 형태로 연결한다.
    • HashMap의 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 LinkedList의 첫 부분이다.

두 가지 방법 모두 WorstCase는 O(M)으로 같다. 하지만 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 상대적으로 더 높다. 따라서 데이터의 갯수가 충분히 적다면 Open Addressing이 Seperate Chaining보다 성능이 더 좋다. 하지만 배열이 커질수록 그 장점은 사라진다. 캐시 적중률(hit ratio)이 낮아지기 때문이다.

Seperate Chaining

JAVA의 HashMap은 Seperate Chaining을 사용한다.

  • 데이터 삭제 시 Open Addressing 보다 처리 효율이 더 높다.
    • remove() 메서드가 빈번한 HashMap에 적합
  • 배열이 커지면 Open Addressing 은 느릴 수 밖에 없다.
    • Seperate Chaining이 LinkedList에서 Tree구조를 변경하면 차이는 더 커짐

JAVA8 부터는 해시 충돌 객체가 일정 수준을 넘어서면 LinkedList 대신 Tree를 사용한다. O(N) -> O(logN) 으로 줄어들어 충돌하는 해시 버킷이 많아질수록 성능이 크게 향상될 수 있다. LinkedList를 사용할 것인가 Tree를 사용할 것인가의 기준은 해시 버킷의 개수다. JAVA8 HashMap에서는 상수 형태로 기준을 두고 있는데, 버킷이 8개 이상이 되면 Tree 구조로 변경하고, 6개 이하가 되면 다시 LinkedList로 변경한다. 여기서 2의 차이를 둔 것은 삽입/삭제가 반복되면 불필요하게 구조가 반복적으로 불필요하게 변경될 수 있기 때문이다.

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

이 때 사용하는 Tree는 Red-Black Tree를 사용한다. TreeMap과 구현이 거의 같다고 할 수 있다. 트리 순회 시 대소의 판단 기준은 해시 함수 값이다. 해시 값을 기준으로 대소를 판단하다 보면 대소가 모호해질 수 있다. hash 값이 서로 같아도 둘이 동등하지 않을 수 있기 때문이다. HashMap에서는 tieBreakOrder()메서드를 사용해 이를 해결한다.

transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {  
  // 클래스 이름은 다르지만, Java 7의 Entry 클래스와 구현 내용은 같다. 
}


// LinkedHashMap.Entry는 HashMap.Node를 상속한 클래스다.
// 따라서 TreeNode 객체를 table 배열에 저장할 수 있다.
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;   

        // Red Black Tree에서 노드는 Red이거나 Black이다.
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        final TreeNode<K,V> root() {
        // Tree 노드의 root를 반환한다. 
        }

        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        // 해시 버킷에 트리를 저장할 때에는, root 노드에 가장 먼저 접근해야 한다.
        }


        // 순회하며 트리 노드 조회 
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
        final TreeNode<K,V> getTreeNode(int h, Object k) {}


        static int tieBreakOrder(Object a, Object b) {
         // TreeNode에서 어떤 두 키의comparator 값이 같다면 서로 동등하게 취급된다.
         // 그런데 어떤 두 개의 키의 hash 값이 서로 같아도 이 둘은 서로 동등하지 
         // 않을 수 있다. 따라서 어떤 두 개의 키에 대한 해시 함수 값이 같을 경우, 
         // 임의로 대소 관계를 지정할 필요가 있는 경우가 있다. 
        }


        final void treeify(Node<K,V>[] tab) {
          // 링크드 리스트를 트리로 변환한다.
        }



        final Node<K,V> untreeify(HashMap<K,V> map) {
          // 트리를 링크드 리스트로 변환한다.
        }

        // 다음 두 개 메서드의 역할은 메서드 이름만 읽어도 알 수 있다.
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {}
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {}


        // Red Black 구성 규칙에 따라 균형을 유지하기 위한 것이다.
        final void split (…)
        static <K,V> TreeNode<K,V> rotateLeft(…)
        static <K,V> TreeNode<K,V> rotateRight(…)
        static <K,V> TreeNode<K,V> balanceInsertion(…)
        static <K,V> TreeNode<K,V> balanceDeletion(…)



        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
        // Tree가 규칙에 맞게 잘 생성된 것인지 판단하는 메서드다.
        }
    }

해시 버킷 동적 확장

해시 버킷의 수가 적다면 메모리 사용을 줄일 수 있지만 성능상의 손실이 발생할 수 있다. 그래서 HashMap은 키-값 쌍 데이터 개수가 임계점에 이르게 되면, 임계점에 이를 때마다 해시 버킷의 수를 두배로 늘린다. 버킷의 최대 개수는 2^30 개다. 그런데 버킷의 개수를 증가시킬 때마다 발생하는 문제가 있다.

모든 키-값 데이터들을 다시 읽어 이미 구성되어 있는 Seperate Chaining을 재구성해야 한다는 것이다. HashMap 생성자의 인자로 초기 해시 버킷의 개수를 지정할 수 있으므로, 해당 HashMap객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우 이를 생성자의 인자로 지정하면 불필요하게 Seperate Chaining을 재구성하지 않게 할 수 있다.

// 인자로 사용하는 newCapacity는 언제나 2a이다.
	void resize(int newCapacity) {  
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;

        // MAXIMIM_CAPACITY는 230이다.
        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;
        // 모든 해시 버킷을 순회하면서
        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);
                }
                // 해시 버킷 개수가 변경되었기 때문에
                // index 값(hashCode % M)을 다시 계산해야 한다. 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

해시 버킷의 개수를 두 배로 확장하는 임계점은 현재 데이터의 개수가 load factor * 현재 해시 버킷 개수 에 이를 때이다. 여기서 load factor = 3/4, 즉 0.75다. 물론 이 값도 생성자에서 지정할 수 있다.

근데 이렇게 매번 해시 크기를 두 배로 확장하는 것은 결정적인 문제가 존재한다. M = 2^a 형태가 되기 때문에 버킷 인덱스를 구할 때 index = X.hashCode() % M 이므로 하위 a개의 비트만 사용하게 된다는 점이다. 즉, 해시 함수가 32bit를 고루 사용하도록 만들어도 2의 승수로 나눈다면 해시 충돌이 쉽게 발생하게 된다.

이 때문에 보조 해시 함수가 필요하다.

보조 해시 함수

보조 해시 함수(supplement hash function)의 목적은 키의 해시 값을 변경해 해시 충돌 가능성을 줄이는 것이다. 

/* 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);
}

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

위에서 알 수 있듯, JAVA 8 부터는 그 이전보다 훨씬 간단한 보조 해시 함수를 사용한다. 그 이유는 다음과 같다.

  1. JAVA8 부터는 해시 충돌이 많아지면 Tree를 사용하기 때문에 성능 문제가 완화됐다.
  2. 최근 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아 JAVA 7에서의 보조 해시 함수의 효과가 크지 않기 때문이다. => 결정적인 이유

개념적으로 해시 버킷 인덱스를 계산할 때는 index = X.hashCode() % M 처럼 나머지 연산을 하는게 맞지만, M 값이 2^a 이기 때문에 해시 함수의 하위 a비트만을 취한 것과 값이 같다. 따라서 나머지 연산 대신 1 << a-1 과 같은 비트 논리곱(AND, &)연산을 사용하는게 수행이 훨씬 더 빠르다.

String 객체에 대한 해시 함수

String 객체에 대한 해시 함수 수행 시간은 문자열의 길이와 비례한다. 그렇기 때문에 JDK 1.1 에서는 수행 속도를 줄이기 위해 String 객체에 대해 일정 간격의 문자에 대한 해시를 누적한 값을 사용했다.

public int hashCode() {  
    int hash = 0;
     int skip = Math.max(1, length() / 8);
     for (int i = 0; i < length(): i+= skip) // skip을 통해 문자 간격을 둔다.
           hash = s[i] + (37 * hash);
    return hash;
}

즉 모든 문자에 대해서 해시 함수를 계산하는게 아니라 문자열의 길이가 16을 넘으면 최소 하나의 문자를 건너가며 해시 함수를 계산한 것이다.

그러나 이런 방식은 WEB 상의 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;
}

String 객체 해시 함수에서 31을 사용하는 이유는, 31은 소수이고 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다.

31 = 32 - 1 = 2^5 - 1 이다. 32는 shift 연산으로 빠르게 계산 가능하기 때문에, N에 31을 곱한 값은 (N<<5)-N 으로 표현할 수 있다. 이렇게 31을 곱하는 연산은 최적화된 머신 코드로 생성할 수 있기 때문에 31을 사용한다.

출처

profile
신명철
내 머릿속 지우개
이전 포스트

[JAVA] Integer Caching

다음 포스트

[JAVA] Predicate

0개의 댓글