Title: Map
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Map - SortedMap Interfaces

There are times when you want to have keyed objects. You have a class that contains information, and you look it up by some key. For example, I may have a class that contains all of the information on a student a WCC. I would like to be able to look up the student by some key like student number or by name. I want a technique that doesn't require me to search through a list.

In this set of notes we will use another example: States and Captols. I want to maintain information about capitols of the States. I would like to find the record for Lansing by using a Key of Michigan.

1. The Map interface is not derived from the Collection interface. A Map interface has a lot in common with a Collection class, but fundamentally a Map is different. A Map always has a relationship between 2 things ( a key and a value object). This makes it hard for the add method in the Collection interface to make any sense because it only has one parameter. Consequently Java created an independent Map interface that happens to have a lot of methods that are the same as in a Collection interface, but there are fundamental differences.
2. put method - this method defines a key and a value object. The put method is the replacement for the add method in the Collection class.
3. Note that instead of one "contains" method there are 2 ---- one for the key and one for the value.
4. Iterators - You can't directly create an Iterator. However, you can indirectly create an Iterator using the "keySet" and "values" methods. For example to create an iteration of the values, you first create a Collection from the Map using the "values" method. Then you call the iterator method in the Collection interface and this allows you to iterate through the values in your Map. A similar approach works for iterating through the keys using the keySet method. See the example below.
5. The HashMap class is an implementation of the Map interface.
6. Keys may not be duplicated, but the Value objects can be duplicated. The HashMap class actually allows one key to be null.
7. The Hashtable class is an older version of the HashMap class, just like the Vector class is an older version of the ArrayList. The Hashtable class is synchronized, while the HashMap class is unsynchronized. I would recommend that you use HashMap whenever you can.

interface Map

Proto-Type | Description
void clear() | Removes all mappings from this map (optional operation).
boolean containsKey(Object key) | Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value) | Returns true if this map maps one or more keys to the specified value.
Set entrySet() | Returns a set view of the mappings contained in this map.
Object get(Object key) | Returns the value to which this map maps the specified key.
boolean isEmpty() | Returns true if this map contains no key-value mappings.
Set keySet() | Returns a set view of the keys contained in this map.
Object put(Object key, Object value) | Associates the specified value with the specified key in this map (optional operation).
void putAll(Map t) | Copies all of the mappings from the specified map to this map (optional operation).
Object remove(Object key) | Removes the mapping for this key from this map if present (optional operation).
int size() | Returns the number of key-value mappings in this map.
Collection values() | Returns a collection view of the values contained in this map.

Dog class revisited with a HashMap collection class


import java.util.*;

class Dog {
   String name;
Dog(String n) {
      name = n;
   }
public String toString() {
   return "Dog:"+name ;
   }
void print ()
    {
        System.out.println("print: " + toString());
    }

public boolean equals(Object obj)
    {
        boolean retval = false;
        if (obj instanceof Dog)
        {
            Dog d = (Dog)obj;
            if (name.equals(d.name))
                return true;
        }
        return false;
    }
} // end of class Dog
// -----------------------------------------------

public class Dogs {
public static void main(String[] args) {
      HashMap dogs = new HashMap();
      Dog d;
      Object ob;

      dogs.put("Tiger",  new Dog("Tiger") );
      dogs.put("Fido",   new Dog("Fido")  );
      dogs.put("Maya",   new Dog("Maya")  );
      dogs.put("Benji",  new Dog("Benji") );

      // Looking up objects by Value
      // After trying this once, uncomment the equals method in Dog
      // recompile and rerun and see the difference.
      d = new Dog("Fido");
      if (dogs.containsValue(d))
        {
        // This works because we implemented "equals" on the Dog class
          System.out.println(" We already have a " + d);
          // Can't add another object with the same key
        }

      // Looking up objects by Key
      if (dogs.containsKey("Fido"))
      {
        System.out.println(" We found an object: " + dogs.get("Fido"));
      }

      // Normal way to use a HashMap for lookup --
      // the get method is the preferred way to access objects stored in
      //     HashMap because of its efficiency.

      d = (Dog)dogs.get("Tiger");
      if (d != null)
        System.out.println("Tiger object: " + d);


      d = (Dog)dogs.get("Fido");
      if (d != null)
        System.out.println("Fido object: " + d);


      System.out.println("***** Looking at the whole collection of dogs ****");
      Set s = dogs.keySet();
      Iterator iter = s.iterator();

      while(iter.hasNext())
      {
      // Notice the Caste which is required to call print
          String key = (String)iter.next();
          d = (Dog)dogs.get(key);
          d.print();
      }


  }

}


The following example will only work if you first create the following file:

stateCaps.txt

TryMap.java


import tools.*;
import java.util.*;

class Capitol
{
   int population;
   String name;
   Capitol(String n, int p)
   {
      name = n;
      population = p;
   }
   public String toString()
   {
        return name + ":" +population;
   }
   // needed to make containsValue work properly
   public boolean equals(Object obj)
    {
        boolean retval = false;
        if (obj instanceof Capitol)
        {
            Capitol c = (Capitol)obj;
            if (name.equals(c.name))
                return true;
        }
        return false;
    }

}

public class TryMap
{
// If you change HashMap to TreeMap, your States will be sorted
    Map store = new HashMap();
    void load()
    {
        String str, cap, state, cpop;
        int cpop_val;
        Capitol capitol_class;
        MyInput in = new MyInput("stateCaps.txt");
        do
        {
            str = in.get();
            if (str != null)
            {
                str = str.trim();
                if (str.length() == 0) break;
                StringTokenizer tok = new StringTokenizer(str, ";\r\n");
                cap = (String)tok.nextElement();
                state = (String)tok.nextElement();
                cpop = (String)tok.nextElement();
                cap = cap.trim();
                state = state.trim();
                cpop_val = Integer.parseInt(cpop.trim());

                capitol_class = new Capitol(cap, cpop_val);

                store.put(state, capitol_class);
            }

        }while (str != null);
        // Execute toString method on HashMap
        System.out.println(store);
    }
    void doCmd(MyInput input, String str)
    {
      if (str.equals("containsKey"))
        {
           System.out.println("enter key");
           str = input.get();
           str = str.trim();
           System.out.println("containsKey = " +
                store.containsKey( str));
        }
      else if (str.equals("containsValue"))
        {
           System.out.println("enter value");
           str = input.get();
           str = str.trim();
           Capitol c = new Capitol(str, 0);
           System.out.println("containsValue = " +
                store.containsValue( c));
        }
      else if (str.equals("keyIter"))
            {
               Set s = store.keySet();
               Iterator iter = s.iterator();
               while (iter.hasNext())
                    System.out.println(iter.next());
            }
      else if (str.equals("valueIter"))
            {
               Collection coll = store.values();
               Iterator iter = coll.iterator();
               while (iter.hasNext())
                    System.out.println(iter.next());
            }

      else if (str.equals("get"))
            {
                System.out.println("enter key");
                str = input.get();
                str = str.trim();
                System.out.println("Value = " +
                    store.get(str));
            }

      else if (str.equals("toString"))
                System.out.println(store);
      else if (str.equals("size"))
            {
                System.out.println("size ="+ store.size());
            }
      else System.out.println("Illegal command");
    }
    public static void main(String[] args)
    {
        TryMap doit = new TryMap();
        String str;
        MyInput input = new MyInput();

        doit.load();
        do
        {
            System.out.println(" **********************************");
            System.out.println("ENTER:  toString, get, valueIter, keyIter");
            System.out.println("containsKey, containsValue size");
            System.out.println(" -----------------------");
            str = input.get();
            str = str.trim();

            doit.doCmd(input, str);
        } while (str != null);
    }
}



Analyze the following HashMap program and describe what is going on. In some sense we are anaylyzing how good our Random number generator is.

Statistics.java


// Simple demonstration of HashMap
import java.util.*;

class Counter {
   int count =1;
  public String toString() {
   return Integer.toString(count);
   }
}
// ----------------------

class Statistics {
public static void main(String[] args) {
      HashMap ht = new HashMap();
      Counter c;
      for(int i =0;i <50000; i++)
      {
         // Produce a number between 0 and 50:
         Integer r = new Integer((int)(Math.random() * 50));
         if(ht.containsKey(r))
         {
             c = (Counter)ht.get(r);
             c.count++;
         }
         else
         {
             c = new Counter();
             ht.put(r, c);
         }
      }
      System.out.println(ht);

      Collection collectView = ht.values();
      Iterator e = collectView.iterator();

      while(e.hasNext())
          System.out.println("Counter = "+ e.next());

   }// end of main
}


Creating a Key from your own class

So far our key has been a String. Strings are easy, because they already have implementations for all of the important interfaces (equals, toString, compareTo, and hashCode). You will note from the Map interface that a key can be any class. However, it takes some work. A class can only be a Key in a Map interface if the class has implementations of the following 2 methods:

1. equals - this shouldn't be any surprise
2. hashCode - You have to provide a method that generates a hashing number out of your object. If 2 of your classes are considered equivalent, then they should generate the same hashcode. It is OK to have 2 different classes generate the same hashCode.
3. In the following example, the State class contains more information than just the name of the state. Note that I am considering 2 State classes the same if they have the same name.
4. See what happens if you get rid of the hashCode interface. Note that it actually compiles, but doesn't work properly. Where do you think the default hashCode method lives?

TryMap2.java


import tools.*;
import java.util.*;
class State
{
    int population;
    String name;
    State (String n, int p)
    {
        name = n;
        population = p;
    }
    // Good to implement -- convenience for output
    public String toString()
    {
        return name + ":" + population + ":" ;
    }
    // Need to implement hashCode if you are going
    // to use this class as a KEY
    public int hashCode()
    {
        return name.hashCode();
    }
    // There are a number or reasons for implementing
    // this method.  Any containsXXX require it.  Using
    // this class as a key requires it.
    public boolean equals(Object obj)
    {
        boolean retval = false;
        if (obj instanceof State)
        {
            State s = (State)obj;
            if (name.equals(s.name))
                return true;
        }
        return false;
    }
}
class Capitol
{
   int population;
   String name;
   Capitol(String n, int p)
   {
      name = n;
      population = p;
   }
   public String toString()
   {
        return name + ":" +population;
   }
   public boolean equals(Object obj)
    {
        boolean retval = false;
        if (obj instanceof Capitol)
        {
            Capitol c = (Capitol)obj;
            if (name.equals(c.name))
                return true;
        }
        return false;
    }

}
public class TryMap2
{
// If you change HashMap to TreeMap, your States will be sorted
    Map store = new HashMap();
    void load()
    {
        String str, cap, state, spop, cpop;
        int spop_val, cpop_val;
        State state_class;
        Capitol capitol_class;
        MyInput in = new MyInput("stateCaps.txt");
        do
        {
            str = in.get();
            if (str != null)
            {
                str = str.trim();
                if (str.length() == 0) break;
                StringTokenizer tok = new StringTokenizer(str, ";\r\n");
                cap = (String)tok.nextElement();
                state = (String)tok.nextElement();
                cpop = (String)tok.nextElement();
                spop = (String)tok.nextElement();
                cap = cap.trim();
                state = state.trim();
                spop_val = Integer.parseInt(spop.trim());
                cpop_val = Integer.parseInt(cpop.trim());

                state_class = new State(state, spop_val);
                capitol_class = new Capitol(cap, cpop_val);

                store.put(state_class, capitol_class);
            }

        }while (str != null);
        // Execute toString method on HashMap
        System.out.println(store);
    }
    void doCmd(MyInput input, String str)
    {
      if (str.equals("containsKey"))
        {
           System.out.println("enter key");
           str = input.get();
           str = str.trim();
           State s = new State(str, 0);
           System.out.println("containsKey = " +
                store.containsKey( s));
        }
      else if (str.equals("containsValue"))
        {
           System.out.println("enter value");
           str = input.get();
           str = str.trim();
           Capitol c = new Capitol(str, 0);
           System.out.println("containsValue = " +
                store.containsValue( c));
        }
      else if (str.equals("keyIter"))
            {
               Set s = store.keySet();
               Iterator iter = s.iterator();
               while (iter.hasNext())
                    System.out.println(iter.next());
            }
      else if (str.equals("valueIter"))
            {
               Collection coll = store.values();
               Iterator iter = coll.iterator();
               while (iter.hasNext())
                    System.out.println(iter.next());
            }

      else if (str.equals("get"))
            {
                System.out.println("enter key");
                str = input.get();
                str = str.trim();
                State s = new State(str, 0);
                System.out.println("Value = " +
                    store.get(s));
            }

      else if (str.equals("toString"))
                System.out.println(store);
      else if (str.equals("size"))
            {
                System.out.println("size ="+ store.size());
            }
      else System.out.println("Illegal command");
    }
    public static void main(String[] args)
    {
        TryMap2 doit = new TryMap2();
        String str;
        MyInput input = new MyInput();

        doit.load();
        do
        {
            System.out.println(" **********************************");
            System.out.println("ENTER:  toString, get, valueIter, keyIter");
            System.out.println("containsKey, containsValue size");
            System.out.println(" -----------------------");
            str = input.get();
            str = str.trim();

            doit.doCmd(input, str);
        } while (str != null);
    }
}



SortedMap interface

1. You can change the TryMap.java program to use the TreeMap class instead of the HashMap class.
2. You can also change the Statistics.java program to use the TreeMap class ---- Why?
3. If you try to change the HashMap class to a TreeMap class in TryMap2.java, you will encounter a problem. You will need to implement the Comparable interface in the State class. Otherwise, its hard for the TreeMap class to know how to compare states.

Make the changes to TryMap2.java to make it work with TreeMap.

From the interface additions shown below, you can create the same program that we created in the SortedSet section where we are able to create subsets of the SortedMap taken from the head, tail or the middle.

interface SortedMap extends Map

Proto-Type | Description
Object firstKey() | Returns the first (lowest) key currently in this sorted map.
SortedMap headMap(Object toKey) | Returns a view of the portion of this sorted map whose keys are strictly less than toKey.
Object lastKey() | Returns the last (highest) key currently in this sorted map.
SortedMap subMap(Object fromKey, Object toKey) | Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to toKey, exclusive.
SortedMap tailMap(Object fromKey) | Returns a view of the portion of this sorted map whose keys are greater than or equal to fromKey.

Exercises:

1. Make the changes to TryMap2.java to allow it to be implemented with a TreeMap class.
2. Create a program similar to the program created in the SortedSet section that demonstrates the above methods (i.e. firstKey, headMap, lastKey, subMap, and tailMap) with a TreeMap class.
3. Recreate the StudentRecord, ClassList problem where you use a HashMap instead of a LinkedList. Use the student's name as a hash key.
4. Create a SortedMap of your friends. The information you need to store on your friends is lastname, firstname, phone#, birthdate, hobby. Have the sort of your friends be by
lastname firstname
Create a Friend class that has all of the information for each friend. The toString routine will output "LastName FirstName". Your friend class should have a method called print, which prints out all of the information for your friend. Your program should read in one file that contains all of the friend information. Then your program should take commands like :

get Flintstone Fred

This command will print out all information about Fred Flintstone.

Also add the command:
getall Flintstone
How could we print out all of the records associated with the name Flintstone? HINT: we could use a subMap and pass in "Flintstone" as the first key, and something else as the last key. Then something else must be alphabetically after the last Flintstone. One choice is "Flintstone~". Note that ~ is alphabetically after anything that could be part of a name.

Here is some sample input:
Hasselbach Clem (111)111-1111 4/20/1948 hobby: raising kids
Flintstone Fred (333)222-5678 8/9/-5020 hobby: rock bowling
Crockett Davey (777)777-7777 8/9/1832 hobby: Shootin Bear
Hasselbach Sue (111)111-1111 11/3/1953 hobby: keeping dogs out of trouble
Flintstone Wilma (333)222-5678 7/7/-5016 hobby: bashing Fred
Hasselbach Sam (111)111-1111 7/3/1987 hobby: messing with his friends
Rubble Beaty (333)444-5555 2/2/-5016 hobby: gabbing with Wilma
Flintstone Pebbles (333)222-5678 1/1/-4995 hobby: playing with dynodogs
Hasselbach Marta (111)111-1111 5/13/1984 hobby: soccer
Hasselbach Sarah (123)122-1222 9/22/1980 hobby: guys
Rubble Barney (333)444-5555 6/6/-5020 hobby: rock car racing
Hasselbach Maria (124)133-4444 11/14/1978 hobby: Spanish
5. Create a simple class called Marriage which keeps track of husband/wife pairs. Using the Marriage class update some of the above java programs to store Collections of Marriages.
Update TryMap.java
6. Create 500,000 Random 2 character strings. If the 2 character string has been created already, then increment a count associated with this string. Print out a count of the number times each 2 character string was created.
7. Store a Marriage class in a HashMap datastructure where the Marriage can be found from one of 3 keys (spouse1 name, spouse2 name, and combined Marriage names). Modify TryMap.java to demonstrate the functionality.
8. Rerun the previous example using a TreeMap instead of HashMap ---- what changes?.

Last Updated: October 29, 2003 12:58 PM