[자료구조] Map

정의

Map은 <key, value> pair를 저장하는 자료구조이다. Map은 여기에 더해 다음 두 가지 특성을 가진다.

1. key는 반드시 자연수가 아니어도 괜찮다.(non-numeric key)

2. key가 반드시 연속될 필요는 없다.(non-consecutive key)

3. value는 중복될 수 있지만, key는 반드시 unique해야 한다.

 

응용

어떤 unique한 key로 무엇인가를 분류해야 하는 경우에 사용할 수 있다.

- 주민등록번호(key),이름(value): 이름은 동명이인이 있을 수 있지만 주민등록번호는 각 개인이 모두 고유한 값을 가지기 때문에 map을 이용하는 것이 적절하다.

- 국가 이름(key):각 국가가 사용하는 화폐(value) : 각 국가 이름은 고유하지만, 화폐는 여러 국가가 같은 화폐를 사용할 수 있다.(EU 국가들의 유로 사용 등) 

 

구현

각 node가 <key, value> pair를 저장하는 unsorted DLL로 구현할 수 있다. 

이러한 방식으로 map을 구현하게 되면, unsorted DLL을 이용했기 때문에 insertion 연산은 O(1) 시간에 수행 가능하지만, 기타 다른 연산들은 O(n) 시간에 수행된다.(search, remove 등) 이러한 단점을 보완할 수 있는 것이 다음에 포스팅할 hash이다.