[Java] Map과 HashMap, Multimap, TreeMap 은?

Map

• 키(Key) 와 값(Value)을 가진 Map.Entry 로 구성.
• 키(Key)는 해당 Map에서 고유(Unique)해야 한다.
• 값(Value)은 중복이 가능하다.

 

Map 의 형태

 

선언되어 있는 메서드

메서드 시그니처	설명
V put(K key, V value)	Map 내에 key로 구분한 value를 저장
void putAll(Map<? extends K, ? extends V> m	매개변수 Map의 모든 데이터 저장
V get(Object key)	key에 맞는 value 반환
V remove(Object key)	key에 맞는 Map 삭제
Set<K> keySet()	모든 key을 Set의 형태로 반환
Collection<V> values()	모든 value 를 Collection 형태로 반환
Set<Map.Entry(K, V)> entrySet()	Map.Entry 타입을 Set으로 반환
int size()	Map의 크기 반환
void clear()	Map의 모든 내용을 지운다.

 

 

HashMap

• Map 의 구현체.
• Serializable , Cloneable 을 구현하여, 클론 혹은 직렬화 역질렬화를 할 수 있다.
• 해시 함수와, 해시 테이블 원칙에 따라 작동한여. 탐색 과정에서 O(1) 시간이 소요 된다.
  • 해시 테이블과 해시 함수
• 키가 오브젝트 일때는 hashCode() 와 equals() 를 구현해두어야 한다.

HashMap 내부

• 해시 맵에 값을 넣을 때 키의 hashCode() 값이 저장될 위치(버킷)를 결정한다.
• 해시 맵의 검색을 할 때에는 hashCode() 로 버킷의 위치를 탐색하고, 키의 equals() 메서드를 통해 정확히 일치하는 항목을 찾는다. hashCode() 값이 같다면 같은 버킷을 사용하기 때문에, equals() 메서드를 통해 구분될 수 있어야 한다.
  • 검색에 있어 O(1) 의 시간 복잡도를 갖는다.
  • 다른 키가 같은 해시 값을 가지면 두 값은 동일한 버킷에 저장되며 내부에서 특정 값을 찾는것은 O(n) 비용이 든다. 또한 이와 같은 상황을 충돌이라고 한다.
• 하나의 버킷의 값의 개수가 늘어나면 균형 트리 형태로 변경하여 이진 탐색을 진행하여 O(lonN) 의 시간 복잡도를 가지게 된다. 다만 값을 추가하거나 관리하는데 오버헤드가 발생할 수 있다.

 

TreeMap

• Map에서 Key가 정렬된 상태로 필요해야 할 때 사용한다.
  • 정수의 경우 오름차순, 문자열의 경우 알파벳 순서를 의미합니다.
• 너무 많은 데이터를 처리할 때는 키가 정렬된 상태로 존재해야하기 때문에 속도가 느리다.
• 정렬되어 가능한 메서드를 제공한다.
  • firstKey() , lastKey() , higherKey() , lowerKey()

 

TreeMap의 내부

• 레드-블랙 트리 노드로 구성된 데이터 구조를 사용하고 있다.
• 레드-블랙 트리로 기본적으로 균형 이진 탐색 트리이다. 따라서 추가, 삭제, 검색등의 기본작업에 O(logN)이 보장된다.

 

 

MultiMap

• 하나의 키가 여러 값과 연관될 수 있다.
• 하나의 Key에 Value가 Collection 형태로 제공된다.

 

위 내용을 편하게 하기 위해 Google Guava 라이브러리 구현중에 Multimap이 존재한다.