> Map (Interface)
Map의 가장 기본 개념은 Key를 Value에 매핑하는 자료의 한 구조란 것 이다. Key는 중복될 수 없으며, 각 Key는 하나의 Value(객체)만을 가질 수 있다. 이는 Map안에 존재하는 Key로 재차 삽입(put)할 경우 해당 Value는 덮어쓰기 된다는 걸 의미하기도 한다. Map interface의 구현체들은 (put, get, remove, containsKey, containsePlue, size, empty)와 같은 기본 작업을 구현한다. 결국 Map은 Key를 이용해 Value를 쉽게 얻고자 할 때 사용한다.
Map은 기본적으로 List, Set과 같은 Java Collection과는 다르게, Collection Interface를 구현하지 않는다. 하지만, Data를 삽입(add or put)하고 삭제(remove)하는 등의 일반적인 자료구조의 형태를 가지고 있다는 점에서 유사하다.
> Hashtable
가장 처음으로 등장한(JDK 1.0) Map의 종류이다. 내부 적으로는 Entry라는 버킷을 만들어 배열형태로 자료들을 저장한다. Hashtable은 기본적으로 Thread-safe하다. (동기화, synchronized) 또한 Null Key와 value를 허용하지 않는다.
실제로는 Hashtable은 최초로 등장한 Map이기에 이전 Java 결과물들의 지원을 위해 존재하는 이상의 의미를 현재는 가지질 않는다. Java API Document에서도 Thread-safe 한 구조가 필요하지 않을 경우 HashMap의 사용을 권장하고 있다. 설사 Thread-safe한 구조 필요하다해도 ConcurrentHashMap을 사용하도록 권장한다.
hashCode와 equals를 이용하고 내부 버킷을 운용하는 방법은 HashMap과 유사하므로 해당 내용은 HashMap에서 설명하도록 하겠다.
> HashMap
HashMap은 Null Key & value를 허용한다. HashMap은 동기화되지 않고 Null을 허용한다는 점을 제외하고는 Hashtable과 거의 동일하다. HashMap은 Element 들의 순서를 보장하지 않는다.
hashTable의 원리는 Element가 될 Class의 hashCode() 메서드를 이용해 Hash 값을 알아낸 후, 해당 Hash값으로 내부 버킷의 배열 인자(index)를 결정, 분배하여 저장한다. 그리고 알고 있겠지만 동일한 Index로 분배가 될 경우(HashCrash) 해당 Index를 인자로 가지는 배열 멤버는 LinkedList와 같은 형태로 동일한 Index Element를 관리한다. 또한 HashMap의 구현에서는 해당 동일한 Index로 배정된 Element의 갯수가 8개 이상되면 그 Index만 TreeNode 형태로 변화한다. (Red-black binary search tree)
HashMap의 성능에 영향을 미치는 두가지 매개 변수가 있다. (1) Capacity는 HashTable의 배열 크기이다 (초기 default 16). (2) LoadFactor는 Capacity가 자동으로 증가하기 전에 HashTable이 얼마나 가득 찼는지를 나타내는 측도이다. Element의 갯수가 LoadFactor 및 현재 Capacity를 초과하면 2배로 resize가 일어나며 내부 Element들은 다시 Index를 부여 받아 분배된다.
일반적으로, Default loadFactor (0.75)는 시간과 공간 비용 사이에서 좋은 절충을 제공한다. 값이 높을수록 공간 오버 헤드는 감소하지만 조회 비용은 증가한다. 초기 Capacity를 설정할 때는 ReHashing 작업 수를 최소화하기 위해 예상되는 Element 갯수와 loadFactor를 고려해야 한다. 초기 Capacity가 삽입된 Element 갯수를 LoadFactor로 나눈 값보다 큰 경우에는 ReHasing 작업은 수행되지 않는다.
많은 Element를 HashMap에 저장해야 하는 경우 충분한 Capacity를 초기 값으로 생성하면 resize 오버헤드를 줄일 수 있다. 또한 Element가 되는 객체의 hashCode() 메서드가 제대로 구현되도록 해서 동일한 Hash값이 발생하는걸 줄임으로 HashMap의 성능을 높일 수 있다.
> TreeMap
Red-black binary search tree 자료구조를 표현한다. Key의 Natural ordering에 따라 순서가 정해지며, 필요할 경우 생성자에 제공된 Comparator에 의하여 정렬 순서가 정해지도록 할 수 있다.
TreeMap은 키를 정렬 가능한 순서에 따라 저장하기 떄문에 hashCode() 메서드는 전혀 사용되지 않는다. 또한 TreeMap은 Red-black tree의 특성 대로 검색, 삭제, 삽입 모든 동작들이 O(log n)의 처리 성능을 가진다.
HashMap과의 주된 차이는 순서를 보장함에 따라 Iterator를 활용해 순서대로 순회가 가능하다는 것이다.
> LinkedHashMap
HashMap을 상속하여 구현되었다. LinkedHashMap은 멤버가 되는 Element들이 doubly-linked (이중링크) 되었다는 점에서 HashMap과 차이가 있다. Link는 삽입된 순서대로 Iteration 할 수 있게 생성된다. 동일한 Key를 Map에 다시 삽입하는 경우에는 삽입 순서는 영향을 받지 않는다. (containsKey(k) true 일때, put(k, v) 가 호출되면 k가 다시 삽입된다.)
HashMap과 동일하게 LinkedHashMap도 성능에 영향을 미치는 두가지 매개 변수가 있다. (HashMap 참조, Capacity/Loadfactor) 다만, iteration time은 Capacity에 영향을 받지 않기 때문에, Capacity를 지나치게 높게 선택했을 경우의 페널티는 HashMap의 경우보다 덜 심각하다.