Map 알아보기

저번에 List에 대해서 정리를 했는데 정리를 하지 않을 것이 Map이랑 Set이 있다.

 

이번에는 Map에 대해 알아보고자 한다. 

1. Map이란?

java.util에 존재하는 map interface는 키와 값사이의 매핑을 나타낸다.

맵 인터페이스는 컬렉션 인퍼테이스의 하위 항목이 아니다.

그러므로 컬렉션 타입의 나머지와 약간 다르게 작동한다. 맵은 유일한 키를 가진다.

출처 : https://www.geeksforgeeks.org/map-interface-java-examples/

 

Map은 사전처럼 key-value 연관 매핑같은 사용에 완벽하다.

 

맵은 키로 색인을 하는데 혹은 키로 값을 가져오거나 수정할 때 사용한다. 

 

흔한 시나리오는다음과 같다. 

• 에러 코드와 그 설명에 대한 맵
• 우편번호와 도시의 맵
• 매니저와 피고용인의 맵. 각각의 매니저(key)는 그가 운영하는 피고용인의 리스트와 연관있다.
• 반과 학생들의 맵. 각 클래스(key)는 학생 리스트(value)를 가진다.

맵은 interface이기에, 객체는 type map을 만들 수 없다. 우리는 항상 객체를 만들려면 이 map을 상속하야 한다.

 

또한, java 1.5에서의 제네릭의 도입으로, 맵에 저장된 객체의 타입의 제한이 가능해졌다.

Map 인터페이스의 특징

1. 맵은 키를 복사할 수 없고 각각의 키는 하나의 값과 연결될 수 있다. 몇몇 구현체들은 null key 혹은 null value를 허용한다. (HashMap, LinkedHashMap은 허용, TreeMap은 안됌)
2. map의 순서는 특정 구현에 의존한다. 예를 들어, TreeMap과 LinkedHashMap은 예측 가능한 순서를 가졌는데, HashMap은 그렇지 않다. 
3. java에서 Map을 구현하는 두개의 인터페이스가 있다. Map과 SortedMap, 그리고 세개의 클래스가 있다.(HashMap, TreeMap, LinkedHashMap)

메소드 보기 클릭!

MethodAction Performed 

clear()	Map collection에서 정의된 모든 원소와 매핑을 제거한다.
containsKey(Object)	특정 키가 Map안에서 mapping되어 있는지, 아닌지는 확인한다.  파라미터로 key 원소를 넣고 만약 존재한다면 true를 반환한다.
containsValue(Object)	특정 값이 하나 혹은 하나 이상의 key와 mapping되어 있는지 확인한다.  파라미터로 value 를 넣고 만약 존재한다면 true를 반환한다.
entrySet()	This method is used to create a set out of the same elements contained in the map. It basically returns a set view of the map or we can create a new set and store the map elements into them.
equals(Object)	This method is used to check for equality between two maps. It verifies whether the elements of one map passed as a parameter is equal to the elements of this map or not.
get(Object)	This method is used to retrieve or fetch the value mapped by a particular key mentioned in the parameter. It returns NULL when the map contains no such mapping for the key.
hashCode()	This method is used to generate a hashCode for the given map containing keys and values.
isEmpty()	This method is used to check if a map is having any entry for key and value pairs. If no mapping exists, then this returns true.
keySet()	This method is used to return a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
put(Object, Object)	This method is used to associate the specified value with the specified key in this map.
putAll(Map)	This method is used to copy all of the mappings from the specified map to this map.
remove(Object)	This method is used to remove the mapping for a key from this map if it is present in the map.
size()	This method is used to return the number of key/value pairs available in the map.
values()	This method is used to create a collection out of the values of the map. It basically returns a Collection view of the values in the HashMap.
getOrDefault(Object key, V defaultValue)	Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.
merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)	If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value.
putIfAbsent(K key, V value)	If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the curassociaterent value.

 

Map인터페이스를 구현하는 클래스들이 다음과 같이 있다.

2. HashMap이란?

HashMap을 이해하기 전에 우선 Hash가 무엇인지 알고 넘어가야겠다.

 

이미 선배 개발자분께서 이에 대한 글을 잘 정리해놨다. (여기 참고)

 

그러면 HashMap이 무엇인지 좀 더 이해가 잘 될 것이다. 

 

해쉬 테이블에 기반을 둔 Map interface의 구현체. 이 구현체는 선택적인 맵 기능을 제공하고, null value와 null key를 허용한다. (HashMap class는 대략적으로 HashTable하고 동일하다. 동기화되지 않고, null을 허용한다는 점을 빼면 말이다.)이 클래스는 맵의 순서를 보증하지 않는다. 

출처 : https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

 

HaspMap에 데이터를 추가하게 되면, 특정 시점에 해시 테이블이 꽉차게 된다. 이 경우 새로운 해시테이블을 생성하고, 기존에 있던 데이터들을 옮기는 작업을 한다. 이 과정은 불필요한 데이터 복사를 발생시키므로 성능을 저하시킬 수 있다. 그러니 처음부터 큰 해시테이블을 생성한다면 이런 작업은 피할 수 있다.

 

참고 : https://hbase.tistory.com/134

 

이거는 사실 앞에서 본 Map기능을 거의 동일하게 가지고 있다.

3. LinkedHashMap이란?

LinkedHashMap은 HashMap을 상속한 클래스로 순서를 보장하는 Map이다. 

출처 : https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

 

또 찾아보니 LinkedHashMap과 HashMap에서 성능은 오히려 LinkedHashMap이 좋다는 글도 있다.

(HashMap 그럼 왜쓰는거야...?)

 

이에 대해 한글로 정리한 내용을 찾았다. (여기 참고)

 

또한, 검색 결과 두개를 비교한 표를 찾았다.

Comparison Table of LinkedHashMap and HashMap

Consider the below comparison table of HashMap and LinkedHashMap:

 

Property	HashMap	LinkedHashMap
Order of Iteration	No guarantee order	Insertion order
Implements (Interface)	Map	Map
Null key/values	Only one null key & multiple values	Only one null key & multiple values
Implementation	Buckets	Double-linked buckets
Synchronized	Non-synchronized	non-synchronized
Performance	Fast	Almost Similar to HashMap
Extends	AbstractMap class	HashMap class
Memory	Low Memory	More memory as compared to HashMap.
Thread-safety	Non-thread-safe	Non-thread-safe

 

여기서 HashMap은 Bucket을 사용한다는 표현이 있다.

 

여기서 bucket이란 양동이긴 한데... hashMap에서는 배열의 한 인덱스처럼 원소들을 저장하는 곳이다.

 

요약을 하자면,

 

HashMap은 일반적은 목적의 hashing 기반 collection에 유용하고, LinkedHashMap 은 원소의 무작위 순서에 유용하다

 

출처 : https://www.javatpoint.com/linkedhashmap-vs-hashmap-in-java

4. TreeMap이란?

사실 필자는 TreeMap을 한 번도 사용해 본 적이 없다.

 

물론 tree도 (다음에 공부 예정... ㅠㅠ) 말이다.

 

우선 Tree 구조가 뭔지 알아봤다.

What is Tree?

Array와 LinkedList같은 선형 데이터 구조와 달리, tree는 계층적 데이터 구조다.

작업이 선형 데이터 구조에서 실행될 때, 복잡도가 데이터 사이즈에 따라 증가한다. 

반면에, 트리 데이터 구조는 비선형인 데이터에 훨씬 더 빠른 접근을 제공한다. 

이 데이터 구조는 트리를 닮아서 트리라고 불린다.

뿌리 노드에서 시작해서 그것의 자손들로 가지를 뻗는다. 

출처 : https://www.naukri.com/learning/articles/tree-data-structures-types-properties-and-applications/

 

출처 : https://www.geeksforgeeks.org/introduction-to-tree-data-structure/

용어 정리

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

출처 : https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

 

Tree가 어느정도 이해가 된다면... TreeMap은 무엇인가?

 

NavigableMap구현체에 기반한 red-black tree다. 맵은 key의 natural ordering에 따라,  map creation time에 제공된  Comparator에 의해  정렬된다. 사용된 생성자에 따라서 말이다.

출처 : https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

 

여기서 Red-Black Tree는 다음과 같다.

출처 : https://coding-factory.tistory.com/557

TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있습니다. 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요합니다. 값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 냅니다.

이 문제를 보완하기 위해 레드 블랙 트리가 등장하였습니다. 레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줍니다.

레드-블랙 트리는 balanced binary search tree로 항상 넣을때와 뺄때, 그리고 순회에 대해서 모두 O(logN)을 만족합니다. 원리를 간단하게 말씀드리면 레드와 블랙으로 노드의 색깔을 칠하고 데이터를 넣을때(Insert)와 뺄때(Delete) Restructuring과 Recoloring라는 추가 프로세스로 진행하여 균형을 맞춥니다. 
"루트부터 리프노드까지의 블랙 노드의 개수는 같다."라는 것을 기조
로 합니다. 

레드-블랙 트리의 조건을 맞추면 루트로부터 리프까지의 최소길이와 최대길이의 차이가 2배 이하로 되게됩니다.

출처 
https://coding-factory.tistory.com/557
https://sabarada.tistory.com/139

 

생성자 / 메소드 보기 클릭!

Constructor and Description

TreeMap() Constructs a new, empty tree map, using the natural ordering of its keys.

TreeMap(Comparator<? super K> comparator) Constructs a new, empty tree map, ordered according to the given comparator.

TreeMap(Map<? extends K,? extends V> m) Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.

TreeMap(SortedMap<K,? extends V> m) Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.

Method Summary

Map.Entry<K,V>	ceilingEntry(K key) Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
K	ceilingKey(K key) Returns the least key greater than or equal to the given key, or null if there is no such key.
void	clear() Removes all of the mappings from this map.
Object	clone() Returns a shallow copy of this TreeMap instance.
Comparator<? super K>	comparator() Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
boolean	containsKey(Object key) Returns true if this map contains a mapping for the specified key.
boolean	containsValue(Object value) Returns true if this map maps one or more keys to the specified value.
NavigableSet<K>	descendingKeySet() Returns a reverse order NavigableSet view of the keys contained in this map.
NavigableMap<K,V>	descendingMap() Returns a reverse order view of the mappings contained in this map.
Set<Map.Entry<K,V>>	entrySet() Returns a Set view of the mappings contained in this map.
Map.Entry<K,V>	firstEntry() Returns a key-value mapping associated with the least key in this map, or null if the map is empty.
K	firstKey() Returns the first (lowest) key currently in this map.
Map.Entry<K,V>	floorEntry(K key) Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
K	floorKey(K key) Returns the greatest key less than or equal to the given key, or null if there is no such key.
V	get(Object key) Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
SortedMap<K,V>	headMap(K toKey) Returns a view of the portion of this map whose keys are strictly less than toKey.
NavigableMap<K,V>	headMap(K toKey, boolean inclusive) Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.
Map.Entry<K,V>	higherEntry(K key) Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.
K	higherKey(K key) Returns the least key strictly greater than the given key, or null if there is no such key.
Set<K>	keySet() Returns a Set view of the keys contained in this map.
Map.Entry<K,V>	lastEntry() Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
K	lastKey() Returns the last (highest) key currently in this map.
Map.Entry<K,V>	lowerEntry(K key) Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
K	lowerKey(K key) Returns the greatest key strictly less than the given key, or null if there is no such key.
NavigableSet<K>	navigableKeySet() Returns a NavigableSet view of the keys contained in this map.
Map.Entry<K,V>	pollFirstEntry() Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
Map.Entry<K,V>	pollLastEntry() Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
V	put(K key, V value) Associates the specified value with the specified key in this map.
void	putAll(Map<? extends K,? extends V> map) Copies all of the mappings from the specified map to this map.
V	remove(Object key) Removes the mapping for this key from this TreeMap if present.
int	size() Returns the number of key-value mappings in this map.
NavigableMap<K,V>	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) Returns a view of the portion of this map whose keys range from fromKey to toKey.
SortedMap<K,V>	subMap(K fromKey, K toKey) Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
SortedMap<K,V>	tailMap(K fromKey) Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
NavigableMap<K,V>	tailMap(K fromKey, boolean inclusive) Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.
Collection<V>	values() Returns a Collection view of the values contained in this map.

 

지원하는 method를 보면 많이 낯설다.

 

그래도 뭐 이름을 보면 무슨 기능인지는 알 것 같다.

 

근데 TreeMap은 그래서 언제 써야하는거지? 

 

이에 대한 답변을 원하는 stack overflow 친구들의 글을 가져왔다.

 

 

심지어 10년 전에 다른 나라의 개발자가 이에 대해 고민하고 있었다니... 이분은 어떻게 됐을까 궁금도 하다.

 

하여간 그게 중요한 게 아니다.

 

답변으로는 다음과 같다. 

It is efficient way of having objects sorted by some key. If also random access is important for you then TreeMap is the answer. With this data structure you can iterate in order.

If random access is not needed then rather use sorted set/bag or list.

 

사용하는 이유는 간단하다. 랜덤하게 저장된 특정 값을 찾기 위해 좋은 구조라고 한다. 

 

물론 random하게 접근하지 않는 경우에는 필요가 없지만 말이다. 

 

이것은 Tree에 대해 처음 알아봤을 때 어느정도 유추할 수 있는 이유이기도 하다. 

 

모두 순회해야하는 선형 데이터 구조와는 달리, 비선형인 데이터에 훨씬 더 빠른 접근을 제공하는 Tree를 좀 더 나은 방법으로 구현한 것이 TreeMap이니... 

 

속도가 더 증가할 것이다. 

---

이번 시간에 Map에 대해 좀 더 자세히 알아봤다.

 

코드 구현을 하지 않은 이유는 귀찮기(가장 큰 이유) 도 한데...

 

내가 굳이 정리를 하지 않다고 사용법같은 경우에는 너무 찾기가 쉬웠다.

 

그러므로 필자는 좀 더 개념을 더 알고 싶었기에 이렇게 정리했다.