Maps ADT

Question 1

Name the 3 properties of a Map as well as a reason for the inspiration of maps

Answer 1

1. A searchable collection of key, value entries
2. Main operations are searching, inserting and removing
3. Multiple entries with the same key are not allowed

Maps are used to map a key, normally some sort of unique identifier to a specific value. That collection is the searchable

Question 2

Name 2 applications of the Map ADT

Answer 2

A student database

an address book

Question 3

Name the 3 main functions of a map and a brief definition of each

Answer 3

remove(k): remove key-value pair return value or null if DNE
put(k,v) : new entry and return null or replace old value and return it
get(k) : return associated value otherwise return null

Question 4

Write down the pseudo code for the get method

Answer 4

get(k){

for each p in S.positions()
if p.element().getKey() == k
return p.element().getValue()

return null
}

Question 5

Write down pseudo-code for the put(k,v) method

Answer 5

put (k,v){

for each position p in S.positions()
if p.element().getKey() == k
t = p.element.getValue()
set (k,v)
return t

S.addLast((k,v))
S.size++
return null

Question 6

Write down pseudo-code for the remove(k) method

Answer 6

remove(k){

for each p in S.positions 
if p.element().getKey() == k 
t = p.element().getValue()
S.remove(p) 
S.size--
return t

return null

}