[Data Structure / Java] ✒️ Map

Array는 index로 빠르게 읽기는 좋은데 유연하지 못하고 ...

List는 유연하기는 한데 index로 빠르게 읽기는 못하고...

유연하면서도 빠르게 읽어내는 방법이 없을까?

 

Map

Key와 Value로 이루어진 자료구조.

순차적으로 메모리에 데이터를 저장하는 Array와 List와는 달리 Key와 Value로 구성되어 있다.

 

 

 

hashing: Key를 범위(배열 크기)에 맞게 적절히 겹치지 않는 index로 변경한다.

hash function: hashing의 기능을 수행함, key값을 넣으면 hash값으로 변환하여 bucket의 index로 사용된다. 

bucket: Map의 Array

hash collision: 해쉬 충돌, 이미 존재하는 key값에 다른 key값으로 같은 hash의 index를 가리킨다면 가리키는 곳의 List에 값을 추가한다. 

 

Mapping table

또는 Map, dictionary라고도 부른다.

 

Key값과 Value값을 테이블로 정리할수도 있다. 

 

Map의 특징

1. Key는 중복일 수 없다.

- Key는 Map 자료구조에서 대응하는 값을 찾기 위한 요소로 중복을 허용하면 안된다. 만약 중복이 된다면 접근하는데 문제가 생길 수 있기 때문

2. Key와 Value 중 하나만 존재하지 않는다.

3. Value는 중복이 가능하다.

 

Map 자료구조의 대표적인 종류

• HashMap: Key와 Value의 쌍으로만 구성이 될뿐 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없다. 즉, 사용자는 Key와 Value값이 구성되는 위치를 결정하거나 알 수 없다.
• HashTable: 멀티스레드 환경에서 사용해야 한다, thread-safe를 해야 할 때.
  (가능하면 ArrayList나 HashMap을 사용할 것.)
• ConcurrentHashMap: thread-safe를 해야 하고 많은 동시성이 요구 될 때 사용한다.
• TreeMap: Key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조, Key값을 통한 탐색 뿐 아니라 Key값의 정렬을 통한 탐색등을 하기에 용이하다.
• LinkedHashMap: 데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조이다. Array, List처럼 indexing접근에 용이하다.