컬렉션 - Map

Map의 클래스 - Multimap(구글의 guava 자료구조), TreeMap, HashMap, LinkedHashMap

📌Map

키와 값으로 구성된 객체. 중복되는 키 값을 가질 수 없다. 많은 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있는 자료 구조

• 사용해야 하는 경우
  1) 정렬해야 한다.
  2) 많은 자료를 저장하고, 검색이 빨라야 한다.
  3) 빈번하게 삽입, 삭제하지 않는다.

데이터 읽기 성능 : HashMap > LinkedHashMap > HashTable > TreeMap

💡 정리

• 키 중복의 경우, 같은 키의 여러 value의 경우 Multimap 사용
• 정렬이 필요한 경우 TreeMap 사용 (검색에 있어서 가장 느리다.)
• 메모리 보다 성능이 우선일 경우 HashMap 사용 (검색에 관해 대부분 O(1) 성능인 HashMap 사용)
• 일정한 수행시간과 삽입 순서를 유지하는 경우 LinkedHashMap 사용 (입력순서가 중요할 때)

📖1. Multimap

google 에서 제공하는 다양한 자료구조와 유틸리티들을 모아둔 라이브러리인 guava에 Mulimap가 존재한다.map과 거의 비슷하나, 각 키값에대해서 복합적인 값을 가질 수 있다는 것이 다르다.(key값이 중복 가능)

Value형에 배열이나 List 등과 같은 Collection을 사용한다. 같은 key가 들어오면 value가 over write하지 않고, list에 추가된다.
예시 ) Multimap<String, String> mulimapCart = ArrayListMultimap.create();

• 사용해야하는 경우
  1) 저장된 데이터들을 정렬해야할 경우
  2) 많은 자료들을 저장하고, 특정자료에 대해 검색을 빠르게 해야 할 경우
  3) map과 동일하나, key값이 중복된 원소를 가질 수 있는 경우

📖2.TreeMap

TreeMap은 레드-블랙 트리(Red-Black Tree)의 이진탐색트리를 보완한 자료구조를 이용하여, key값을 기준으로 정렬 유지한 상태로 키와 값의 쌍으로 이루어진 데이터를 저장한다(HashMap과의 차이점). 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 오름차순 정렬한다.

하지만, 이진검색트리처럼, 데이터를 저장할 때 정렬하기 때문에 저장시간이 길다는 단점이 있습니다. 또한, 트리 구조의 특성상 특정 엔트리에 접근하기 위해서는 O(logn)이 걸린다.

TreeMap 은 일반적으로 Map으로써의 성능이 HashMap 보다 떨어진다.
TreeMap은 데이터를 저장할때 즉시 정렬하기에 추가나 삭제가 HashMap 보다 오래 걸린다. 따라서, 주로 HashMap를 사용한다.

• 사용해야 하는 경우
  1) 정렬된 상태로 데이터를 조회하는 경우
  데이터를 조회할 때 정렬해야 하는 hashMap보다는 이미 정렬된 상태로 저장되어 있는 TreeMap이 빠른 조회결과를 얻을 수 있다.
  2) 정렬된 상태로 Map 을 유지해야 하는 경우
  3) 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우
  4) 키 값을 기준으로 정렬을 해서 사용할 경우

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

---

1) 이진 탐색 트리가 편향 트리가 될 경우를 방지하는 조건을 추가함.
레드블랙트리의 높이는 logn에 바운드 됩니다 -> 레드블랙트리에서 삽입, 삭제, 검색 연산은 O(logn)의 시간복잡도를 가진다.
2) 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다. (worst-case guarantees).
이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.

📖3. HashMap

Map의 특징인 키(Key)와 값(Value) 를 이용하여 하나의 데이터(entry) 로 저장한다. 단, hashCode를 사용하기 때문에 예측할 수 없는 순서로 저장한다.(TreeMap과의 차이점)

키는 중복이 되지 않지만 값은 중복이 될 수 있습니다. 기존에 저장된 키로 값을 저장하면 기존 값은 없어지고 새로운 값이 저장된다.해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색할 때 성능이 좋다.
→ Key의 해시 계산값을 이용해 나온 값으로 인덱스를 지정한 배열을 활용해 Value에 접근할 수 있어 O(1)의 시간 복잡도를 가진다. (= 빠르다는 이야기)

해시 함수(hash function)란 데이터의 효율적인 관리를 목적으로 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시(hash) 또는 해시 코드(hash code)라고 한다. 이 데이터 값들은 해시테이블에 저장된다.
이렇게 해시함수를 이용하여 데이터를 매핑하여 저장하고 검색하는 기법을 해싱(hasing)이라고 한다. 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다.

해시 함수를 통해 매핑된 해시를 Index로 활용하기 때문에 데이터에 대한 검색, 삽입, 제거 연산의 시간 복잡도가 O(1)이라는 확실한 장점이 있다.

💡 저장/조회 할 배열 인덱스 계산하는 식
int index = Key.hashCode() % (배열의 크기);

📖4. LinkedHashMap

“입력된 key의 순서가 보장된다.”는 것이 가장 큰 특징이다.

LinkedHashMap은 HashMap을 확장한다. HashMap의 모든 기능을 사용하되, Doubly-Linked List(이중 연결 리스트)를 내부에 유지함으로써 입력된 자료의 순서를 보관한다. 즉, LinkedHashMap은 기존 HashMap 자료구조에서 LinkedList 자료구조를 섞어놓은 자료구조이다.

HashMap의 특징인, 저장된 값들을 순회하고자 할때 값을 넣은 순서가 아닌 무작위로 출력되게 되는 것을 보완하기 위해 등장하였다.
따라서,LinkedHashMap은 FIFO (First In First Out) 구조로 데이터를 저장한다.

HashMap과 LinkedHashMap의 최종 속도 차이는 큰차이가 없지만, LinkedHashMap은 순서를 유지하기 때문에 메모리 사용량이 HashMap보다 높다.