[자료구조] HashMap에서 Treeify를 도입한 Java 8의 성능 개선기 (feat. TREEIFY_THRESHOLD)

반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

 

 

💋 인트로

요즘 진행중인 CS 스터디에서 신기한 이야기를 들었다.

바로바로 자바 HashMap은 hash collision을 사용하기 위한 방법으로 separate chaining을 사용하며, 한 인덱스에 충돌된 데이터 개수에 따라, LinkedList와 Tree 구조를 왔다갔다 한다는 정보!

그래서 열심히 찾아보았다.

 

💋 Java HashMap

✔️ hash collision 해결 방법 - separate chaining

Java의 HashMap 클래스는 separate chaining 방식을 사용한다.

 

이미지 출처:  https://www.baeldung.com/cs/hashing-separate-chaining

 

 

Separate chaining은 해시 충돌이 발생할 경우 해당 버킷(인덱스)에 여러 개의 항목을 저장하는 방식으로, 이를 주로(보통) LinkedList로 구현한다(고 설명한다)

 

물론 HashMap을 어떻게 구현했는지에 따라서 LinkedList를 사용할 수도 있고,,, 등등 이 개념의 핵심은 한 인덱스에 그냥 여러 데이터를 몰아 넣어버린다는 것이지, 어떤 자료구조를 안에 몰아놨는지가 중요한 것은 아니다. 실제로도 구현 언어별로 HashMap을 구현한 방식은 천차만별이다. (딱 규칙이 뽝 있는 건 아니다.)

 

그치만, 나는 백엔드 개발자로 자바를 주로 사용하니깐 어떻게 구현되어 있는지 알면 좋다!

 

✔️ Java 7까지: LinkedList만을 사용한 separate chaining의 단점

Java 7까지의 HashMap에서는 separate chaining을 구현할 때 LinkedList만을 사용했다.

해시 충돌이 발생하면 해당 인덱스에 이미 들어있는 LinkedList에 노드를 그냥 추가했다. 문제점이 뭐였을까? LinkedList의 길이가 길어지면 알다시피 탐색하는데 O(n) 시간복잡도라는 아주 긴긴 시간이 들기 때문에 성능 문제가 발생했다.

 

해시 테이블은 배열 개념에다가, 진짜 빨리 검색해보고 싶어서 hash function까지 데려온 그런 속도를 위한 구조인데, 이렇게 속도가 줄어드는 것은 hash 자료구조에 속도를 기대하고 사용하던 사람들에게 치명적이다.

 

✔️ Java 8부터: LinkedList와 Tree를 오가며 성능 향상!

Java 8에서는 이러한 성능 문제를 개선하고자 LinkedList만 사용하는 대신 self-balancing 트리 중 하나인 Red-Black Tree로의 변환을 도입했다.

 

해시 충돌이 발생한 인덱스에 처음에는 일단 기존처럼 LinkedList에 노드를 추가하는 방식을 사용하되, 노드 개수가 일정 임계값을 초과하면 데이터 구조를 LinkedList에서 트리 구조로 변환한다. 이렇게 하면 검색 연산의 성능을 향상시킬 수 있다.

 

💋 HashMap.java 소스 코드 까보기

openjdk 깃허브 소스 코드에서 TREEIFY_THRESHOLD를 검색하면 쉽게 소스 코드를 찾을 수 있다.

소스 코드 바로가기

 

관련된 소스 코드를 일부 발췌해 왔다.

 

✔️ TREEIFY_THRESHOLD & UNTREEIFY_THRESHOLD

 

/**
 * 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.
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 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.
 */
static final int UNTREEIFY_THRESHOLD = 6;

 

• TREEIFY_THRESHOLD
• 한 인덱스에 저장된 데이터의 개수가 트리로 변환되기 위한 임계값
• 만약 한 인덱스에 저장된 데이터의 개수가 8개 이상이면, 해당 인덱스의 데이터는 LinkedList에서 Red-Black Tree로 변환된다.
• 데이터가 많은 상황에서 트리 구조는 검색 연산에서 더 좋은 성능을 가진다.
• UNTREEIFY_THRESHOLD
• 한 인덱스에 저장된 데이터의 개수가 다시 LinkedList로 변환되기 위한 임계값
• 만약 한 인덱스에 저장된 데이터의 개수가 6개 이하로 줄어들면, 해당 인덱스의 트리 구조는 다시 LinkedList로 변환한다.
• 작은 크기의 데이터에서는 레퍼런스 저장에 큰 메모리를 차지하는 트리보다도, LinkedList가 더 효율적이기 때문이다.

 

 

실제로 이 상수를 사용하는 코드를 다 읽기엔 너무 어려워서 슬쩍 훔쳐봤는데, 아래같이 TREEIFY_THRESHOLD 를 넘어가는 경우에는 treeify()라는 메서드를 호출한다.

 

 

 

✔️ treeify()

treeify()라는 메서드도 한번 훔쳐봤는데, LinkedList로 되어 있던 구조를 막 트리 구조로 변경하는 과정을 담고 있다.

 

 

✔️ 왜 하필 6개, 8개인가?

데이터 개수가 너무 적을 때는 트리를 사용하는 것이 그닥 더 빠르지도 않다.

트리는 자료구조가 리스트보다 복잡하기 때문에 자료구조를 만드는 것 자체에 오버헤드가 있다. 불필요하게 저장해야 하는 정보가 더 많아서 메모리에 부담이 간다는 말이다.

그래서 처음에는 LinkedList에 데이터를 차례대로 저장하다가, 어느 순간부터는 트리가 메모리 오버헤드를 고려하더라도 더 성능이 좋은 시점이 온다. 그게 7개이다. 1+2+4로 딱 perfect binary tree가 된 경우부터, 트리의 성능이 더 좋아진다.

그렇다면 임계값을 7개로 설정하고 7개 이상부터는 트리, 7개 미만부터는 리스트로 결정하면 될 것 같은데, 1개씩 떼어서 6개, 8개로 설정한 이유는 뭘까?

너무 자주 바꾸는 것 역시 무리다. 해시 충돌로 인한 데이터가 계속 6, 7, 6, 7로 왔다갔다 하는 경우에 쬐에에에에에곰의 검색 성능 향상을 위해서 계속해서 자료구조를 바꾸는 것은 성능 저하에 직빵이다. (위에서 treeify() 메서드만 봐도 저거 실행하는데 한세월 걸릴 듯한 비쥬얼)

그래서 6~8 사이에서는 조금의 갭을 두고 자주 변경되지는 않도록 buffer를 두는 것이다.

 

 

💋 참고자료

• https://stackoverflow.com/questions/42422469/why-does-a-hashmap-contain-a-linkedlist-instead-of-an-avl-tree
• https://stackoverflow.com/questions/55153953/is-there-any-reason-to-have-8-on-treeify-threshold-in-java-hashmap
• https://www.studytonight.com/post/hashmap-performance-improvements-in-java-8-using-treeify-threshold
• https://en.wikipedia.org/wiki/Hash_table#Other_data_structures_for_separate_chaining

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!