[Java] Collection Framework - Map의 구현체(기본)

아래 질문에 대한 답은 해당 글 하단에서 확인해 볼 수 있다.

1. 왜 Map 인터페이스는 Collection 인터페이스를 상속받지 않는가?
2. HashMap은 어떻게 동작하는가?
3. 어떠한 클래스도 Map의 Key로 사용될 수 있는가?
4. Map 인터페이스가 제공하는 다른 Collection 뷰는 무엇인가?
6. HashMap과 TreeMap은 각각 어떤 상황에서 사용하기에 적합한가?

---

0. Map 인터페이스 특징

• List, Set, Queue 와 같은 인터페이스와 달리 Collection 인터페이스를 상속받지 않음
• key-value 쌍(Entry) 으로 데이터 저장
• 순서 없음
• key 중복 불가/value는 중복될 수 있음

사용시 주의해야할 점

Map 인터페이스 주석 참고

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a map.

Map의 키로 mutable한 객체를 사용하는 것은 안좋다! Map은 key에서 해시함수를 통해 해시값(hash code)을 얻고 그에 해당하는 요소에 value를 저장하는데, key값이 변경되면 해시값도 달라지게 된다. 그럼, 원래 key의 해시값에 매핑되어 있던 value가 아닌 다른 값이 매핑되거나 메모리 누수가 생길 수 있다. 

1. Map 인터페이스의 구현

• HashMap
• LinkedHashMap
• TreeMap(SortedMap인터페이스)

이외에도 HashTable이 있지만 이는 과거에 사용했던 클래스로 더이상 지원하지 않으니 사용을 지양하는 것이 좋다. 

2. Map의 기본 메소드

return value	method	description
int	size()	key-value 쌍의 수, entry의 수가 Integer.MAX_VALUE 이상이면 Integer.MAX_VALUE 반환한다.
boolean	isEmpty()	key-value 쌍이 없는 경우 true 반환한다.
boolean	containsKey(Object key)	Map에 지정한 키가 포함된 경우 true 반환한다.
boolean	containsValue(Object value)	Map에 지정한 값이 포함된 경우 true 반환 이 연산은 Map 크기에 해당하는 선형시간이 필요하다.
V	get(Object key)	key에 해당하는 값을 반환하거나 매핑되는 값이 없으면 null 반환한다.  Map에 null값을 명시적으로 허용할 수 있으므로 null이 반환되더라도 해당 키에 매핑되는 값이 없다는 것을 의미하는 것은 아니다.
V	put(K key, V value)	key에 value가 매핑된다. 이전에 key에 대한 매핑이 있는 경우 이전 값을 update한-다.
V	remove(Object key)	지정한 key에 대한 매핑이 존재하는 경우 해당 매핑을 제거한다.
void	putAll(Map<? extends K, ? extends V> m)	지정한 Map에 모든 매핑을 복사한다.
void	clear	Map 내의 모든 매핑을 제거한다.
Set<K>	keySet()	Map의 포함된 key들의 Set 뷰를 제공한다.  Map의 변경 내용이 Set에도 반영되고 그 반대도 마찬가지이다. 해당 Set 뷰에서 요소를 삭제하는 연산(remove, removeAll, retainAll, clear)은 허용되며 이 연산이 Map에도 반영되지만 추가하는 연산(add, addAll)은 지원되지 않는다.
Collection<V>	values()	Map에 포함된 value들의 Collection 뷰를 제공한다.  Map의 변경 내용이 Collection 뷰에도 반영되고 그 반대도 마찬가지이다.  해당 Collection 뷰에서 요소를 삭제하는 연산은 허용되며 이 연산이 Map에도 반영되지만 추가하는 연산은 지원되지 않는다.
Set<Map,.Entry<K, V>>	entrySet()	Map에 포함된 매핑의 Set 뷰를 반환한다.  Map의 변경 내용이 Set 뷰에도 반영되고 그 반대도 마찬가지이다.  해당 Set 뷰에서 요소를 삭제하는 연산(remove, removeAll, retainAll, clear)은 허용되며 이 연산이 Map에도 반영되지만 추가하는 연산(add, addAll)은 지원되지 않는다.

이외에도 Entry(key-value 쌍) 인터페이스에 정의된 유용하게 쓰일만한 메소드는 아래와 같다. 

return value	method	description
V	getOrDefault(Object key, V defaultValue)	지정한 key에 매핑된 value를 반환하거나, 매핑이 없는 경우 지정한 defaultValue를 반환한다.

각 구현체에 대한 설명에 앞서, 아래에서 사용될 용어 중 "버킷"에 대해서 정리하고 가자.

버킷(bucket)? 해시 함수를 통해 계산된 키의 해시값에 따라 매핑된 값들이 저장되는 위치
일반적으로, 해시 테이블이 배열로 구현되며 각 배열의 요소를 버킷이라고 한다. 

3. HashMap

• 해시함수를 이용한  Map - key의 해시값(hash code)을 사용하여 value를 저장, 각 해시값(hash code)은 해시 테이블(배열로 구현됨)의 인덱스로 사용되며 해당 인덱스의 요소에 value가 저장된다. 
• 삽입/검색/삭제 연산의 시간복잡도: O(1)
• 삽입한 데이터의 순서를 보장하지 않음(순서를 보장하려면 LinkedHashMap을 사용해야함)
• 정렬이 불가(정렬을 위해서는 TreeMap을 사용해야함)

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

static final float DEFAULT_LOAD_FACTOR = 0.75f;​

기본 생성자에 의해 HashMap객체를 생성하는 경우 HashMap의 초기 용량은 16이며 초기 적재율을 0.75으로 정의되어 있다. 

여기서, 적재율(load factor)은 해시 테이블 크기 대비 키의 개수 비율을 의미한다. 만약 용량이 4인데 3개의 키가 쌓인 경우 적재율이 75%(3/4)라고 볼 수 있다. 

Map에 요소가 추가되면서 기본으로 설정되어 있는 용량을 벗어나게 되는 경우 resize를 수행하는데 resize를 수행할 때마다 용량은 2배 늘어나게 된다. ( 아래 코드에서 newThr = oldThr << 1; 부분 참고) 

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;

4. LinkedHashMap

• 해시테이블과 연결리스트를 결합하여 key-value 쌍을 저장 - 해시 테이블의 각 버킷에 연결리스트가 저장, (1) key를 해시함수를 이용하여 hash code로 변환, (2) 해당 해시값에 대응하는 버킷에 key-value 쌍을 저장, (3) 동일 해시값에 대응 하는 버킷에 이미 다른 key-value 쌍이 저장된 경우 연결 리스트의 마지막에 새로운 엔트리 추가
• 입력 순서 혹은 접근 순서가 유지
• 삽입/삭제가 일반 Map보다 느림
• LRU(Latest Recently Used) 캐시와 같은 캐시 구현체로 사용될 수 있다.

    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);
        }
    }
    
    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

LinkedHashMap에서 정의된 Entry 클래스이다. 각 Entry는 이전(before)과 이후(after)에 대한 포인터를 가지며 LinkedHashMap에서 head, tail 엔트리를 가진 것으로 보아 내부적으로 해시테이블이 이중연결리스트로 구현되어 있음을 알 수 있다. 

Entry 클래스에서 각각의 변수가 의미하는 것은 다음과 같다.

• before: 해당 노드 앞에 삽입된 노드
• after: 해당 노드 뒤에 삽입된 노드
• key: 키
• value: 값
• next: 동일한 버킷에 있는 다음 노드

LinkedHashMap에서 동일 버킷에 대해 다른 Entry를 가질수 있으면서 순서를 어떻게 저장하는지 궁금했는데 Entry 클래스의 정의 내용을 보면 답을 얻을 수 있었다. 

before, after 엔트리는 순서 보장을 위한 포인터이고 next는 동일 버킷에 대한 연결된 Entry에 대한 포인터라고 이해하면 된다. 

5. TreeMap

• 이진검색트리(binary search tree)를 기반으로 한 Map - 각 노드의 key를 이용하여 key-value 쌍을 저장하고 검색
• 키가 항상 정렬된 순서로 유지
• 키와 값이 저장된 Map Entry를 저장
• 추가나 삭제시 정렬 수행(레드-블랙 트리를 유지하기 위해서) → HashMap보다 Map 성능이 떨어짐, O(logN) 의 시간복잡도
• 정렬 순서: 부모노드의 키값보다 작은 키값은 왼쪽 자식 서브트리로/부모노드의 키값보다 큰 키값은 오른쪽 자식 서브트리로
• key 비교를 위해 Comparable 인터페이스 혹은 Comparator 인터페이스 구현이 필요, natural ordering이 기본
• key의 순서가 중요하고 검색 속도가 중요한 경우에 유용하다. 

이진트리의 문제점

• TreeMap에서는 이진트리에서 발생할 수 있는 편향 문제를 레드-블랙 트리를 사용하여 해결했다.
• 레드-블랙 트리는 트리가 편향되지 않도록 Recoloring, Restructuring을 통해서 균형된 이진 트리를 유지한다. 

---

1. 왜 Map 인터페이스는 Collection 인터페이스를 상속받지 않는가?
   • Map과 Collection은 요소를 다루는 방식이 다르다. Collectin은 객체의 모음을 다루는 인터페이스로서 일반적으로 요소를 반복하며 처리하는 방식으로 구현되어 있다. 반면, Map은 key-value 쌍을 다루는 인터페이스로서 각 key에 대응하는 value를 저장하고 검색하는 기능을 제공한다. 또한, Map은 요소를 반복하는 것보다 key를 이용한 검색을 하는 방식으로 구현되어 있다. 추가적으로, Java 8 부터는 Map 인터페이스에 forEach() 메소드를 추가하여 Collection 인터페이스의 일부 기능을 사용할 수 있도록 개선되었다.
2. HashMap은 어떻게 동작하는가?
   • HashMap은 Map 인터페이스를 구현한 클래스 중 하나로서 key-value 쌍을 저장하는 해시테이블을 사용하여 데이터를 관리한다. HashMap에서 각 엔트리는 key와 value의 쌍으로 구성되며 key의 해시값을 통해 버킷에 저장된다. 해시값은 hashCode() 메소드를 호출하여 계산되며, 동일한 key 객체에 대해서는 항상 동일한 해시값이 반환된다. 
   • get() 메서드 호출시 hashCode() 메소드를 호출해 해시값을 찾고 equals() 메소드를 통해 찾으려고 하는 key와 동일한지 확인한다. 
   • put() 메서드 호출시 hashCode() 메소드를 호출하여 Map에 동일한 key가 있는지 찾는다. 만약, 존재하는 Entry인 경우 equals() 메소드를 통해 key가 이미 존해자는지 확인하고 존재한다면 덮어쓴다. 
   • 해시값이 충돌하는 경우, 이를 해결하기 위해 각 버킷에 연결 리스트를 이용하여 key-value 쌍을 저장한다. 최대한 충돌이 발생하지 않도록 적절한 초기 용량과 로드 팩터를 설정하는 것이 중요하다. 
   • HashMap은 삽입, 검색, 삭제 연산에 대해 O(1)의 시간 복잡도를 가지며, 해시충돌이 발생하는 경우 최대 O(N)의 시간 복잡도를 가질 수 있다. 
3. 어떠한 클래스도 Map의 Key로 사용될 수 있는가?
   
   • 어떤 클래스도 Map의 key로 사용될 수 있지만, 해당 클래스는 반드시 hashCode()와 equals() 메소드를 구현해야 하며 불변클래스로 구현하는 것이 좋다. 
   • Mutabl 객체를 Key로 사용하는 경우 예측하지 못한 결과가 발생할 수 있다. Map의 key로 사용된 객체 상태가 변경되면 hashCode() 메서드 반환값도 변경된다. 해당 key를 검색하기 위해 사용하는 해시 테이블에서 key의 위치가 변경되어 검색이 실패하거나 다른 key를 찾게 될 수 있다. 
   • 또한, 정렬기준으로 사용되는 Comparable 또는 Comparator 인터페이스의 compareTo() 메서드나 compre() 메서드의 반환값도 변경될 수 있다.
4. Map 인터페이스가 제공하는 다른 Collection 뷰는 무엇인가?
   
   • keySet() 메서드: Map에 저장된 key들의 Set 뷰 반환
   • values() 메서드: Map에 저장된 Collection 뷰 반환
   • entrySet() 메서드: Map에 저장된 key-value 쌍들의 Set 뷰 반환
   • 위 Collection 뷰들을 통해 Map에 저장된 key, value, key-value 쌍들을 다룰 수 있다.
5. HashMap과 TreeMap은 각각 어떤 상황에서 사용하기에 적합한가?
   • HashMap과 TreeMap은 크게 데이터 정렬 방식, 속도에서 차이를 가진다. 
   • 데이터 정렬 방식: HashMap은 데이터 순서를 보장하지 않은데 반해 TreeMap은 key를 기준으로 정렬된 순서로 데이터를 저장한다.
   • 속도: HashMap은 해시테이블을 사용하여 데이터를 저장하므로 삽입, 검색, 삭제 연산에 O(1)의 시간복잡도를 보장한다. 반면, TreeMap은 이진검색트리를 사용하여 데이터를 저장하므로 삽입, 검색, 삭제 연산에 O(logN)의 시간복잡도를 가진다. 
   • 따라서, 데이터의 순서가 중요하지 않은 경우 혹은 대용량 데이터를 빠르게 처리할 때는 HashMap을
   • 데이터를 정렬된 상태로 유지해야 하거나 특정 키값에 대한 검색 연산이 많은 경우, key의 자연적인 순서나 Comparable 인터페이스를 구현한 사용자 정의 클래스를 key로 사용할 때는 TreeMap을 사용하는 것이 좋다.