java hashMap 살펴보기 (feat: red black tree)

서론

---

공부를 하다가 평소에는 딱히 생각 없이 사용하던 HashMap에 일반적인 put, remove와 같은 메서드 뿐만이 아니라 훨씬 더 많은 메서드가 있고 내부적으로 복잡하게 동작하는 클래스라는 것을 알게 되었다.

 

java 8 이후로 (java 8 이전 HashMap도 공부할 것이 많긴 하지만) 구현된 HashMap 클래스에 있는 중요한 내용들을 분석하고 정리하였다.

 

본론

---

Node

HashMap class 를 열었을 때 가장 먼저 Node 라는 클래스를 볼 수 있다.

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

 

 

코드에서 볼 수 있듯이 Node는 기본적인 hash, key, value등을 가지는 클래스로 HashMap의 기본적인 구성요소이다.

 

 

HashMap은 내부 데이터 관리를 데이터가 적을 때는 linked list 로 하다가 데이터가 일정 수 이상 넘어가면 red black tree로 전환하는데 둘 다 Node, TreeNode 를 단위로 만들어지고 필요할 때 쌍방으로 변환이 된다.

 

hash

 

기본적으로 Objects 클래스에 아래와 같은 hashCode 메서드가 있다. 그런데 왜 내부에 hash 메서드를 또 구현했을까?

//Objects 내부 메서드
public native int hashCode();


//hash 보조 메서드
static final int hash(Object key){
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
///

 

 

해당 메서드는 해시 충돌 가능성을 줄이기 위한 보조 해시 함수로 아래와 같이 값을 넣거나 지울 때 사용된다.

 

 

(hash는 보통 [hashValue % m] 형태로 사용되는데 m이 소수일 때 가장 효율적인 분배가 발생한다, 하지만 해당 구현에서는 2의 승수로 나누기에 -> 하위 a개의 비트만 사용하기에 해시 충돌 가능성이 높아서 보조 해시 함수가 필요하다. )

 

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

 

 

공부를 하면서 본 네이버 기술 블로그 글에 따르면 java 7에 비해서 보조 해시 함수 로직이 굉장히 간단하게 변했다고 하는데 그 이유는

1. 데이터가 많아지면 링크드 리스트 대신 트리를 사용하게 되어 충돌 발생시 성능 문제가 완화
2. 최근 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아 보조 해시 함수의 효과가 크지 않다.

라고 한다.

 

 

TreeNode

 

데이터가 일정 수 넘어가 레드 블랙 트리가 되었을 때를 위한 클래스이다.

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

 

 

해당 클래스 내에 레드 블랙 트리를 관라하기 위한 putNode, removeNode, roateLeft, rotateRight
등등의 여러 메서드가 있다.

 

 

 

이러한 메서드들 중 linked list <---> red balck tree 를 지원해주는 untreeify, treeify 메서드도 있다.

두 메서드의 코드를 간단히 살펴보면

 

untreeify

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    for (Node<K,V> q = this; q != null; q = q.next) {
        Node<K,V> p = map.replacementNode(q, null); // treeNode를 Node로 변환해준다.
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

 

 

코드에서도 볼 수 있듯이 HashMap을 받아서 트리의 모든 노드를 순환하면서 TreeNode들을 Node로 바꾸고 연결시켜 linked list로 만들어준다.

 

 

 

treeify

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;

    ...
    //root 가 없을 경우 현재 TreeNode를 부모로 설정한다.
    if (root == null) {
        x.parent = null;
        x.red = false;
        root = x;
    }
    ...

    //자식 노드로 설정하기 위해 순서를 정해준다. hash값에 따라 먼저 순서를 정해주고 hash값이 같으면 tieBreakOrder 메서드를 통해
    //순서를 정해준다. (tieBreakOrder는 아래서 설명할 예정이다.)
    if ((ph = p.hash) > h)
        { dir = -1; }
    else if (ph < h)
        { dir = 1; }
    else if ((kc == null && (kc = comparableClassFor(k)) == null) 
             || (dir = compareComparables(kc, k, pk)) == 0)
        { dir = tieBreakOrder(k, pk); }

    ...

    //그렇게 순회하면서  linked list를 red black tree로 만들어준다.
    if ((p = (dir <= 0) ? p.left : p.right) == null) {
        x.parent = xp;
        if (dir <= 0)
            xp.left = x;
        else
            xp.right = x;
        root = balanceInsertion(root, x);
        break;
    }

    ....

    //그 후 tree의 root를 배열 제일 앞에 넣어준다.
    root = balanceInsertion(root, x);    

 

이렇게 linked list 로 이루어져있던 배열을 트리로 만듬으로 해시 충돌이 발생해도 좀 더 빠른 성능을 보장해준다.

 

 

 

tieBreakOrder

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null || (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0) {
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
    }
    return d;
}

 

 

코드에서 볼 수 있듯이 Tree Node를 넣을 때 크기를 비교할 수 없는 객체에 대해서 비교를 해주는데 identityHashCode 메서드를 통해 hashCode() 가 구현되어져 있는 객체라도 default hashCode로 얻은 hash 값으로 비교한다.

 

 

기준 상수들

//크기를 지정하지 않고 map을 생성할 때 쓰이는 상수
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//map의 최대 크기이다, hash 값은 int 로 반환되기 때문에 2^32까지 밖에 표현이 안되고 해당 클래스에서는 2^30을 최대로 했다.
//물론 index의 최대 크기인거지 그보다 더 많은 값들이 map에 들어갈 수 있다.
static final int MAXIMUM_CAPACITY = 1 << 30;

//사이즈를 조정할 때 해당 값을 기준으로 증가시킨다, 즉 100의 길이에서 75가 넘으면 사이즈를 키워준다.
static final float DEFAULT_LOAD_FACTOR = 0.75f;


//해시 버켓 하나에 해당 값 이상의 데이터가 있으면 linked list에서 tree로 바꿔준다.
static final int TREEIFY_THRESHOLD = 8;


//반대로 해당 값 아래로 떨어지면 tree를 linked list로 바꿔준다.
//하나의 값을 기준으로 삼지 않는 이유는 특정 값에서 커졌다 작아졌다 하면 계속적인 변경으로 성능이 떨어짐을 예방한 것이다.
static final int UNTREEIFY_THRESHOLD = 6;

 

 

결론

---

위 메서드들 말고도 더 다양한 메서드들이 있다.

• map 기능을 위한 기본적인 메서드
• clone, serialization
• compute, computeIfPresent...

다 살펴보기는 양이 너무 많아서 이번 글에서는 내가 궁금했던 데이터를 관리하는 자료 구조와 내부 동작 과정을 중점으로 다뤘다.

 

공부를 하면서 학부생 때 배웠던 red black tree, hash등을 복습하면서 기초의 중요성을 다시 한번 느꼈다, 만간에 좀 더 깊이있게 공부할 예정이다.