[자료구조] 10. 맵 & 딕셔너리(Map & Dictionary)

맵 & 딕셔너리(Map & Dictionary)

맵과 딕셔너리는 매우 유사한 자료구조다. 이에 맵에 대해서 먼저 설명하고, 맵과 딕셔너리의 차이점을 알아보겠다.

우선 맵은 키-값(key-value) 쌍으로 이루어진 집합이다. 키를 통해서 값을 추가, 탐색하고 이를 수정, 삭제할 수 있다. 이때 맵의 특징은 같은 키를 가지는 여러 값이 존재할 수 없다는 것이다.

 

그렇다면 딕셔너리는 무엇일까? 딕셔너리는 기본적으로 맵과 동일하지만, 중복된 키값이 존재할 수 있다는 특징이 있다.

 

다만 실제로 맵과 딕셔너리의 차이를 엄밀하게 다들 지키는 것은 아니고, 반대의 의미로 쓰이거나 하여 사실상 같은 의미를 가진다고 볼 수 있다.

예를 들어 파이썬의 딕셔너리는 기본적으로 키 중복을 허용하지 않지만 딕셔너리(dict)라는 이름을 가지고 있다.

ADT

맵의 ADT

find(key): key 키를 가지는 값을 리턴한다.
put(key, value): key 키에 value 값을 삽입한다.
erase(key): key 키를 가지는 정보를 삭제한다
추가적으로
size()
isEmpty()
begin()
end()

딕셔너리의 ADT

find(key): key 키를 가지는 값을 리턴한다.
findAll(key): key 키를 가지는 모든 엔트리를 반환한다(pointers or an iterator).
put(key, value): key 키에 value 값을 삽입한다.
erase(key): key 키를 가지는 정보를 삭제한다
추가적으로
size()
isEmpty()
begin()
end()

기본적으로 맵의 ADT와 동일하나, 키 중복이 가능하기에 해당 키 값을 가지는 모든 엔트리를 불러오는 함수가 존재한다.

구현

간단히 구현의 에시를 들면 unsorted list(linked list)를 이용한 구현이 존재한다.

실제로 효율 좋은 구현을 위해서는 해시테이블이나, 이진탐색트리를 이용한다.

효율

	연결리스트(Linked list)	해시테이블(Hash table)	이진탐색트리(Binary search tree)
find()	O(n)	O(1)
put()
erase()	O(n)

작성중