📖 Map 컬렉션 클래스

---

• Map 인터페이스는 Collection 인터페이스와는 다른 저장 방식
• 키와 값을 하나의 쌍으로 저장하는 방식(key-value 방식)을 사용
  - 키(key)란 실질적인 값(value)을 찾기 위한 이름의 역할

특징

1. 요소의 저장 순서를 유지하지 않음
2. 키는 중복을 허용하지 않지만, 값의 중복은 허용

대표적인 Map 컬렉션 클래스

1. HashMap<K, V>
2. Hashtable<K, V>
3. TreeMap<K, V>

💬 HashMap<K, V> 클래스

---

• 가장 많이 사용되는 클래스 중 하나
• JDK 1.2부터 제공된 HashMap 클래스는 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠름
• Map 인터페이스를 구현하므로, 중복된 키(key)로는 값을 저장할 수 없음
• 하지만 같은 값(value)을 다른 키로 저장하는 것은 가능
• null 허용함
• 시간복잡도
  • get : O(1)
  • containsKey : O(1)
  • next : O(h/n) h는 테이블 용량

◾ HashMap<K, V>의 주요 메소드

메소드	설명
void clear()	모든 맵 제거
boolean containsKey(Object key)	전달된 객체(key) 포함하는지 확인
boolean containsValue(Object value)	전달된 객체(value) 포함하는지 확인
Set<Map.Entry<K,V>> entrySet()	해당 맵에 포함된 매핑의 집합 반환
V get(Object key)	전달된 객체(key)의 값(value) 반환
boolean isEmpty()	해당 맵이 비었는지 확인
Set< K > keySet()	해당 맵에 포함된 key 집합 반환
V put(K key, V value)	해당 맵에 전달된 key와 value을 연결
V remove(Object key)	전달된 객체(key)와 동일한 값 제거
int size()	해당 맵의 key-value 맵핑 개수 반환
Collection< V > values()	해당 맵에 포한된 value 집합 반환

💬 Hashtable<K, V> 클래스

---

• JDK 1.0부터 사용해 온 HashMap 클래스와 같은 동작을 하는 클래스
• 현재의 Hashtable 클래스는 HashMap 클래스와 마찬가지로 Map 인터페이스 상속
• 메소드는 HashMap 클래스에서 사용할 수 있는 메소드와 거의 같음
• 하지만 현재에는 기존 코드와의 호환성을 위해서만 남아있으므로, Hashtable 클래스보다는 HashMap 클래스를 사용하는 것이 좋음

💬 TreeMap<K, V> 클래스

---

• 키와 값을 한 쌍으로 하는 데이터를 이진 검색 트리(binary search tree)의 형태로 저장
• 이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠름
• JDK 1.2부터 제공된 TreeMap 클래스는 NavigableMap 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현

  • 레드 블랙 트리
    • 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 걸림
    • 데이터의 값이 트리에 잘 분산되어 있다면 효율성에 큰 문제가 없으나 데이터가 들어올 때 값이 편향되게 들어올 경우 한쪽으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스 나옴
    • 이 문제를 보완하기 위해 레드 블랙 트리가 등장
    • 레드 블랙 트리는 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줌

• Map 인터페이스를 구현하므로, 중복된 키로는 값을 저장할 수 없음
• 하지만 같은 값을 다른 키로 저장 가능
• 정렬이 되면서 추가 됨
• null은 허용하지 않음
• 시간복잡도
  • get : O(log n)
  • containsKey : O(log n)
  • next : O(log n)

◾ TreeMap<K, V>의 주요 메소드

메소드	설명
V put(K key, V value)	해당 맵에 전달된 키에 대응하는 값으로 특정 값을 매핑
V remove(Object key)	해당 맵에서 전달된 키에 대응하는 매핑을 제거
int size()	해당 맵의 매핑의 총 개수를 반환
boolean containsKey(Object key)	해당 맵이 전달된 키를 포함하고 있는지를 확인
boolean containsValue(Object value)	해당 맵이 전달된 값에 해당하는 하나 이상의 키를 포함하고 있는지를 확인
NavigableMap<K, V> descendingMap()	해당 맵에 포함된 모든 매핑을 역순으로 반환
Set<Map.Entry<K, V>> entrySet()	해당 맵에 포함된 모든 매핑을 Set 객체로 반환
Map.Entry<K, V> firstEntry()	해당 맵에서 현재 가장 작은(첫 번째) 키와 그에 대응하는 값의 엔트리를 반환
K firstKey()	해당 맵에서 현재 가장 작은(첫 번째) 키를 반환
Map.Entry<K, V> lastEntry()	해당 맵에서 현재 가장 큰(마지막) 키와 그에 대응하는 값의 엔트리를 반환
K lastKey()	해당 맵에서 현재 가장 큰(마지막) 키를 반환
Map.Entry<K, V> ceilingEntry(K key)	해당 맵에서 전달된 키와 같거나, 큰 키 중에서 가장 작은 키와 값의 엔트리 반환 (만약 해당하는 키가 없으면 null 반환)
K ceilingKey(K key)	해당 맵에서 전달된 키와 같거나, 큰 키 중에서 가장 작은 키 반환 (만약 해당하는 키가 없으면 null 반환)
Map.Entry<K, V> floorEntry(K key)	해당 맵에서 전달된 키와 같거나, 작은 키 중에서 가장 큰 키 값의 엔트리 반환 (만약 해당하는 엔트리가 없으면 null 반환)
K floorKey(K key)	해당 맵에서 전달된 키와 같거나, 작은 키 중에서 가장 큰 키 반환 (만약 해당하는 키가 없으면 null 반환)
Map.Entry<K, V> higherEntry(K key)	해당 맵에서 전달된 키보다 작은 키 중에서 가장 큰 키 값의 엔트리 반환 (만약 해당하는 엔트리가 없으면 null 반환)
K higherKey(K key)	해당 맵에서 전달된 키보다 작은 키 중에서 가장 큰 키 반환 (만약 해당하는 키가 없으면 null 반환)
Map.Entry<K, V> lowerEntry(K key)	해당 맵에서 전달된 키보다 큰 키 중에서 가장 작은 키와 값의 엔트리 반환 (만약 해당하는 키가 없으면 null 반환)
K lowerKey(K key)	해당 맵에서 전달된 키보다 큰 키 중에서 가장 작은 키 반환 (만약 해당하는 키가 없으면 null 반환)
Map.Entry<K, V> pollFirstEntry()	해당 맵에서 현재 가장 작은(첫 번째) 키와 그에 대응하는 값의 엔트리를 반환하고, 해당 엔트리를 맵에서 제거
Map.Entry<K, V> pollLastEntry()	해당 맵에서 현재 가장 큰(마지막) 키와 그에 대응하는 값의 엔트리를 반환하고, 해당 엔트리를 맵에서 제거
SortedMap<K, V> subMap(K fromKey, K toKey)	해당 맵에서 fromKey부터 toKey까지로 구성된 부분만 반환 (이때 fromKey는 포함되나, toKey는 포함되지 않음)
SortedMap<K, V> tailMap(K fromKey)	해당 맵에서 fromKey와 같거나, fromKey보다 큰 키로 구성된 부분만을 반환