출처 : 출처
Map(HashMap, TreeMap, LinkedHashMap, HashTree)
Map은 인터페이스
기본적으로 Map은 key:value를 가진 형태(Python의 Dictionary)
리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 key를 통해 value를 찾음
요소의 저장 순서를 유지하지 않음
key : 중복 불가 / value : 중복 가능
HashMap vs HashTable
-
HashMap
- key or value에 null 가능
- 멀티쓰레드에서 안전하지 않음
-
HashTable
- key or value에 null 불가능
- 멀티쓰레드에서 안전함
따라서, HashMap을 Thread safe하게 쓰려면
Map m = Collections.SynchronizedMap(new HashMap(...));같이 선언해야 함
HashMap
Java에서 주로 활용하는 Map
내부적으로 Entry<K, V> Entry Array로 구성되어 있음
Array(배열)의 index를 hash 함수를 통해 계산함
내부적으로 Hash 값에 의해 어떤 bucket에 담길지 결정됨(일종의 index)
만약 hash 값이 동일하다면 같은 bucket 내에 list로 연결됨(일종의 LinkedList처럼 Entry안에 next Entry를 저장하는 변수 존재)
Hash값을 이용해서 저장하기 때문에 순서를 보장하지 않음
get() 메서드 => Hash값으로 해당 Array에 바로 접근 가능함 => 성능 O(1), 빠른 편
TreeMap
Entry가 Tree 형태로 저장되어 있음
특정 Entry에 접근하려면 O(logn) 성능 보임
SortedMAp 인터페이스를 구현하고 있음 => Key 값을 기준으로 정렬 되어있음.
따라서, 이는 Comparator를 구현해 정렬 순서 변경 가능함.
BST(Binary Search Tree)
- 각 노드의 자식이 2개 이하인 트리
- 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼
- 순서를 보장함
LinkedHashMap
큰 흐름에서 HashMap과 비슷함
하지만, Entry 내 before / after Entry가 저장되어 있는 것이 특징임
HashTable
Map 인터페이스를 구현한 클래스
중복을 허용하지 않음
동기화 처리가 되어있어 Thread safe함
