java treemap compareto나 compare만 구현했을 때 제대로 동작할까요?

 자바에는 TreeMap이 있습니다. 키 오브젝트가 Obj의 인스턴스라고 해 봅시다. Obj 클래스에서 equals를 override 하지 않고 compareTo를 비교하거나, Obj를 비교하는 방법인 comparator만 생성자로 넘기면 어떻게 될까요? 그래도 잘 동작할까요?

 

---

 우리가 걱정하는 부분은 equals입니다. equals는 두 객체의 동등성을 비교합니다. 이 메서드가 어디에서 쓰이는지 TreeMap 내부에서 한 번 찾아보도록 합시다.

 

putAll에 등장합니다. Objects.equals이네요. comparator를 넘기는 것으로 보아서는, 비교하는 객체를 넘기는 것으로 보입니다. 따라서, 키 값과는 아무런 연관이 없습니다.

 

 다음 replace 입니다. 이 부분도 잘 보면, value에 대해서만 equals를 보고 있음을 알 수 있어요.

 

 valEquals 함수 안에서도 equals가 쓰이는데요. 이 메서드는 Entry 내에서 쓰입니다. 키 값에 대해서는 equals가 있으나 없으나 별 문제 없이 동작할 거 같은데요. put과 getEntry를 보겠습니다.

 

 

---

 먼저 put입니다. 원소를 추가할 때 이 메서드가 호출되게 됩니다. 해당 부분은 comparator가 있는지 없는지를 검사합니다.

 

 만약에 compareTo를 오버라이딩 했고, comparator를 넘기지 않았다면 812번째 줄이 수행되게 됩니다. k.compareTo의 결과값을 가지고 무언가를 수행함을 볼 수 있습니다. 여기서, cmp가 0일 때 oldValue를 바로 리턴해 버리는 것을 볼 수 있습니다.

 

 만약에 현재 보고 있는 루트보다 넣을 키가 더 작다면 왼쪽 자식으로, 그렇지 않다면 오른쪽 자식으로 이동합니다. rb tree도 기본적으로는 key 값의 대소를 기반으로 왼쪽으로 갈지, 오른쪽으로 갈지, 탐색을 끝낼 지를 판정합니다. 고로 해당 로직이 그대로 쓰이게 됩니다. 단지 rotate 연산이 추가로 있을 뿐입니다. 고로 순서가 같은 키가 중복해서 들어오는 걱정은 compareTo로 해결이 가능합니다.

 

 다음에 getEntry입니다. remove라던지 contains와 같이 TreeMap을 쓸 때 사용하는 주요 메서드의 경우, getEntry를 먼저 호출하게끔 되어 있습니다.

 

 여기서도 cmp의 값을 기준으로 왼쪽으로 가고, 오른쪽으로 가는 것을 반복함을 볼 수 있습니다. 당연하게도 cmp가 0인 경우, 그냥 해당 위치를 리턴해 버립니다. 즉, key 값은 compare 기반으로 동작합니다. 따라서, 키로 이용될 것은 compareTo를 overriding 하거나, 키를 compare하는 비교 클래스를 생성자의 인자로 넣어버리면 됩니다.

 

 두 키의 순서가 같다는 것은 어떻게 알 수 나요? compare을 한 결과가 0인 것으로 알 수 있습니다. 굳이 왜 equals를 안 쓸까요? tree는 루트에 있는 값과 키 값을 비교 (ordering)을 해서 키 값이 작으면 왼쪽, 크면 오른쪽으로 가는 식으로 동작합니다. 비교가 필요한데, 동일한지에 대해서만 판정하면 될까요? 아닙니다. 고로 비교 연산이 적합합니다. hash 계열은 equals랑 hashCode 둘 다 필요한데요. 이는 키 값을 탐색하는 방식이 다르기 때문입니다. hash 계열은 아래와 같이 동작합니다.

 

hashCode로 버킷값을 찾습니다.

 

 버킷에 물려 있는 키들을 보면서 정말 같은지 동등성을 확인합니다. 물론 compareTo로 비교해서 0이면 같다고 판정하는 방법이 있을 겁니다. 그렇게 쓸 수는 있는데 어색한 용법입니다.

 

---

 그런데, value의 경우 이야기가 달라집니다. 몇 가지 기능이 의도하지 않는 방향으로 동작해 버릴 수 있습니다. 대표적으로 replace 입니다.

 

 

 Obj는 compareTo만 오버라이딩 되어 있습니다. replace(key, v1, v2)는 key에 대응되는 값이 v1이면 v2로 교체합니다. 이 메서드는 제대로 수행될까요?

 

 아닙니다. 이 메서드는 내부적으로 value 값을 비교할 때 equals를 사용하기 때문입니다.

 

 curValue와 oldValue를 Objects.equals의 인자로 넘기는 것을 보면 알 수 있습니다. 정리하면, TreeMap은 키 값의 순서를 가지고 동작하는 자료구조입니다. 따라서, compare 클래스를 넣거나 compareTo를 override 하면 동작합니다. value의 경우 equals가 구현되어있지 않으면 동작하지 않는 기능이 있다는 것 정도만 알아가시면 됩니다.