Maps & Dictionaries

Maps이란?

맵은 key-value를 갖는 entries의 검색할 수 있는 모음이다.

중복키는 허락되지 않는다. 키가 각각 다름

Dictionary란?

같은 키를 허락한다. 중복허용.

Maps & Dictionaries의 공통 Entry ADT
entry는 key-value의 쌍을 저장한다.(k,v)
주요 메소드

• key(): 관련있는 키값을 리턴.
• value(): 관련있는 값을 리턴.
• setKey(k): k의 키를 세팅
• setValue(v): v세팅

Map ADT

find(k): key k와 연관된 value반환
put(k,v): 키 k와 값v 삽입
erase(k): k와 연관된 value 제거

Dictionary ADT

find(k)
put(k,v)
erase(k)
begin(), end(), size(), empty()
findAll(k): 중복된 키를 허용하기 때문에 k에 해당되는 모든 엔트리를 찾을 수 있다.

Map의 예시

리스트 기반 Map

비정렬리스트(doubly-linked list 기반)를 이용하여 구현한다.
list S 안에 map의 아이템을 저장

find()

Algorithm find(k):
	for each p in [S.begin(), S.end()) do
    	if p->key() k then
        	return p
	return S.end()

탐색해야하기 때문에 O(n)

Algorithm put(k,v):
	for each p in [S.begin(), S.end()) do
    	if p->key() k then //동일한 키가 리스트에 있는 경우
        	p->setValue(v)
            return p
    //동일한 키가 리스트에 없는 경우
    p = S.insertBack((k,v)) //맨 뒤에 삽입
    n = n+1; //리스트크기 +1
    return p

보는 것처럼 뒤에 삽입하기 때문에 시간복잡도는 O(1)

Algorithm erase(k):
	for each p in [S.begin(), S.end()] do
    	if p.key() = k then
        	S.erase(p)
            n = n-1
            //동일한 키가 없으면 그냥 넘어감.
            //doubly Linked List기반이기에 앞뒤 노드를 Re-Link 해야한다.

탐색해야하기 때문에 O(n)

비정렬리스트 기반 맵은 작은 사이즈나, 검색, 삭제가 드물게 일어나는 상황에 좋다.

Search Table

서치 테이블은 정렬된 배열로 구현된 딕셔너리이다.
key에 의해 정렬된 배열기반 시퀀스 안에 딕셔너리의 아이템을 저장한다.
우리는 외부comparator를 받아 정렬에 이용한다.

• find: Binary search 알고리즘을 사용하여 O(log n) 시간이 걸린다.
• put, erase: 최악의 경우 가운데에서 삽입, 삭제되면 n/2개의 데이터에 대해 Shift연산을 수행하므로 O(n)시간이 걸린다.

Search Table은 작은 사이즈나, 검색, 삭제가 드물게 일어나는 딕셔너리에 좋다.

Binary Search

딕셔너리에서 find(k) 수행에 대해 알아보자.

• up&down게임과 유사하다.
• 각 스텍에서 k일 가능성이 있는 아이템의 개수는 절반이 된다.

Example: find(7)
m = [(l + h)/2] -> 내림연산 이용