HashMap : 해시 충돌이 발생하였을 때

해시 테이블은 해시 충돌이 발생하였을 때, 분리 연결법에 의하여 LinkedList를 활용하여 동일한 해시값에 대응하는 요소들을 저장한다고 해시 포스팅에서 다룬 적이 있다.

해시 테이블 기반인 해시 맵 또한 LinkedList를 활용하여 해시 충돌을 해결하는지에 대해 알아보려고한다.

---

해시 충돌이 발생하였을 때 해결 방법

Java 8 기준으로 해시 충돌이 발생하였을 때 해결하는 방법이 다르다.

Java 8 이전

LinkedList 방식으로 해시 충돌을 해결한다.

java 7에 대한 put 메서드에 대한 내용을 확인해본다.

https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/HashMap.java#L386

jdk7u-jdk/src/share/classes/java/util/HashMap.java at master · openjdk-mirror/jdk7u-jdk

 

Java 8 이후

LinkedList 방식을 사용하다가 Red-Black Tree 방식으로 변경하여 해시 충돌을 해결한다.

해시 충돌이 발생하였을 때, 어떻게 해결하는지 보기 전에 몇 가지 알고 넘어가려고 한다.

1. HashMap에서 활용하는 노드들의 관계

HashMap의 TreeNode는 LinkedHashMap의 Entry 클래스를 상속하고, 이 Entry 클래스는 HashMap의 Node를 상속하며 이 Node는 Map 인터페이스의 Entry를 구현하는 관계로 이루어져있다.

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    transient Node<K,V>[] table;

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
    
    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;	//Red Black Tree에서 노드는 Red이거나 Black이다
    }
}

 

2. 트리를 사용하기 위한 조건

static final int TREEIFY_THRESHOLD = 8;

HashMap에 선언된 해당 필드의 설명은 공식문서에 다음과 같이 작성되어있다.

The bin count threshold for using a tree rather than list for a bin. Bins are converted to trees when adding an element to a bin with at least this many nodes. The value must be greater than 2 and should be at least 8 to mesh with assumptions in tree removal about conversion back to plain bins upon shrinkage.

트리 구조로 변환하기 위한 임계값으로, 버킷에 저장된 요소는 최소한 2개 이상이며 버킷에 저장된 요소가 적어지게 되었을 때에도 최소한 8개의 요소가 있어야 트리 구조를 유지한다는 내용이다.

즉, 해시 충돌이 발생하였을 때 LinkedList를 사용하다가 버킷에 저장된 요소들이 8개 이상이 되면 트리로 사용한다는 것이다.

 

3. 연결리스트를 사용하기 위한 조건

static final int UNTREEIFY_THRESHOLD = 6;

HashMap에 선언된 해당 필드의 설명은 공식문서에 다음과 같이 작성되어있다.

The bin count threshold for untreeifying a (split) bin during a resize operation. Should be less than TREEIFY_THRESHOLD, and at most 6 to mesh with shrinkage detection under removal.

LinkedList 구조로 변환하기 위한 임계값으로, 테이블 사이즈를 재 측정할 때 사용된다. 트리 구조로 변환하기 위한 조건인 TREEIFY_THRESHOLD 값보다 작아야하며 최대값은 6이다.

 

HashMap의 put 함수 코드의 일부분이다.

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 ((p = tab[i = (n - 1) & hash]) == null) //(1)
            tab[i] = newNode(hash, key, value, null);
        else { //(2)
            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) //(3)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { //(4)
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null); //(5)
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st (6)
                            treeifyBin(tab, hash);
                        break;
                    }
                    ...
                }
            }
            ...
        }
        ...
    }

 

(1) 해시 충돌이 발생하지 않는 경우에 대한 처리로, 해시값에 해당하는 버킷에 저장된 값이 없다면 새로운 노드를 생성하여 해당 버킷에 저장한다. Node 클래스의 newNode 메서드를 호출하는데, 이는 충돌이 발생하였을 때 여러 노드가 하나의 버킷에 LinkedList 형식으로 저장될 수 있다는 기초 작업을 보여준다.

 

(2) 해시 충돌이 발생한 경우에 대한 처리로, 어떤 조건으로 LinkedList와 Red-Black Tree 구조를 사용하는지를 보여준다.

 

(3) 버킷에서 가져온 요소가 TreeNode 객체인 경우에 대한 처리를 보여준다. Node<K,V>의 객체인 p를 TreeNode로 Upcasting하여 저장한다. Upcasting 할 수 있는 이유는 위에서 노드들의 관계를 보면 알 수 있듯이, 결국 TreeNode도 Node클래스의 자식클래스이기 때문에 형 변환이 가능하다.

따라서, TreeNode의 putTreeVal 메서드를 호출하여 새로운 요소를 트리 구조에 저장한다.

 

(4) LinkedList 구조이거나 버킷에 하나의 요소만 들어있는 경우에 대한 처리를 보여준다.

 

(5) 버킷에 저장된 요소의 다음 노드가 없을 경우, 새로운 노드를 생성한다. 이 과정에서 기존에 있던 노드와 새로운 노드는 연결이 진행되며, LinkedList 구조가 된다.

 

(6) binCount는 해당 버킷에 저장된 요소의 수를 나타내는데, binCount가 TREEIFY_THRESHOLD - 1 이상이면 LinkedList에서 트리 구조로 변경한다.

 

LinkedList 에서 Red-Black Tree 구조를 사용하는 이유

검색의 효율성을 위해서 Red-Black Tree 구조를 사용한다.

데이터 처리(저장, 삭제 등)를 하기위해서는 우선적으로 데이터를 빠르게 검색할 수 있어야 한다. 이는 데이터 검색 처리 속도가 중요하다는 것이다.

 

그럼 LinkedList와 Red-Black Tree의 검색 속도는 어떻게 될까?

LinkedList의 검색 속도는 O(n)이며, Red-Black Tree는 O(log n)이다. 최악의 경우에도 동일하다.

O(n)과 O(log n)에 대한 시간 복잡도를 확인해보면 다음과 같다.

https://hangbok-archive.com/computer-science/algorithm/time-complexity/

O(n)은 데이터의 입력 크기가 커질수록 실행 시간이 선형적으로 증가하지만, O(log n)은 데이터의 입력 크기가 커져도 시간의 증가율이 완만한 것을 볼 수 있다. 즉, 데이터 크기가 커질수록 O(n)은 O(log n)보다 실행 시간이 더 많이 걸린다는 것을 알 수 있다.

 

예를 들어, 충돌이 1000번 일어나 한 버킷에 1000개의 요소가 저장되어있다고 가정해보자.

이 때, LinkedList 구조에서는 노드를 순차적으로 확인해야기 때문에 검색하려는 요소가 마지막에 있을 경우 1000번의 비교를 해야한다. 반면, Red-Black Tree 구조에서는 시간복잡도가 O(log n)이기 때문에 10번의 비교만으로도 데이터를 찾을 수 있다.

 

결론적으로 데이터를 처리하기 위해 검색 속도가 중요하기 때문에, 버킷에 저장된 요소가 특정 임계값 이상이 되면 LinkedList 대신에 Red-Black Tree 구조로 변환하여 효율성을 높이는 것이다. 것이다.

---

Java 8 기준으로 해시 충돌을 해결하는 방법이 다르다.

8 이전에는 연결리스트 구조로 데이터를 처리하였지만, 이후에는 특정 임계값을 기준으로 연결리스트 구조를 사용하였다가 트리구조로 변경하여 데이터를 처리한다. 

다음에는 Red-Black Tree 구조에 대해 더 자세히 알아봐야겠다.

---

참고

https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html

HashMap (Java SE 21 & JDK 21)