HashMap - 자바코드 뜯어보기(treeify 중심으로)

자바의 hashMap은 내부 배열의 길이가 64, 한 버킷의 요소 수가 8 이상이 되면 해당 배열의 요소들은 연결리스트가 아닌 레드-블랙 트리 기반의 트리노드로 구현된다.


putVal의 로직 중 다음 로직을 보면 binCount를 반복하면서 TREEIFY_THRESHOLD-1 값에 다다를 때 treeifyBin을 호출한다.

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

 

 

1. treeifyBin

첫번째 조건으로 배열의 길이를 측정하고 64 미만이라면 treeify하지 않고 resize()를 호출한다.

그 외 조건에서는 replacementTreeNode를 이용해 TreeNode를 생성하고 해당 버킷에 대한 treeify를 수행한다.

 

 

2. treeify

treeify는 해시맵의 내부배열 요소를 Node(연결리스트) 에서 TreeNode(레드-블랙 트리, 연결리스트 통합) 으로 변경하는 작업을 수행한다.

 

 

3.balanceInsertion

레드-블랙 트리의 속성에 맞게 노드 구조를 재조정한다.

 

4.moveRootToFront

메서드 이름만 보면 단순히 root를 해당 버킷의 요소로 할당만 하는것 같지만

추가적으로 root.next에 기존의 연결리스트를 참조한다.

 

여기서 중요한 점은 hashMap의 TreeNode는 레드-블랙 트리의 특성과 LinkedList의 특성을 동시에 가지며,
이 메서드에서는 treeify를 호출한 버킷의 요소를 기존의 Node(LinkedList) 형식에서 TreeNode(red-black tree)로 변환하고

root(TreeNode).next에 기존의 Node를 연결하여 순서를 계속 기억하고 있다는 점이다.
이 연결 순서를 기억하기 위해 putTreeVal 같은 연산을 시행할 때, 해당 메서드 내부에서는 

TreeNode의 값만을 연산하는것이 아니라, Node의 순서또한 업데이트한다.   

이는 효율성의 문제로 LinkedList형식으로 돌아갈 때 사용하는 untreeify를 위해서이다.

 

5. checkInvariants

Node -> TreeNode 형식으로 변환되면서 참조, 속성에 대해서 위반사항이 없는지 확인한다.

 

---

treeify를 정리하면서 해시맵이 단순히 연결리스트 -> 레드-블랙 트리 구조로 변경되는것이

아니라 레드-블랙 트리 + 연결리스트 구조를 합친 TreeNode로 변경되는것이 놀라웠다.

 

그래서 putTreeVal 같은 메서드 호출시 내부 로직을 보면 보면 값을

TreeNode에 추가함과 동시에 연결리스트에도 추가한 값의 순서를 저장한다.