Dictionary

Dictionary

Concepts :

• 우리가 원하는 내용을 찾기 위하여 key를 검색한다.
• Key comparison : key값을 비교하여 같은 key 값을 가진 value를 가져온다.

 

Records and Keys :

key를 record와 별도로 저장을 한다.

(key, record) pair 형태로 가지고 잇으며 이를 (key, value) pair라고도 부른다.

 

 

Sorted vs Unsorted Array List Dictionaries

list가 key 값으로 sorted가 되어 있을 때 :

• binary search를 이용하여 key 값을 검색할 때 빠르게 검색할 수 있다. O(logn)
• 그러나 새로운 (key, value)값을 insert할 때 순서에 맞춰서 insert를 해야하기에 느리다. (O(n)이 걸린다. O(logn)이 아닌 이유로는 뒤에 있는 (key, value) pair들을 shift 해야하기 때문이다.)

 

list가 sorted가 되어있지 않을 때 :

• key값을 검색할 때 느리다. O(n)
• 그러나 insert할 때는 O(1)밖에 걸리지 않는다.

따라서 search가 많다면 sorted list가 적절할 것이고, insertion이 많다면 sorting이 큰 의미는 없을 것이다.