학교에서 진행되는 자료구조 수업을 듣고 중요한 부분 위주로 정리하였습니다. 내용 상에 오류가 있다면 댓글로 피드백 부탁드립니다!

Dicionary란

• 검색 가능한 (key value) entry의 모음(collection)
• 동일한 key를 가지는 entry가 한 dictionary 안에 들어갈 수 있다.
• 주요 기능: 엔트리 search(탐색), insertion(삽입), deletion(삭제)
• 응용: 동의어를 포함하는 영어 사전, 연락처(phone book) 등

구현 방법

map은 list와 hash-table로 구현할 수 있다. dictionary는 여기에 추가해서 제안적인 상황에 ordered search table으로도 구현할 수 있다.

• list-based
• hash-table implementation
• ordered search table

Dictionary Operations

entry find(k)
list findAll(k)
entry insert(k,v)
entry remove(e)
eist entries()
size(), isEmpty()
Common operations: size(), isEmpty()

list-based dicionary

• 정렬되지 않은 리스트로 구현 가능
• 임의의 순서로 entry를 NodeList 또는 ArrayList에 저장

성능 분석

• insert: $O(1)$
• find, find: $O(n)$

유용한 상황

• dictionary의 크기가 작을 때
• 삽입(insertion)이 많고 탐색(search)과 제거(removal)이 적을 때
• 예시: 시스템 로그(audit trails)
  log란 운영체제에서 사용자 또는 프로그램에서 발생시키는 event를 기록하는 장소, event는 자주 발생하나 검색은 자주 하지는 않으니 dictionary가 유용하다.

Hash Table Dictionary

• Seperate chaining과 open addressing으로 collision을 해결한다.

성능 분석

• 똑같은 key 값을 갖는 entry는 무조건 collision이 발생함.
• find, remove, insert: $O(1)$
• findall: $O(1 + s)$ (s는 같은 키를 갖는 엔트리의 개수)

Ordered Search Table

• 줄여서 search table로 부르기도 한다.
• 정렬된 array list로 구현하는 dictionary

성능 분석

• find, remove: $O(n)$
• search: $O(nlogn)$

유용한 상황

• insert는 느리지만 검색이 빠르다.
• insert가 적고 검색이 많은 데이터가 있을시에 유용함
• 신용카드는 사용될 때마다 database에서 승인(검색)이 일어남
• 신용카드 등록 횟수는 적으나 검색(권한 인증) 횟수는 많아 효율적

Binary Search(이진 탐색)

• 일정한 범위를 두고 하는 숫자 맞추기 게임과 비슷함.
• 각 시행마다 가능한 엔트리의 수가 반으로 줄어서 $O(logn)$에 끝난다.
• 의사코드

low = 0, high = n - 1, mid = [(low + high)  / 2]
if k = e.getKey()) return e
else if k < e.getKey(), the range of indices from low to mid - 1(high = mid - 1)
else if k > e.getKey(), the range of indices from mid + 1 to high(low = mid + 1)
if low > high, it fails to find k in the array list(return null)
go to step 1

Dictionary 구현끼리 비교하기

• hash table의 insert
  • seperate chaining: O(1): 바로 insert로 collision 생긴 곳에 추가
  • open addressing: 평균 O(1), 최악시 O(n)

Dictionary의 확장

Location-aware entries

• 자신의 위치를 의미하는 노드와 연결하는 백링크 생성
• remove를 O(1) 시간에 수행할 수 있다.

Ordered dictionary

• K값의 앞과 뒤에 무엇이 있는지 찾음
• first(): 가장 작은 키, last(): 가장 큰 키
• successor: k값보다 크거나 같은 키를 찾아줌
• Predecessors: k값보다 작거나 같은 키를 찾아줌