[자료구조] 탐색

맵(map)이란?

• 맵(map) 또는 사전(dictionary)은 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조
• 키를 가진 레코드(keyed record) 또는 엔트리(entry)라 불리는 키-값 쌍(key, value)을 테이블에 저장한다
  • 이때 각 키는 유일하고 맵에 저장되는 키와 값은 어떠한 자료형도 가능하다.
• "값"은 변경할 수 있지만 "키"는 변경할 수 없다.

맵에서 필요한 연산들의 추상 형태

- 객체: 유일한 키를 가진 엔트리(키를 가진 레코드)의 집합

- 연산

(1) create(): 공백 상태의 맵을 생성
(2) search(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 반환
(3) insert(entry): 테이블에서 주어진 entry를 삽입
(4) delete(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 삭제
(5) count(): 테이블의 모든 레코드 수를 반환

맵을 구현하는 방법

1. 정렬되지 않은 배열을 사용하는 방법
   • 시간복잡도: O(n)
2. 정렬된 배열을 사용하는 방법
   • 시간복잡도: O(log n)
3. 이진 탐색 트리를 이용하는 방법
   • 시간복잡도: O(log n)
   • 단, 이진 트리의 균형을 잘 맞췄을 경우에 해당
4. 해싱을 사용하는 방법
   • 시간복잡도: O(1)
   • 저장된 레코드의 수에 관계 없이 일정한 시간 안에 탐색 가능