Java 의문점 정리 3 — Map 종류와 동작방식

우테코 8기 3주 차 Java 미션을 하면서
Map과 관련된 의문점들을 정리해 봤다.

 

1. Map이란?

Java Collections Framework 중 하나의 인터페이스로
key-value 쌍을 가지고 있다.

Java Collections Framework: 동적으로 변할 수 있는 자료구조 List, Set, Map
Array는 참조 타입

 

2. Map 종류

- HashMap
빠르고 정렬 순서가 없다.

- TreeMap
Key에 따라서 정렬된다. (글자, 숫자순)

- LinkedHashMap
Key 삽입 순서에 맞춰 정렬된다.

 

3. TreeMap은 어떻게 Key를 정렬할까?

TreeMap의 put 메서드 코드를 살펴보면
어느 정도 추측할 수 있다.

private V put(K key, V value, boolean replaceOld) {
        Entry<K,V> t = root;
        ...
        int cmp;
        Entry<K,V> parent;

        Comparator<? super K> cpr = comparator;
        // 1번
        if (cpr != null) {
            ...
        } else {
            ...
            Comparable<? super K> k = (Comparable<? super K>) key;
            // 2번
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                // 3번
                else {
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        }
        // 4번
        addEntry(key, value, parent, cmp < 0);
	return null;
}

- 1번
사용자가 전달한 Comparator(정렬방식)에 따라서 분기된다.
없으면 compareTo를 사용해 정렬한다.

- 2번
기존 엔트리를 순회하면서 삽입 키와 비교한다.

- 3번
일치하면 값을 수정한다.

- 4번
key-value는  저장한 위치에 따라서 parent 엔트리에 추가된다.

cmp 값은 기준값이 비교값보다 크면 양수, 작으면 음수 동일하면 0을 갖는다.

 

4. LinkedHashMap은 어떻게 Key 순서를 유지할까?

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements SequencedMap<K,V>

LinkedHashMap은 HashMap 저장 구조를 그대로 사용한다.

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
    	super(hash, key, value, next);
	}
}

다만, 삽입 순서를 유지하기 위해
Entry에 before/after 링크를 두고 별도의 이중 연결 리스트를 관리한다.

 

5. isEqualTo는 왜 LinkedHashMap과 HashMap를 동일하다고 할까?

// LinkedHashMap
Map<String, Integer> listMap = new LinkedHashMap<>();

listMap.put("SECOND", 0);
listMap.put("FIRST", 0);

// HashMap
Map<String, Integer> hashMap = new HashMap<>();

hashMap.put("FIRST", 0);
hashMap.put("SECOND", 0);

assertThat(listMap).isEqualTo(hashMap); // true

hashMap 은 순서가 보장되지 않고
동일한 인터페이스여도 클래스가 달라서 오류가 반환될 줄 알았다.
하지만 그러지 않았다.

- isEqualTo() 알아보기
할당한 인자값과 기준값이 일치하는지 검증하는 assertJ 메서드다.

AssertJ.isEqual은 comparisonStrategy.areEqual 메서드로 값을 판단한다.

/**
 * Returns true if actual and other are equal according to the implemented comparison strategy.
 * 
 * @param actual the object to compare to other
 * @param other the object to compare to actual
 * @return true if actual and other are equal according to the underlying comparison strategy.
 */
boolean areEqual(Object actual, Object other);

구현된 비교 전략에 따라서 동등을 판단한다고 되어있다.

 Map의 비교 전략을 찾아봤다.

transient Set<Map.Entry<K,V>> entrySet;

entrySet은 추상화된 뷰로 Map 엔트리를 관리하고 있었다.

실제 키-값은 내부에서 Node로 관리된다.
entrySet은 외부서 엔트리 접근 목적으로 사용된다. 

entrySet의 타입 Set.equals를 찾아보면 의문을 해소할 수 있을 것이라고 추측했다. 

/**
 * ... Returns {@code true} if the specified object is also a set,
 * the two sets have the same size, and every member of the specified set is
 * contained in this set.
 * ...
 */
boolean equals(Object o);

 순서 관계없이 크기, 멤버가 동일하면 참인 것을 알 수 있었다.

 

- 참고
W3Schools. Java Collections.
W3Schools. Java Map.
W3Schools. Java HashMap.
W3Schools. Java TreeMap.
W3Schools. Java LinkedHashMap.