해시 맵 내부는 충돌 시 언제 트리 구조로 변경될까?
내가 알고 있는 지식이나 네이버 D2 블로그나 여러 블로그에서 확인한 내용은
내부에 버킷이 갖고 있는 노드의 개수가 8개 이상일 때 트리로 변경된다는 내용이었다.
여기서 내가 궁금한 건 정말 한 버킷에 노드의 개수가 8개 이상일 때 바로 연결 리스트에서 트리로 바로 바뀌는 것일까?
한번 내부를 확인해보자!!!!!
내부 탐색을 위한 예제 코드는 다음과 같다. (jdk 1.8 기준)
HashMap에 더미 객체를 계속 생성해서 put 하는 간단한 예제 코드이다.
눈여겨볼 것은 해시 코드 재정의 시 1로 한 것이다.
해시 코드를 1로 재정의 한 이유는 같은 버킷 인덱스에 여러 노드를 쌓아 8개 일 때 트리로 변경되는지 확인하기 위함이다.
이제 본격적으로 내부 구조를 분석하면서 확인해보자.
put()
첫 번째 데이터인 map.put(new Dummy(1), 1); 을 수행하면 어떻게 되는지 확인해보자.
put 메서드 내부는 다음과 같다.
넘겨받은 key 값과 value 값인 new Dummy(1)을 해싱하고
putVal() 메서드에 넘겨주며 호출한다..!
hash() 내부를 보자.
hash()
넘겨받은 키의 해시 코드를 호출하고 xor 연산을 수행한다.
key가 null이라면 0을 리턴하며, null이 아니라면 key 값을 int형으로 변형하는 것을 확인할 수 있다.
key의 Object class에 있는 해시 코드 메서드를 실행하고 (재정의 하였다면 재정의한 해시 코드가 호출)
얻은 해시 코드를 16번 오른쪽으로 unsigned right shift 한 값과 XOR을 하여 해시를 얻어낸다.
이전에 더미 객체의 해시 함수를 재정의함으로써 해시함수를 통해 리턴되는 값은 내가 원하는 값인 1이 최종적으로 리턴된다.
해시하는 연산 과정이 궁금한 분은 갓준우님의 블로그를 참고하면 좋을 것 같다.
putVal()
다시 put으로 돌아와 해시함수를 통해 얻은 해시값 1을 putVal()로 넘겨준다. putVal()를 확인해보자.
holly.. 생각보다 길다.. 하지만 640 Line ~ 651 Line을 살펴보면 우리가 확인하고자 하는 목표가 담겨있음을 확인할 수 있다.
차근차근 분석해보자.
628 Line의 조건은 해시 맵 멤버 변수인 table을 지역변수인 tab에 옮기고 값이 들어있는지, 길이를 확인한다.
처음으로 값을 넣고 있기 때문에 해당 조건은 true가 되면서 resize()를 수행하게 된다.
resize()를 파악하려면 내용이 길어져 resize()에 내부는 다른 포스팅에서 설명할 예정이다.
resize() 내부 흐름을 확인해보면 해시 맵이 언제 크기를 늘려야 할지 판단하고 길이를 재조정한다.
첫 번째로 값을 삽입하게 되면 628 Line 조건을 만족하게 되어 각 지역변수에 값이 세팅된다.
그 후 630 Line을 수행한다.
630 Line의 조건은 resize()를 거친 후 (hash % n - 1)의 index에 노드가 존재하지 않으면 새로운 노드를 만들어 삽입하고
해당 putVal() 메서드를 종료한다.
즉, 첫번째 데이터는 해시 함수를 거쳐 나온 값을 버킷 인덱스로 하여 해당 버킷에 value를 노드 객체로 만들어 저장한다.
두 번째 데이터부터는 632 Line부터 수행한다.
632 Line else 부터는 해시값에 속하는 버킷 인덱스에 값이 존재하는 경우이다.
634 Line의 조건은 hash값과 실제 값이 같은지 비교한 후 같다면 기존에 있던 값을 교체한다.
(hashCode와 equals를 같이 재정의해야 하는 이유 중 하나!)
637 Line은 버킷이 링크드 리스트가 아닌 이미 트리로 변경되었을 때 트리노드인지 판단하고 트리노드라면 put 한다.
즉 트리로 변경된 이후부터이기에 현재 흐름상 무시해도 괜찮다.
젤 중요한 부분이다. 이 else 문에서 treeifyBin()을 통해 트리로 변경된다는 것을 알 수 있다.
for 문을 통해 bitCount를 증가시키면서 조건문들을 확인한다.
(647 Line은 634 Line의 조건과 같다. hash값과 실제 값이 같은지 비교한 후 같다면 기존에 있던 값을 교체한다.)
여기서 bitCount는 무엇을 의미할까?
디버깅을 통해 확인한 결과 버킷에 담긴 노드의 개수임을 확인할 수 있었다.
버킷에 담긴 노드의 개수 만큼 반복한다. 왜냐하면 버킷에 담긴 노드들은 각 Node 포인터로 연결되어 있는
링크드 리스트이기 때문에 첫 노드부터 순차 접근을 한다.
반복문의 내부 구현 내용은 다음과 같다.
641 Line은 현재 노드에 다음 노드에 값이 없으면 다음 노드에 현재 값을 연결해준다.
그러고 나서 현재 버킷의 현재 노드의 카운트가 TREEIFY_TRESHOLD - 1보다 같거나 크면 트리로 정의한다..!
(TREEIFY_TRESHOLD의 값은 8이다.)
즉 해석해보면 해시값에 맞는 버킷 인덱스에 담긴 노드들의 개수가 8개 이상일 경우 (bitCount는 0부터 시작)
treeifybin()을 수행하게 된다.
오오 여기까진 다른 블로그들과 D2에 설명된 내용과 일치한다.
그럼 treeifyBin()의 내부를 살펴보자.
treeifyBin()
내부를 보니 759 Line부터 트리로 변경됨을 확인할 수 있다. 마지막 관문인 757 Line의 조건을 살펴보자.
넘어오는 파라미터인 Node<K, V>[] tab은 실제 해시 맵이 가지고 있는 멤버 변수인 버킷 배열이다.
이 버킷 배열의 길이가 MIN_TREEIFY_CAPACITY 보다 작으면 resize()를 진행한다.
MIN_TREEIFY_CAPACITY의 값은 다음과 같다.
즉, 해시 맵의 크기가 64보다 작으면 트리로 변환시켜주지 않는다.
앗.. 일단 특정 버킷의 노드 개수가 8개이면 트리로 바로 변환되는 줄 알았는데 아니었다.
실제로 디버깅시 계속 resize()가 되고, 해당 버킷의 개수가 8개 이상 쌓이면 resize() 함수를 통해 다른 버킷으로 데이터를 옮긴다. resize()를 계속 거쳐 해시맵의 크기가 64개가 되고 버킷에 담긴 노드의 개수가 8개가 되어서야 비로소 트리로 변환된다.
이때까지의 과정을 요약해보면 다음과 같다.
1. 해시 코드로 나온 값을 버킷 인덱스로 삼고, 해당 버킷에 값이 없으면 값을 보관한다.
2. 또 다른 값들을 삽입시 특정 버킷에 같은 해시값과 코드가 존재하는지 확인한다.
같으면 대체해주고 다르면 현재 존재하는 노드의 next 포인트에 연결을 해준다. (링크드 리스트 원리)
3. 특정 버킷에 노드를 계속 연결해주고 노드의 길이가 8개가 되었을 경우 treeifyBin()을 수행한다.
4. treeifyBin()에서 넘어오는 파라미터는 해시 맵 내부에서 관리하고 있는 버킷 배열이며
해시 맵의 크기가 64보다 작으면 resize()를 통해 하나의 버킷에 많은 데이터를 관리하지 않도록 데이터를 다른 버킷에 분할하여 관리한다.
5. 해시 맵의 크기가 64보다 같거나 커지면 그때부터 버킷 내부를 링크드 리스트가 아닌 트리로 변경하여 관리한다.
'java' 카테고리의 다른 글
| [자바 병렬 프로그래밍] Lock에 대한 궁금점 (2) | 2021.12.21 |
|---|---|
| compareTo()를 재정의 시 equals()를 왜 함께 재정의 해야할까? (0) | 2021.01.25 |
댓글