[Java] Map 자료구조

Map

Java의 Map 인터페이스는 Collection 인터페이스와는 다른 저장 방식을 가진다.

• 키와 값을 하나의 쌍으로 저장한다. (key-value 방식)
• 자바의 구현체로는 HashMap, HashTable, ConcurrentHashMap,LinkedHashMap, TreeMap 등이 존재한다.
• 리스트나 배열처럼 순차적으로 값을 구하지 않고 key를 통해 바로 value를 얻을 수 있다. -> 조회 시간 복잡도 O(1)

HashTable, HashMap

• Hashing : 키에 hash function을 적용해 테이블의 주소를 계산해 원소에 접근하는 방식을 말한다.
• hash function : 키를 입력으로 받아 Hash address를 생성하고, 이 주소를 hash table의 인덱스로 사용하게 한다.
• 해시코드를 사용해 중복을 제거한다.
• 해싱을 사용하여 많은 양의 데이터를 검색해도 속도가 빠르다.
• HashMap
  • 키 값으로 하나의 null을 허용한다.
  • synchronized가 적용되지 않았다.
• HashTable : 키에 대한 연산에 의해 직접 접근이 가능한 구조이다.
  • Java에서 Map 인터페이스의 레거시 구현체로 Key와 Value의 한 쌍으로 이루어지는 데이터의 집합이다.
  • key 혹은 value 값으로 null 불가능
  • synchronized가 적용되어 thread-safe하다. (멀티스레딩 가능)

ConcurrentHashMap

• HashMap에 동기화 처리를 해 멀티스레드 환경에서 사용할 수 있도록 하였다.
• key 혹은 value 값으로 null 값을 허용하지 않는다.
• 메소드 단위가 아니라 코드 블럭 단위로 synchronized 처리되어있다.
• 조회시에는 block되지 않고, 변경시에만 block처리된다.

LinkedHashMap

• 저장 순서를 보장하는 HashMap이다.
• 순서를 유지하기 위해 이중 연결 리스트를 사용한다.
  • 기존 HashMap보다 메모리 소모가 많고 성능이 떨어진다.
• synchronized가 적용되지 않으므로 멀티스레딩 환경에서는 Collections.synchronizedMap으로 감싸줘야 한다.

	Map m = Collections.synchronizedMap(new LinkedHashMap(...));

TreeMap

- 이진 검색 트리(binary search tree) 형태의 Map 자료구조이다. - 데이터 추가 및 제거 동작 시간이 매우 빠르다. - 중복된 키 값 저장이 불가능하다.

• 내부적으로 레드-블랙 트리(Red-Black tree)로 구현되어 있으며, NavigableMap의 구현체이다.
• synchronized가 적용되지 않으므로 멀티스레딩 환경에서는 Collections.synchronizedSortedMap으로 감싸줘야 한다.

    SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));