• Maps are a searchable collection of key-value entries
  • Lookup the value using the key
  • Keys are unique

The Map ADT

public interface Map<K,V>{
    int size();
    boolean isEmpty();
    V get(K key); //return the value associated with key in the map, or null if it doesn't exist
    void put(K key, V value); //associate the value with the key in the map
    void remove(K key); //remove the key and it's value from the map
    Collection<E> entrySet(); //return an iterable collection of the values in the map
    Collection<E> keySet(); //return an iterable collection of the keys in the map
    Iterator<E> values(); //return an iterator over the map's values

List-Based Map

A basic map can be implemented using an unsorted list.

  • get(k)
    • Does a simple linear search of the list looking for the key,value pair
    • Returns null if search reaches end of list and is unsuccessful
  • put(k,v)
    • Does linear search of the list to see if key already exists
      • If so, replace value
    • If not, just add new entry to end
  • remove(k)
    • Does a linear search of the list to find the entry and removes it
  • All operations take time so this is not very efficient