HashMap은 탐색시 어떻게 O(1)의 성능을 낼까?

들어가며

 

HashMap은 어떻게 값을 저장하고 관리하는지 또 탐색시 O(1)의 성능은 어떻게 내는지 궁금하여 정리하고자 한다.

 

이를 분석하기 전 해시 라는 개념부터 정리해본다.

 

해당 포스팅은 Java 8 기준으로 작성됐다.

 

 

Hash란?

 

어떠한 값이 있을 때 hasing 함수에 이 값을 입력하면 해시 값으로 추출할 수 있다.

동일한 값으로는 동일한 해시 값을 얻을 수 있다.

추출된 해시 값은 자료구조에서 데이터를 빠르게 탐색할 때 쓰인다.

 

 

어떻게 데이터를 빠르게 탐색할 수 있을까?

 

해시를 이용한 데이터 탐색은 내부적으로 O(1) 탐색이 가능한 배열을 사용하여 진행된다.

다음은 탐색에 사용되는 해시테이블 (2차원배열)의 모습이다.

 

(실제 Java 8 HashMap은 내부적으로 slot을 연결리스트 또는 TreeNode 타입의 1차원 배열을 사용하여 관리한다. 이해를 돕기 위해 2차원 배열로 표현했다.)

 

 

해시 테이블은 N 개의 bucket을 가지며 bucket 1개는 1개 이상의 slot을 가진다.

그리고 slot 하나는 실제 데이터가 저장되는 공간이므로 bucket[0][0]으로 data 1 을 가져올 수 있다.

 

 

그럼 bucket 내 slot에 데이터를 저장하거나 탐색하기 위해서는 인덱스 값이 필요한대 인덱스 값은 어떻게 얻어올까?

 

인덱스 값은 key 값을 해싱 함수로 해싱 하여 얻은 해시 값을 통해 연산하여 추출한다.

 

아래의 코드는 (0 <= index 값 < bucket size) 조건을 만족하는 index 값을 얻기위한 HashMap 내부에 일부 코드다.

 

(bucketSize - 1) & hash

 

 

왜 굳이 인덱스 값을 얻을 때 해시 값을 이용하는 걸까?

 

길이가 서로 다른 값을 해싱 함수를 통해 해싱 하더라도 해싱된 결과의 해시 값 길이는 모두 같다. 따라서 길이에 관련하여 해시가 효율적이기 때문에 사용하는것이지 않을까 생각한다.

 

 

Key-Value 형식으로 단일 value를 저장하는 것일 텐데 value가 저장되는 slot이 왜 여러개일까?

 

해싱 함수에 입력되는 key 값은 그 케이스가 무한하지만 출력되는 해시 값은 유한하기 때문에 결국 다른 key 값으로 동일한 해시 값을 얻을 수 있게된다. 이를 해시충돌 이라고 부른다.

 

비둘기집 원리를 생각하면 된다.

ko.wikipedia.org/wiki/%EB%B9%84%EB%91%98%EA%B8%B0%EC%A7%91_%EC%9B%90%EB%A6%AC

비둘기집 원리 - 위키백과, 우리 모두의 백과사전

 

그러므로 해시충돌로 인해 key 값 하나당 여러 데이터가 저장되는 경우가 생길것을 예상해 slot을 미리 여러개 만들어 둔것이다.

 

즉, slot이 하나 밖에 없다면 해시충돌이 일어나는 순간 에러를 뿜는다고 생각하면된다.

 

 

해시 충돌을 예방하는 방법이 있을까?

 

다음과 같은 방법이 존재한다.

• 해시 충돌 발생시 현재 데이터를 저장하려는 bucket에서 일정 개수 건너 뛰어 저장한다.
• 이미 해싱된 값을 재해싱하여 인덱스 값을 새로 추출한다.
• slot을 연결리스트로 구성하여 새로운 데이터를 노드로 계속 추가한다.

 

 

이제 해시는 어떤 개념으로 O(1) 탐색을 진행하는지 알겠으니 이런 방법을 탐색에 사용하는 Java의 HashMap 구현 코드를 살펴보자.

 

 

HashMap의 O(1) 탐색 방법

 

HashMap은 해시 테이블이 노드 배열로 되어있으며 각 노드는 연결리스트 형태로 되어있어 해시 충돌이 발생하더라도 새로운 노드로 저장한다. (단, 연결리스트 형태는 슬롯이 8개 이하 일때만 사용하고 8개가 초과되면 성능이 떨어져 트리 노드 형태로 전환된다.)

 

HashMap의 key-value 쌍으로 값을 저장하는 V put(K key, V value)의 내부 구조를 분석해보자.

핵심 내용에만 주석을 달아 보았다.

 

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}


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


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)       // table <- HashMap이 관리중인 hash table을 의미.
            n = (tab = resize()).length;                          // hash table 초기화.
        if ((p = tab[i = (n - 1) & hash]) == null)                // hash 값 연산을 통해 얻은 인덱스로 접근한 bucket에 값이 없을시
            tab[i] = newNode(hash, key, value, null);             // 새로운 노드를 생성해 slot(Node)으로 put.
        else {                                                    // hash 값 연산을 통해 인덱스로 접근한 bucket에 값이 이미 존재한다면
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;                                            // 이미 존재하는 노드의 해시, 키 값과 새로 put 하려는 key의 해시, key 값이 동일하다면 
                                                                  // 38~44 행에서 새로운 value로 overwriting 해주고 종료된다.
            else if (p instanceof TreeNode) 
                                                                  // 해시충돌된 상태이고 slot이 8개가 초과되어 TreeNode 형태로 
                                                                  // 관리되고 있다면 TreeNode 형태로 put.
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {                                                // 해시충돌된 상태이고 TreeNode로 관리되고있지 않다면(slot 개수가 8개 이하인 상태)
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {                   //slot(Node)을 추가하기 위해 마지막 slot(Node)를 찾음.
                        p.next = newNode(hash, key, value, null); //slot(Node) put.
                        if (binCount >= TREEIFY_THRESHOLD - 1)    // slot이 9개 이상이 되었다면 
                            treeifyBin(tab, hash);                // TreeNode 형태로 자료구조를 변경.
                        break;
                    }
                    if (e.hash == hash &&                         // 다음 slot(Node)의 hash, key와 put 하려는 key의 해시, key 값이 동일하다면
                        ((k = e.key) == key || (key != null && key.equals(k)))) // 38~44 행에서 새로운 value로 overwriting 해주고 종료된다.
                        break;
                    p = e;
                }
            }
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}