5. Map & Dictionary

Map이란?

Map은 key-value 형태로 데이터를 저장하는 자료구조이며,

key 값을 통해서 데이터를 검색, 저장, 삭제한다.

이 때, map은 중복된 key 값은 허용되지 않는다.

 

예를 들어, 전화번호부의 경우 같은 전화번호에 여러 이름은 저장되지 않는다.

따라서 전화번호를 key 값으로, 이름을 value로 map에 저장하면 된다.

 

Dictionary란?

Dictionary는 기본적으로 map과 같이 key-value 형태로 데이터를 저장하지만,

map과 달리 중복된 key 값이 허용된다.

 

예를 들어 단어 사전의 경우 하나의 단어에 여러 가지 뜻이 있을 수 있다.

따라서 단어를 key 값으로, 단어의 뜻을 value로 dictionary에 저장하면 된다.

 

 

그렇다면 List를 기반으로 Map을 구현하면 어떻게 find, put, erase를 수행하고 어느 정도의 시간이 걸리는지 알아보자.

 

Find

list에서 데이터를 찾으려면 노드를 하나씩 돌아보며 일치하는 key 값을 찾아보아야 한다.

최악의 경우 일치하는 key 값이 없다면 모든 노드를 돌아봐야 하므로 O(n)의 시간이 소모된다.

 

Put

map에 데이터를 넣을 때에는 key 값이 존재하면 value를 수정하고, 존재하지 않으면 끝에 추가하게 된다.

이 때 데이터를 수정, 추가는 상수 시간에 가능하지만, key 값이 존재하는지 파악하려면 O(n)의 시간이 소모된다.

 

Erase

삭제 또한 마찬가지로 map에 일치하는 key 값이 있는지 먼저 탐색해야 하므로 O(n)의 시간이 소모된다.

 

 

이와 같이 데이터의 검색, 삽입, 삭제 모두 O(n)의 시간이 소모되기 때문에

map과 dictionary는 Hash Table이나, Binary Search Tree와 같은 자료구조로 구현하는 것이 효율적이다.

(Hash Table과 Binary Search Tree는 별도의 게시글에서 설명)