Map

11 Sep 2023 - 2 minute read

🔗 Map     🔗 LinkedHashMap     🔗 Doubly linked list     🔗 TreeMap     🔗 HashMap

Map

---

• 대응 관계를 쉽게 표현할 수 있게 해주는 자료형

• 키(key)-값(value)을 한 쌍으로 갖는 자료형

• value의 중복은 허용되나, key의 중복은 허용되지 않음

• 순서가 중요하지 않음

  • LinkedHashMap : 입력된 순서대로 데이터 저장

  • TreeHashMap : 입력된 key의 오름차순으로 데이터 저장

HashMap

---

• HashMap의 제네릭스는 key, value 모두 String 자료형

• put(K key, V value) : 항목 추가

• putAll(Map<? Extends K, ? Extends V> m) : 어떤 map의 모든 항목을 해당 map으로 복사

• putIfAbsent(K key, V value) : 해당 key에 값이 없거나 null이면주어진 value를 저장하고 null 반환, 값이 있는 경우에는 저장되어 있는 value값을 반환

• get(Object key) : key에 해당되는 value 얻기

• getOrDefault(Object key, V defaultValue) : key에 해당하는 value가 없을 때 null이 리턴되는데, 이 때 getOrDefault()를 사용하면 null 대신 default 값을 얻을 수 있음

• containsKey(Object key) : 해당 key의 존재 여부 true/false로 리턴

• containsValue(Object value) : 해당 value의 존재 여부 true/false로 리턴

• isEmpty() : 맵이 비어있는지 확인, 어떠한 key-value 값도 가지고 있지 않으면 true 리턴

• remove(Object key) : 맵의 항목 삭제, value값 리턴

• size() : 요소의 개수 리턴

• keySet() : 맵의 모든 key를 리턴

• clear() : 맵의 모든 항목 삭제

• replace(K key, V value) : 해당 key에 대한 값 변경

• replace(K key, V oldValue, V newValue) : key가 특정 value일 때만 value 값 변경

LinkedHashMap

---

• public class LinkedHashmap<K, V> extends HashMap<K, V> implements Map<K, V>

• HashMap과 동일하게 키-값 쌍을 요소로 가지며, key의 중복은 허용하지 않음

• non-synchronized

• HashMap과는 다르게 LinkedHashMap은 입력된 순서대로 데이터를 저장

• LinkedHashMap의 implementation은 이중연결리스트(doubly-linked list)와 매우 비슷함 [before] - [key] - [value] - [after]

  • 이중연결리스트란?

    • 단순연결리스트(linked list)와는 다르게 이전 노드(previous)와 다음 노드(next)로 구성

    • 노드와 노드가 서로 연결되어 있음

    • 다음 노드의 탐색만 가능한 단방향 연결 리스트와 다르게 양방향으로 연결되어 있기 때문에 노드 탐색방향이 양쪽(앞뒤)로 가능함

    • 이전 노드를 지정하기 위한 변수를 추가로 사용하기 때문에 메모리를 더 사용하고, 구현이 복잡해진다는 단점이 있음

• containsValue(Object value) / entrySet() / keySet() / get(Object key) / removeEldestEntry(Map.Entry<K, V> eldest) / values()

• LRU Cache 구현 가능

TreeMap

---

• 이진트리를 기반으로 한 Map 컬렉션

• 저장과 동시에 key의 오름차순으로 정렬 (부모 키값과 비교해 키 값이 낮은 것은 왼쪽 자식 노드에, 높은 것은 오른쪽 자식 노드에 저장)

• 데이터 저장 시 정렬되기 때문에 HashMap보다 성능이 떨어지지만, 정렬된 상태로 Map을 유지하거나 정렬된데이터를 조회해야 하는 범위 검색이 필요한 경우 효율적

• TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어짐

  • 레드-블랙 트리란?

    • 자가 균형 이진 탐색 트리

    • 각 노드들은 red 혹은 black의 색상을 가짐

    • 일반적인 이진 탐색 트리는 현재 노드보다 값이 작은 것은 자신의 왼쪽 서브 트리에, 값이 큰 것은 오른쪽 서브 트리에 가짐 > 트리의 높이만큼 시간 필요 (O(log N)), 균형이 무너질 경우 시간 복잡도가 O(N) 까지 증가할 수있음

    • 레드-블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치 > 데이터 추가/삭제 시 균형을 맞춤, 검색/삽입/삭제 시 O(log N)이 보장됨