[Data Structure (Java)] Map

https://crane206265.tistory.com/86

[Data Structure (Java)] Heapsort

이제 다시 새로운 주제를 해봅시다. Map입니다.

---

Map ADT

: Key-Value pair abstraction

- insert a value with specified key

- given a key, search for the corresponding value

 

ex) symbol table, dictionary, associative array ...

* associative array abstraction

: generalized array - keys do not need to be integers between 0~n-1

---

Map API

API for the Map (Data Type - key : Key / value : Value) (M : Map instance)

methods	explanation
int size()	return # of entries in M
boolean isEmpty()	return if M is empty
Value get(Key k)	return the value v associated with key k (if such entry does not exist : return null)
void put(Key k, Value v)	if key k exist : replace the associated value to v else : adds entry (k, v)
Value remove(Key k)	remove the entry with key k, return its value (if M is empty : return null)
<Iterable> keySet()	return the iterable collection containing all the keys in M
<Iterable> values()	return the iterable collection containing all the values in M
<Iterable> entrySet()	return the iterable collection containing all the key-value entries in M

 

* Conventions
- no duplicate key
- no null keys / values -> we don't know wheter key/value is null or does not exist
- no limit on # of key-value pairs

---

Map implementation

in java.util package

1. java.util.HashMap : not ordered entries
2. java.util.LinkedHashMap : entires can be retrieved in insertion order / access order
3. java.util.TreeMap : TreeMap class implementing SortedMap is efficient for traversing the keys in sorted order

ex) Class<keyDataType, valueDataType> -> HashMap<String, Integer>, etc.

 

 

<Elementary implementation of Map>

Unordered linked list : sequential search

operation	running time	explanation
search	O(n)	scan through all keys until find a match
insert	O(n)	scan through all keys to find if the key already exists

 

Ordered array : binary search

- parallel array for key-value pairs : one for keys Key[] & one for values Value[]

operation	running time	explanation
search	O(log n)	binary search
insert	O(n)	searching position to insert : O(log n) shifting to maintain sorted array : O(n) ==> O(n)