Map

이번 게시물은 자료구조 중 Map에 대해 알아보려고 한다.

Map

Map은 interface의 종류이다. Key와 Value를 가지는 자료형으로, Key값의 중복은 허용하지 않으며, java.util 패키지에 여러 집합들을 사용하기 위한 여러 interface와 class들이 정의되어 있다. (ex. HashMap, HashTable, TreeMap)

HashMap

HashMap은 Map interface를 implements한 클래스이다. HashMap 역시 Key, Value로 구성되어 있고, 중복을 허용하지 않는다. Map과 다른 점이라면 Red Black Tree 대신에 이름에서 명시된 듯이 Hash 알고리즘을 통해 구현되어 있다. 순서를 보장하지 않으며 Null값이 사용 가능하다.

HashTable

HashTable은 Hashtable Map interface를 implements한 클래스로 중복을 허용하지 않는다. HashMap과 다른 점은 Key나 Value값으로 Null을 허용하지 않는다.

TreeMap

TreeMap은 SortedMap을 상속하였다. Red Black Tree를 통해 구현되었고, Key와 Value로 구성되어 있다. 중복을 허용하지 않으며, Key값들에 대한 정렬이 이루어진다.

LinkedHashMap

LinkedHashMap은 연결리스트로 구현된 Map으로, 입력된 순서를 저장한다. LinkedHashMap은 HashMap의 sub class이기 때문에 HashMap의 모든 특징을 상속받는다.

결론

• HashMap, HashTable, TreeMap은 모두 Map의 하위 클래스.
• HashMap은 Hash로 구현, TreeMap은 Red Black Tree로 구현.
  - Hash이므로 정렬 x, Red Black Tree이므로 정렬 O
• HashMap은 Null값 허용 O, HashTable은 Null값 허용 X
• 보통은 검색 성능이 좋은 HashMap을 많이 사용. (O(1))
• Key값이 일정한 수준대로 정렬되도록 하려면 TreeMap을 사용.
  - 랜덤 접근에 대해서는 O(log n)이므로 많은 데이터를 넣을 경우 성능 이슈가 발생할 수 있음
• 입력 순서가 중요한 경우에는 연결 리스트를 사용하는 LinkedHashMap을 사용