---

The Map (Associative array) abstract data type

---

• Map (Associative Array)
  • Definition:

    An associative array (a.k.a map, and a generalized form dictionary) is an abstract data type consisting of: a collection (set) of unique keys a collection (set) of values, where each key is associated with one value (map, associative array) or set of values (dictionary)

    Example:

    { ("cs170", "Siva"),   ("cs171", "Li"),   ("cs323", "Cheung"),   ("cs355", "Cheung") }

  ---

  ---

• Terminology
  • Entry:

    The entry is the unit of information stored inside a map data structure Example: ("cs171", "Li")

    ---

  • Key:

    The key is the value used to find an entry quickly The key is also known as the index

    ---

  • Value:

    The value the the rest of the entry that is not used in indexing The value part usually contain information on the key

  ---

  ---

• Operations supported by the Map ADT
  • Operations applicable on a Map object:

    int size() return the number of entries in the map (associative array) boolean isEmpty() returns true in the map is empty returns false otherwise Value get(Key k) returns the value asscoiated with the key k (if k is stored in the map) returns null if key k is not in the map Value put(Key k, Value v) If the map does not contain an entry with key k, then insert the (new) entry (k, v) The operation will return null (previous value does not exist) If the map does contain an entry with key k, then replace the old value with (the new value) v The operation will return the old value Value remove(Key k) If the map does not contain an entry with key k, then do nothing The operation will return null (previous value does not exist) If the map does contain an entry with key k, then delete the entry The operation will return the old value Set keySet() returns an iterable collection (i.e., linked list) containing all keys stored in the map data structure keySet().iterator() returns an iterator of all the keys Set values() returns an iterable collection (i.e., linked list) containing all values stored in the map data structure values().iterator() returns an iterator of all the values Set entrySet() returns an iterable collection (i.e., linked list) containing all (key, value) pairs stored in the map data structure entrySet().iterator() returns an iterator of all the (key, value) pairs

  ---

  ---

• Java's Map interface (ADT)
  • Java has (several) implementations of the Map ADT:

    java.util Interface Map<K,V> Type Parameters: K - the type of keys maintained by this map V - the type of mapped values All Known Subinterfaces: Bindings, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, LogicalMessageContext, MessageContext, NavigableMap<K,V>, SOAPMessageContext, SortedMap<K,V> All Known Implementing Classes: AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

    ---

  • Online resources:

    Java's MAP API description: click here Java's MAP Tutorial: click here

  ---

  ---

  ---

  ---

• Examples on using Java's MAP inteface
  • Example 1: entering (key values) into a Map

    (Count the number of items in a command argument)

    public static void main(String[] args) { int i; Integer freq; String s; Map<String, Integer> M = new HashMap<String, Integer>(); // Use HashMap implementation of Map /* ------------------------------------------------------- Enter arg strings into the Map along with frequency ------------------------------------------------------- */ for (i = 0; i < args.length; i++) { s = args[i]; freq = M.get(s); if ( freq == null ) { M.put(s, 1); } else { M.put(s, freq.intValue() + 1); } System.out.println("After processing `" + args[i] + "':"); System.out.println(M); System.out.println(); }

    ---

    Example Program: (Demo above code)                                                

    • Prog file: click here

    ---

    ---

  • Example 2: iterating through key or value sets returned by a Map method

    (Iterating through keys)

    public static void main(String[] args) { Map<String, String> M = new HashMap<String, String>(); M.put("John Doe", "Brother"); M.put("Tom Doe", "Cousin"); M.put("Jane Doe", "Sister"); M.put("Todd Hall", "Neighbor"); M.put("Ralph Smith", "Teacher"); Collection<String> s = M.keySet(); /* ------------------------------------------------ Get an iterator over a Set ----------------------------------------------- */ Iterator iter = s.iterator(); /* ------------------------- Iterate over "iter" ------------------------- */ while(iter.hasNext()) { String x; // Help variable x = (String) iter.next(); // Get next entry System.out.println(x); } System.out.println(); }

    ---

    Example Program: (Demo above code)                                                

    • Prog file: click here

    ---

    ---

  • Example 3: iterating through the entries set returned by a Map method

    (The entrySet is a compound data structure)

    public static void main(String[] args) { Map<String, String> M = new HashMap<String, String>(); M.put("John Doe", "Brother"); M.put("Tom Doe", "Cousin"); M.put("Jane Doe", "Sister"); M.put("Todd Hall", "Neighbor"); M.put("Ralph Smith", "Teacher"); /* ------------------------------------------------ entrySet() returns a "Set<Map.Entry<K,V>>" or: a "Set" of items ----------------------------------------------- */ Collection s = M.entrySet(); /* ------------------------------------------------ Get an iterator over a Set ----------------------------------------------- */ Iterator iter = s.iterator(); // ----------------------------------------- // Shorter: // Iterator iter = M.keySet().iterator(); // ----------------------------------------- /* ------------------------- Iterate over "iter" ------------------------- */ while( iter.hasNext() ) { Map.Entry x; // Help variable x = (Map.Entry) iter.next(); // Get next entry System.out.print(x.getKey() + ": "); System.out.println(x.getValue()); } System.out.println(); }

    ---

    Example Program: (Demo above code)                                                

    • Prog file: click here

  ---

  ---

  ---

  ---

• Implementations of unordered maps
  • OK, now that you have seen how to use (one of) the implementation of Maps in Java, we will discuss how to implement it.

    (I.e., we will learn -- among other things --- how to write the HashMap class)

    ---

  • Common implementations of unordered maps:

    Using a linked list Using an array with the hashing technique (the HashMap class)