해시맵에 있는 tiebreakorder는 어떤 메소드일까요?

 HashMap 클래스는 내부적으로 RB tree를 씁니다. 이것을 적용하기 위해서는 compare, 즉 비교를 할 수 있는 비교자가 재정의가 되어야 하는데 (대표적으로 TreeMap, TreeSet 등이 있는데, 비교체 구현 없이 써 보면 어떤 일이 일어날지는..) , 우리는 굳이 그것을 정의하지 않고도 쓸 수 있었습니다. 어떻게 그런 일이 가능했을까요? 답은 tieBreakOrder 메소드에 있었습니다.

 

 이 메서드에 대해 이해하기 전에, 아래 두 글을 읽고 오시는 것을 권장드립니다.

 

[관련글] 왜 equals를 재정의하면 hashCode도 같이 재정의 해야 할까요? hashCode가 모두 같을 때 어떤 일이 일어날까요?

---

 먼저 임의의 객체 하나를 만들어 보겠습니다.

 

 이름은 MyObj라고 짓겠습니다. equals랑 hashCode가 재정의 되어 있는데 모든 해시값이 0임을 알 수 있어요. 그러면 하나의 버킷에 n개의 아이템이  몰릴 수 밖에 없을 겁니다. n이 매우 크다면, java8의 hashMap은 Tree 계열의 구조로 변환합니다. 그 코드를 하나 하나 따라가 보도록 하겠습니다.

 

 

 637번째 줄에 있는 putTreeVal 안으로 들어가 보겠습니다.

 

 

 그러면 if, else if 이런 문구들이 보이는데요. 1988번째 줄과 1989번째 줄을 보면, comparable하지 않은 객체라면, 노란색으로 표시되어 있는 블록을 수행함을 알 수 있습니다. 당연하게도, 이런 찾는 과정은 재귀적으로 이루어 집니다. 그러면 여기서 tieBreakOrder라는 것이 무엇을 하는지 의문이 들 수 있습니다.

 

 

 이 메서드 내부를 보겠습니다. 두 오브젝트를 비교할 건데요. a가 null이거나, b가 null이거나, 아니면, 3번째 조건을 만족하면, 객체의 해시값을 비교함을 알 수 있습니다. 1904번째 줄을 보면, a의 identityHashCode와 b의 identityHashCode를 비교하고 있습니다. 이것은 직관적으로 보았을 때, 2번째 비교조건임을 알 수 있습니다.

 

 1번째 비교 조건은 a의 getClass.getName과 b의 getClass.getName을 비교합니다. 이것이 대체 무엇을 하는 것이냐. 간단하게 말하면, 해당 객체의 클래스 이름을 리턴하는 것입니다. 예를 들자면, 이런 것입니다.

 

 

 Main.java안에 저는 MyObj 클래스를 정의하였습니다. 그리고, HashMap 객체를 참조하는 hm도 있습니다. 이 둘을 어떻게 해 볼까요? getClass().getName()을 호출할 겁니다. 이것이 어떤 결과를 리턴할까요?

 

 

 하나는 java.util.HashMap의 객체이고, 다른 하나는 MyObj의 객체입니다. 이것과 관련된 무언가를 리턴함을 우리는 알 수 있습니다. 이것을 tieOrderBreak에서 1번째 비교 기준으로 삼습니다. 그리고 객체의 identityHashCode값을 2차 기준으로 삼습니다. 물론, 서로 다른 객체라도, identity 값은 같을 수 있으므로 조심해야 합니다.

 

 정리를 하자면, 기준대로 정렬이 된 Balanced Tree에 넣기 위해서, 저 메서드를 호출한다 정도로 이해하시면 좋습니다.

 

---

 문득, 이런 호기심이 들 수 있습니다. 클래스 명과 시스템에서 생성한 객체의 코드 순으로 비교를 한다면, 객체 A를 키값으로 매우 많이 넣고, 객체 B를 10개만 넣었을 때, 객체 B를 찾는 연산을 매우 빠르게 수행할 수 있지 않을까요? 라는 의문이 들 수 있습니다. 사실 이것은 꽤 합당한 생각입니다.

 

 왜냐하면, 2차 정렬 기준은 몰라도, 1차 정렬 기준이면, lower_bound라던지, upper_bound로 매우 빠르게 찾을 수 있기 때문입니다. 심지어, B 객체가 10개이기 때문에, 최악의 경우에도, 찾는 연산은 O(10logn) = O(logn) 정도면 될 겁니다. 정확히 말하면, 이것은 compare를 하는 횟수입니다. 중복을 찾는 연산 또한 마찬가지일 겁니다. lower bound 등으로 위치를 찾고, 거기에서부터 최대 10개만 보면 됩니다. 생각보다 별로 안 걸릴 거 같은데요? 여기서 n은 hashMap 안에 있는 객체의 총 갯수입니다. 실험 프로그램을 보겠습니다. MyObj2 클래스를 선언하였습니다.

 

 역시 hashCode는 무조건 0을 리턴하게끔 하였습니다.

 

 

 그리고 MyObj 객체 4만개, MyObj2 객체 10개가 들어갑니다.

 

 

 그리고 10만번 MyObj2 객체를 찾는 작업을 합니다. 우리는, 아. 이 정도는 정말 금방 끝나겠구나. 이렇게 생각할 겁니다. 그런데, 결과는 이상하게도 매우 긴 시간이 걸립니다.

 

 

 133.862초. 지하철이 한 역에서 다음 역으로 가는 데 평균적으로 걸리는 시간이 2분이니, 얼마나 오래 걸리는지 짐작이 가능한 부분이라 할 수 있겠습니다. 이걸 보고 유추할 수 있는 것은 충돌이 정말 많이 일어났을 때, comparable이 구현되지 않은 경우에 매우 비효율적이 될 수 있다는 겁니다. 왜 이런 현상이 나타났을까요? 분명히 저는 10개의 MyObj2 객체만을 넣어놓았으니, 이들만 비교하면 될 거 같았는데.

 

---

getTreeNode 함수를 trace 해 보겠습니다.

 

 그러면, find가 나오는데요. 이 메서드 안으로 들어가 보겠습니다.

 

 

 들어가 보면 if else if 문들이 잔뜩 나오는데요. 여기서 볼 것은 1867번째 줄입니다. pk가 p.key와 같고, k와 pk가 같으면 p를 리턴하는데, 일단 이 조건에서 equals 메서드를 씁니다. 그게 아니라면 계속 else if문을 탐색하게 되는데, 당연하게도 계속 찾지 못한다면, 밑으로 계속 내려옵니다.

 

 중간에 생략된 부분은 Comparable하냐는 조건문인데, 당연하게도 아니므로, 1877번째 줄까지 내려오게 됩니다.

 

 

 우측 트리에서 찾는다면 다행이고, 그렇지 않으면, 1879번째까지 내려와서 왼쪽 subtree를 p가 가리키게 됩니다. 이 부분도 탐색을 재귀적으로 해서 내려간다면, 전체 원소를 탐색할 겁니다. 그 어디를 봐도, tieBreakOrder는 찾을 수 없습니다.

 

 

 실제로 tieBreakOrder를 찾아보면 HashMap.java에 단 3군데밖에 없음을 알 수 있는데요. 하나는 treeify에, 다른 하나는 putVal에, 다른 하나는 자기 자신 선언부에 있습니다. 나머지 부분에서는, 설령 클래스 명을 1차 우선순위로 삼고, 객체의 시스템 해시값을 2차 우선순위로 삼았다고 해도, 클래스 명을 가지고 찾지는 않습니다. 아예 tieBreakOrder 자체를 호출하지 않습니다.

 

 이는, 내부적으로 Tree화가 되었을 때, 특정한 값을 찾기 위해서 일일히 Object의 클래스 명을 비교하는 것이, 배보다 배꼽이 더 커질 수 있기 때문인 것으로 보입니다. 클래스 명은 길 수도 있기 때문입니다. 예를 들자면, java.util.concurrenthashmap은 27자입니다.