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.