Map이란?

• 고유한 키를 기반으로 Key - Value 쌍으로 이루어져 있는 정렬된(삽입할 때마다 자동 정렬되는) 자료구조이다.
• 균형잡힌 이진탐색트리인 레드-블랙트리로 구현된다.

Map의 시간복잡도

• 참조 : O(logN)
• 탐색 : O(logN)
• 삽입 / 삭제 : O(logN)

Map의 특징

• 고유한 Key를 갖기 때문에 하나의 Key에 중복된 값이 들어갈 수 없다. (Value는 중복이 가능)
• 자동으로 오름차순으로 정렬. (아스키코드 순으로 정렬된 값을 기반으로 탐색)
• 대괄호 연산자 []로 해당 키를 직접 참조할 수 있다.

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

• HashMap
  • key와 value의 쌍으로만 구성이 될 뿐 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없다.
  • 즉, 사용자는 키와 값이 구성되는 위치를 결정 하거나 알 수 없다.
• TreeMap
  • key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조
  • key값을 통한 탐색 뿐 아니라 key값의 정렬을 통한 탐색 등을 하기에 용의 하다.