11-2 (탐색과 맵 구조)

자료를 효율적으로 탐색하기 위해 데이터르 잘 정리하는 방법으로 탐색과 맵 구조가 있다.

 

탐색은 레코드의 집합에서 원하는 레코드를 찾는 작업이다.

레코드의 집합을 테이블이라고 칭하고, 레코드들은 서로를 구별하여 인식할 수 있는 키(혹은 탐색키)를 가지고 있다.

=> 탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업이다.

 

맵또는 딕셔너리는 자료를 저장하고 탐색키르 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 탐색을 위한 자료구조를 말한다. 맵은 엔트리라는 키를 가진 레코드(keyed record)의 집합이다.

엔트리는 키와 값 두 개의 필드를 가진다.

 

키(key): 영단어나 인명같은 레코드를 구분할 수 있는 탐색키

값(value): 영단어의 의미나 어떤 사람의 주소와 같은 탐색키와 관련된 값

 

이렇게 맵은 키-값의 쌍으로 이뤄진 엔트리의 집합으로 파이썬은 내장 자료형으로 딕셔너리를 제공하는데, 이것은 자료구조 맵을 구현한 예이다.

 

Map ADT

search(key): 탐색키 key를 가진 레코드를 찾아 반환

insert(entry): 주어진 entry를 맵에 삽입

delete(key): 탐색키 key를 가진 레코드를 찾아 삭제

 

맵을 구현하는 여러가지 방법으로는

가장 간단한 방법은 엔트리를 리스트에 저장하여 킷값에 따라 정렬하여 맵을 만들 수도 있고, 정렬하지 않고 맵을 만들 수 있는데, 방법에 따라 연산들의 성능에 차이가 발생한다.

맵의 탐색 성능을 향상하고자 하면 이진탐색트리를 사용한다.

맵을 구현하기 가장 좋은 방법은 해싱이다.