TreeMap에서 순서는 어떻게 정해지며 순서가 같으면 어떻게 될까?

초록·2023년 12월 5일

바쁘신 분들을 위한 결론 ⚡️

순서는 Key 클래스의 Comparable 구현이나 트리맵 생성자에 Comparator를 전달함으로써 결정할 수 있음. Key 클래스가 Comparable 구현도 하지않고 기본 생성자를 사용한다면 예외를 발생시킬 것. Integer, String과 같은 클래스는 이미 구현되어있어서 예외발생 X

순서가 같은 게 TreeMap에 추가되면 key-value쌍이 그대로 대체되는 게 아니라, 기존 key는 그대로 두고 value만 대체되므로 유의가 필요함.
HashMap 버킷에 사용되는 트리의 자료구조인 Tree Node는 tieBreakOrder() 메서드로 임의의 순서정보를 기입함으로써 중복으로 인한 문제를 해소함.

궁금증

Java의 TreeMap은 순서를 지원하는 Key-Value 쌍이란 건 알고 있지만, 순서가 같으면 어떻게 처리되는지 궁금해서 구글링을 해보았지만 순서를 지정하는 방법만 나오지 같으면 어떻게 되는지 명확하게 찾을 수 없었습니다.

트리맵의 순서

트리맵의 순서는 트리맵을 생성할 때 생성자에 Comparator 인터페이스의 구현을 넣어주거나 Key로 넣을 객체가 Comparable의 compareTo 메서드를 구현해주면 그 순서대로 순서가 지정됩니다.

class User implements Comparable{	
        // ...
		@Override
        public int compareTo(Object o){
            if (o == null)
                return 1;
            User user = (User) o;
            return this.name.compareTo(user.name);
        }
}

// 귀찮으니 null check는 안 하겠음
Map<User, Integer> map = new TreeMap<>((a, b) -> a.name.compareTo(b.name));

하지만 Key에 들어갈 클래스가 별도로 Comparable을 구현해주지 않은채로 new TreeMap()<Key, Value> 이런식으로 생성자에 아무것도 넣어주지 않으면, 아래와 같이 Comparable을 구현하지 않았다고 예외를 뱉습니다.

Exception in thread "main" java.lang.ClassCastException: class Practice$User cannot be cast to class java.lang.Comparable (Practice$User is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
	at java.base/java.util.TreeMap.put(TreeMap.java:536)
	at Practice.main(Practice.java:37)

String, Integer같은 클래스들은 Comparable을 구현하기 때문에 key로 숫자와 문자열을 넣으면 별도의 구현없이도 알아서 잘 동작합니다만(자연 순서(Natural order)), 위 예시처럼 별도의 객체를 key로 사용하려면 순서정보를 입력해주어야만합니다.

순서가 같다면?

예시를 보며 말씀드리는 게 쉬울 것 같아 예시부터 보겠습니다.

아래 예시에선 User라는 클래스의 name값(생성자의 첫번째 인자인 알파벳)을 기반으로 순서정보를 판단합니다.
총 4명의 user를 map에 넣었는데, 이름이 같은 user를 2개 넣었습니다.

Map<User, String> map = new TreeMap<>((a, b) -> a.name.compareTo(b.name));

// key : User(이름, 나이)
// value : 이메일
map.put(new User("A", 1), "a");
map.put(new User("A", 2), "b");
map.put(new User("B", 3), "c");
map.put(new User("C", 4), "d");

map.entrySet().stream().forEach(entry -> System.out.printf("key : %s, value: %s \n", entry.getKey(), entry.getValue()));

// key : A 1, value: b 
// key : B 3, value: c 
// key : C 4, value: d

그런데 결과가 제 예상 밖이었습니다. user name 순서대로 잘 나왔고, value만 봤을 땐 나중에 추가된 b값이 출력되긴 했는데, key값이 맨 처음에 입력한 user인 (A 1)로 나왔습니다.

즉, 순서정보가 동일할 때 기존 노드를 대체하긴 하는데, 값만 대체하고 key는 대체하지 않는 작동방식이라는 걸 알 수 있습니다.

사실 Comparable을 구현하는 클래스는 (x.compareTo(y) == 0) == (x.equals(y)) 를 지키도록 필수는 아니지만 권고한다고 합니다. Comparable을 구현하고 이 권고를 지키지 않는 모든 클래스는 그 사실을 명시해야 합니다.

이 점을 유의해서, Key의 어느부분까지 일치하면 중복으로 인정할지 잘 정해서 Comparator를 작성해야하겠습니다.

이 내용은 TreeMap의 put 메서드의 설명에도 나와있습니다.

* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old value is replaced.
...
public V put(K key, V value) {
	...
	Comparator<? super K> cpr = comparator;
    if (cpr != null) {
         do {
    	    parent = t;
    	    cmp = cpr.compare(key, t.key); // key로 비교함
    	    if (cmp < 0) // target key보다 작으면 왼쪽으로
    			t = t.left;
    		else if (cmp > 0) target key보다 크면 오른쪽으로
    			t = t.right;
    		else // 같으면 기존 key의 value를 대체함
    			return t.setValue(value);
    	} while (t != null);
    }
}

HashMap의 내부 트리

Java의 HashMap은 내부적으로 배열로 이루어져있고 각 원소는 각자 링크드리스트로 구성되어있습니다. 하지만 링크드리스트가 너무 길어지면 탐색시간을 줄이기 위해 링크드리스트가 아닌 TreeNode(TreeMap 아님)라는 자료구조를 사용하며 이는 Red-black Tree 구조를 사용합니다. TreeMap도 Red-black Tree로 구성되어있죠.

하지만 HashMap의 TreeNode의 경우, 순서정보가 일치하면 TreeMap처럼 값을 대체하는 게 아닌, tieBreakOrder() 메서드로 임의의 순서정보를 생성해 삽입하기 때문에 값을 덮어씌우지 않습니다. 그럼 임의의 순서를 어떻게 정할까요? tieBreakOrder()의 경우 클래스명을 첫번째로, 객체 고유의 해시값인 System.identityHashCode()값을 두번째 기준으로 순서를 정합니다.

그런데 HashMap에 삽입할 땐 이 메서드를 써서 중복을 막지만, HashMap을 조회할 땐 이 메서드를 사용하지는 않고 == 연산자로 동일한 객체인지 먼저 시도해보고, 동일하지 않다면 equals 연산자를 사용해 동등한 객체인지 확인합니다.