[Java] 자바의 HashMap에 대해 알아보자

해시테이블이라는 자료구조에 대해 알고싶으면 다음 글을 참고해주세요!

(https://esoongan.tistory.com/134)

 

해시테이블을 공부하면서 내부적인 해시펑션을 통해 나온 해시값이 충돌했을때 이를 어떻게 처리하는지를 알게되었다.

(추가메모리를 사용해 연결리스트로 값을 이어주거나 빈공간을 활용해 남은공간에다 값을 저장함)

그런데 어떤 블로그에서 자바의 해시맵같은경우 키값이 중복되는경우 이전값을 덮어써버린다는것을 보았다. 읭? (글을 작성한 시점에서 다시 보니 저기서 말한 키값은 해시값이 아닌 해시함수를 통과하기전 진짜 '키값'을 말한것인데 아주 잘못이해했다^^)

 

어쨌든 이 기회에 해시맵에 동작과정과 내부적인 해시함수는 어떻게 이루어져있는지에 대해 공부해보고자 한다.

네이버 기술블로그의 [Java HashMap은 어떻게 동작하는가]의 도움을 매우 많이 받았다. (https://d2.naver.com/helloworld/831311)

 

HashTable과 HashMap의 차이

우선 HashTable은 Java의 API

HashMap은 Java Collections Framework API이다.

 

다만 둘다 Map인터페이스를 구현하고 있기 때문에 제공기능은 동일하다.

 

둘의 차이점은 아래와 같다.

1. HashMap은 보조해시함수를 사용한다.
2. 그만큼 해시충돌이 덜 발생할 수 있다는 점이 있어 HashTable보다 성능상 이점을 갖는다.
3. HashMap은 지속적으로 개선되고 있다.
4. 해시테이블은 처음 생겨난 이후 구현에 거의 변화가 없지만 HashMap의경우 계속해서 성능의 발전이 이뤄지고 있다.

해시충돌이 발생하는 이유

해시충돌이란 서로다른값을 해시함수에 통과시켜 얻어낸 해시값이 동일한 경우를 말한다.

 

😙 그럼 서로다른값이면 무조건 다르게 값을 뱉어내는 해시함수를 만들면 되는거 아니야?

응 불가능

Boolean처럼 구별대상이되는 객체가 적거나, Number객체처럼 객체자체가 나타내는 값이 해시값이 되는 경우에는 다른값이면 다른값을 뱉어내는 해시함수의 대상이 될수 있다.

 

그러나 String이나 POJO와 같은 대상에 대하여 언제나 다른값을 뱉어내는 해시함수를 만드는것은 불가능하다.

 

왜 불가능??

해시맵은 기본적으로 hashCode() 메서드가 반환하는 값을 사용하는데 이 반환값의 타입이 int다.

int는 4비트(32비트)크기를 가지는 정수자료형으로 이걸로는 String이나 POJO와 1:1대응되는 해시함수를 만들수가 없기 때문이다.

그건또 왜???

1. 논리적으로 생성가능한 객체수는 2^32보다 (당연히)많을 수 있고

2. 만약 해시 자료구조의 장점인 키값으로 값을 가져오는 연산을 O(1)에 할 수 있으려면 내부적으로 값을 저장하는 배열크기가 2^32여야 하기 때문이다. ( 메모리상으로 매우 비효율적 )

 

이러한 점때문에 HashMap을 비롯한 해시함수를 이용하는 자료구조 구현체에서는 메모리 절약을 위해 실제 해시함수의 표현 정수범위보다 작은 M개의 원소가 있는 배열만을 사용한다.

 

실제 구현은 아래 코드와 같이 객체에 대한 해시코드의 나머지값을 해시 버킷 인덱스값으로 사용한다.

위 코드를 통해 나온값을 아래 그림의 버킷 인덱스로 사용하는것!!!

int index = X.hashCode() % M;

해시함수를 이용하는 자료구조의 기본형태 (키-값쌍)

 

 

단, 이렇게 할때의 문제점은 해시값이 충돌될수 있다는 점이다.

 

위방식에서는 서로다른 해시코드를 가지는 서로다른 객체가 1/M의 확률로 같은 해시버킷을 사용하게 된다.

이는 애초에 메모리공간이 부족해서 나타나는 것이므로 아무리 해시함수가 잘 설계되어있다고 하더라도 M만큼의 공간이 다 차면 무조건 충돌이 발생하게 되는 문제이다.

 

해시충돌을 해결하는 방법

위에서 본것처럼 해시충돌은 해시함수를 얼마나 잘 설계했냐 하더라도 메모리를 효율적으로 사용하기위해 어쩔수없이 발생할 수 밖에 없는 문제이다.

그럼 해시충돌을 어떻게 해결할 수 있을까

크게 2가지 방법이 있다.

1. Open Addressing(개방주소법)

추가메모리를 사용하지않고 비어있는 해시버킷 공간을 활용한다.

개방주소법을 구현하기위한 방법은 다음과 같다.

• Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
• Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
• Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

2. Separate Chaining(분리연결법)

분리연결법

동일한 버킷으로 접근시, 추가메모리를 사용해 데이터를 연결해서 관리한다.

분리연결법의 경우 해시테이블의 확장이 필요없고, 구현이 간단하지만 데이터의 수가 많아지면 동일한 버킷에 연결되는(chaining)되는 데이터가 많아지며 그에따라 캐시 효율성이 감소한다는 단점이 있다.

 

Java의 HashMap은 어떤 방법으로 충돌을 해결하는가?

Java의 HashMap은 분리연결법을 사용한다.

왜??

• 삭제처리가 효율적이다 : 
  • 개방주소법의 경우 데이터 삭제시 인덱스를 찾아가야하는데, 이 인덱스가 충돌때문에 바뀐 인덱스값을 찾아가는 등의 이유로 삭제처리가 효율적이기 어렵다. HashMap에서 remove()메서드는 매우 빈번하게 호출될 수 있기때문에 분리연결법을 사용한다.
• 데이터가 많을때는 분리연결법이 더 빠르다. 
  • 개방주소법의 경우 해시버킷이 일정수준이상 찼다면 계속해서 최악의 경우로 다가간다(?). 해시충돌이 발생할 경우가 점점더 많아지기 때문이다. 반면 분리연결법은 해시충돌이 발생하지 않도록 잘 조정할수만 있다면 최악의 경우를 방지할 수 있는 여지가 생긴다.

또한 자바는 해시충돌을 방지하기 위해 보조해시함수를 사용한다. 보조해시함수에 대해 자세하게 알고 싶으면 https://d2.naver.com/helloworld/831311 를 참고하자.

 

Java11에서의 put메서드는 다음과 같다. 너무어렵다;

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

 

 

Java8에서 HashMap의 분리연결법 - 트리의 등장

지금까지 분리연결법에서 중복된값을 저장할때 Linked List를 사용했다.

 

그러나 자바8에서부터 데이터의 수가 많아지면 연결리스트대신 트리를 사용하도록 바뀌었다! ( 이렇게 자바8에서 추가된 기능을 또하나 알게되었다.)

 

데이터의 수가 많아진다는것의 기준이 무엇인가??

"하나의 해시버킷에 할당된 키-값 쌍의 개수를 기준"으로 결정한다.

개수가 8개가 되면 링크드 리스트를 트리로 변경한다.

만약 해당 버킷에 있는 데이터를 2개 삭제해서 6개가 된 경우 다시 트리 → 링크드리스트로 변경한다.

 

이때 링크드리스트로 변경하는 기준을 7이아닌 6으로 둔 이유는, 어떤 키-값 쌍 1개가 반복적으로 삽입/삭제 되는 경우 비효율적으로 계속 트리-링크드리스트-트리 이런식으로 반복되어 성능저하가 발생될수 있기 때문이다!

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

 

 

실제 코드를 보면 레드블랙트리를 사용하고 있는것을 볼 수 있다. 어제 스터디에서 내가맡았던 주제중에 레드블랙트리가 있었는데 이렇게바로 만나다니... 신기하다!!!!

 

레드블랙트리에 대해 간단하게만 설명하면 균형잡힌 이진탐색트리의 한 종류로서 편향트리가 되지않도록 조건을 걸어 놓은 트리이다.

즉 이렇게되면 트리의 높이가 logN에 바운드되게 되므로 탐색에서 굉장히 효율적인 시간복잡도를 갖는다.(트리의 탐색시간복잡도는 높이에 비례하기때문) 

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

 

해시버킷의 동적 확장

해시 자료구조에서 중요한것은 해시버킷의 사이즈를 지나치게 크게 사용하지 않으면서(메모리를 효율적으로 사용) 동시에 해시충돌또한 최소한으로 발생하도록 해서 최적의 성능을 보장해야한다.

 

그러므로 적절한 해시버킷의 사이즈를 정하는것이 중요하다.

지나치게 작게하면 메모리는 아낄 수 있어도 해시충돌이 너무 자주 발생하여 성능저하가 발생할 수 있기 때문이다.

 

Java의 HashMap은 키-값 쌍 개수가 일정이상이 되면 해시버킷의 크기를 2배로 늘린다.

해시버킷 개수의 기본값은 16이고 일정개수 이상이 되면 2배씩 증가시켜 최대 2^30개까지 증가시킨다.

이때 2배씩 증가시킨다고 했는데 이럴때마다 모든 데이터를 읽어 새로운 분리연결을 구성해야 하므로 이또한 성능저하가 발생할 수 있다.

즉, 이러한 동적확장이 일어나지 않도록 초기에 미리 해시맵에 얼만큼의 데이터를 넣어야하는지 알 수 있다면 생성자를 통해 크기를 미리 지정하여 불필요한 분리연결을 재구성하지 않도록 하는것이 중요하다.

 

정리

• 자바의 해시맵에서는 해시충돌을 방지하기위해 1. 분리연결법, 2. 보조해시함수를 사용한다.
• 자바8부터 데이터의 개수가 일정수준 이상이 되면 연결리스트에서 트리로 변경된다.
• 해시버킷이 일정수준이상 차서 계속해서 해시충돌이 일어나는경우 해시버킷사이즈를 2배로 늘리는데 이때 분리연결법을 새로 다 구성해야하므로 성능저하가 크다. 따라서 해시맵의 경우 데이터의 개수를 미리 알 수 있다면 초기에 크기를 적절히 설정하는것이 중요!!