Map
'key(키)'를 통해서 'value(값)'를 얻는다.
'Map'은 키를 오로지 하나의 값을 연결한다. 'Map'구조는 중복 키를 허용하지 않지만 두 개의 고유한 키는 동일한 값에 매핑할 수 있다. Map에서 특정 데이터를 찾을 때 키를 이용해서 검색한다.
모든 값은 키를 가지고, 모든 키는 값을 가진다. 예를 들어 모든 사람은 각자의 주민등록 번호가 있다.
키는 고유하고 null일 수 없다.
Map을 사용하는 'HashMap'과 'TreeMap'이 있다.
구현
Unsorted Array
'put' operation은 새로운 'MapEntry'개체를 생성하고 배열에 있는 모든 현재 키에 대한 완전 탐색 (brute force search) (O(n))을 실행시켜 중복을 방지한다. 중복 키가 발견되면 연결된 'MapEntry' 개체가 새로운 개체로 대체되고 해당 개체의 값 특성이 반환된다.
'put', 'get', 'remove', 'contains' operations는 모두 현재 배열 내용을 완전 탐색해야한다. 이 작없은 모두 O(n) 이다.
Sorted Array
Sorted array는 이진검색 알고리즘을 사용할수 있다. 이진 검색 알고리즘은 'get', 'contains' operations의 효율이 향상된다.
Unsorted Linked List
Unsorted array와 비슷하게 대부분의 operations는 완전 탐색을 해야한다. 공간 측면에서 linked list는 필요에 따라서 커지고 축소되기 때문에 array에 비해 메모리 관리에서 어느 정도 이점이 있다.
Sorted Linked List
'Map'에서는 sorted linked list보다 unsorted linked list를 사용하는 것이 더 좋다. 중간 요소를 찾는 것이 비효율적이기 때문이다.
Binary Search Tree
만약 'Map'이 균형 이진 검색 트리를 지원한다면, 'put', 'get', 'remove', 'contains'는 O(log(n))의 효율성을 나타낼 수 있다.
Map
Get a 'value' through the 'key'.
Maps associate a key with exactly one value. A map structure does not permit duplicate keys but two distinct keys can map onto the same value.
Every value has key, Every key has value. For example, every people have their own resident registration number.
'key' is unique and cannot be null.
There are 'HashMap' and 'TreeMap' using a Map.
Implementations
Unsorted Array
The put operation creates a new MapEntry object and perfoms a brute force search (O(n)) of all current keys in the array to prevent key duplication. If a duplicate key is found, then the associated 'MapEntry' object is replaced by the new object and its 'value' attribute is returned.
'put', 'get', 'remove', and 'contains' operations would all require brute force searches of the current array contents. They are all O(n).
Sorted Array
Sorted array can use the binary search algorithm. It is improving the efficiency of 'get' and 'contains' operations.
Unsorted Linked List
Similar to an unsorted array, most operations require brute force search. In terms of space, a linked list grows and shrinks as needed so it is possible that some advantage can be found in terms of memory management, as compared to an array.
Sorted Linked List
To implement the 'Map', better to use Unsorted linked list than Sorted linked list. Because it is not efficiency to inspect the 'middle' element.
Binary Search Tree
If the 'Map' can be implemented as a balanced binary search tree, then 'put', 'get', 'remove', and 'contains' can exhibit efficiency O(logN).
Reference
- CS401-Data Structure. (2021). Micheal Y. Choi, Ph.D. Illinois Institute of Technology.
