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 a lot of the information on a student at 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.

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<K,V>

Proto-Type | Description
void clear() | Removes all mappings from this map (optional operation).
boolean containsKey(K key) | Returns true if this map contains a mapping for the specified key.
boolean containsValue(V value) | Returns true if this map maps one or more keys to the specified value.
Set<Map.Entry<K,V> > entrySet() | Returns a set view of the mappings contained in this map.
V get(K 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<K> keySet() | Returns a set view of the keys contained in this map.
Object put(K key, V value) | Associates the specified value with the specified key in this map (optional operation).
void putAll(Map<K,V> ) | Copies all of the mappings from the specified map to this map (optional operation).
Object remove(K 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<V> values() | Returns a collection view of the values contained in this map.

Dog class revisited using a Map based data structure


import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

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

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

public class Dogs {
public static void main(String[] args) {
      Map<String, Dog>  dogs = new LinkedHashMap<String, Dog>();
     // Map<String, Dog>  dogs = new HashMap<String, Dog>();
     // Map<String, Dog>  dogs = new TreeMap<String, Dog>();
      Dog d;

      // Note that one object can have more than one key
      d = new Dog("Addy", 50.0);
      dogs.put("Addy", d);
      dogs.put("neighborDog", d);

      dogs.put("Tiger",  new Dog("Tiger", 10.0) );
      dogs.put("Tiger1",  new Dog("Tiger", 20.0) );
      dogs.put("Tiger2",  new Dog("Tiger", 30.0) );
      dogs.put("Fido",   new Dog("Fido", 20.0)  );
      dogs.put("Fido1",   new Dog("Fido", 10.0)  );
      dogs.put("Fido2",   new Dog("Fido", 30.0)  );
      dogs.put("Maya",   new Dog("Maya", 25.0)  );
      dogs.put("Zorn",   new Dog("Zorn", 25.0)  );
      dogs.put("Benji",  new Dog("Benji", 66.0) );
      dogs.put("Spot",  new Dog("Spot", 16.0) );
      dogs.put("Garfunkel",  new Dog("Garfunkel", 36.0) );
      dogs.put("Oscar",  new Dog("Oscar", 34.0) );
      dogs.put("Beefy",  new Dog("Beefy", 134.0) );
      dogs.put("Abe",  new Dog("Abe", 21.0) );
      dogs.put("Trixy",  new Dog("Trixy", 21.0) );
      dogs.put("Fred",  new Dog("Fred", 45.0) );
      dogs.put("Zed",  new Dog("Zed", 32.0) );
      dogs.put("Foxy",  new Dog("Foxy", 32.0) );
      dogs.put("Bob",  new Dog("Bob", 31.0) );
      dogs.put("BigRed",  new Dog("BigRed", 98.0) );
      dogs.put("Rover",  new Dog("Rover", 44.0) );
      dogs.put("Pooch",  new Dog("Pooch", 24.0) );
      dogs.put("Socrates",  new Dog("Socrates", 15.0) );
      dogs.put("Pudge",  new Dog("Pudge", 112.0) );

      // 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", 20.0);
      if (dogs.containsValue(d))
        {
        // This works because we implemented "equals" on the Dog class
          System.out.println(" containsValue(Dog(Fido,20.0): true : " + d);

        }

      // Looking up objects by Key
      if (dogs.containsKey("Fido"))
      {
        // Can't add another object with the same key
         System.out.println(" containsKey(Fido) true: " + 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 = dogs.get("Tiger");
      System.out.println("Tiger object: " + d);


      System.out.println("***** Iterating by Keys ****");
      Set<String> s = dogs.keySet();
      Iterator<String> iter = s.iterator();

      while(iter.hasNext())
      {
          String key = iter.next();
          d = dogs.get(key);
          System.out.println("key="+ key + " dog=" + d.toString());
      }

      System.out.println("***** Iterating by Values ****");
      Collection<Dog> collection = dogs.values();
      Iterator<Dog> iterValue = collection.iterator();

      while(iterValue.hasNext())
      {
          d = iterValue.next();
          d.print();
      }

      System.out.println("***** Iterating by Mappings ****");
      Set<Map.Entry<String,Dog> >  mappings = dogs.entrySet();
      Iterator<Map.Entry<String,Dog> > iterMapping = mappings.iterator();

      while(iterMapping.hasNext())
      {
          Map.Entry<String, Dog> entry = iterMapping.next();
          System.out.println("key="+ entry.getKey() + " value="+entry.getValue());
      }

  }
}



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


import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

class Stats {
    int count =1;
    int loopIndex;
    Stats(int loopIndex)
    {
        this.loopIndex = loopIndex;
    }
    public String toString() {
        return  " count="+count + " loop index="+ loopIndex;
    }
}
//----------------------

class Statistics {
    public static void main(String[] args) {
        Map<Integer, Stats> map = new LinkedHashMap<Integer, Stats>();
        //Map<Integer, Counter> map = new HashMap<Integer, Counter>();
        //Map<Integer, Counter> map = new TreeMap<Integer, Counter>();
        Stats stats;
        for(int loopIndex =0;loopIndex <50000; loopIndex++)
        {
            // Produce a number between 0 and 50:
            Integer r = new Integer((int)(Math.random() * 50));
            stats = map.get(r);
            if(stats != null)
            {
                stats.count++;
            }
            else
            {
                stats = new Stats(loopIndex);
                map.put(r, stats);
            }
        }

        Set<Integer> keys = map.keySet();
        Iterator<Integer> iter = keys.iterator();

        while(iter.hasNext())
        {
            Integer key = iter.next();
            System.out.println("key="+ key + " value="+ map.get(key));
        }


    }// end of main
}





A more complicated Key and Value for HashMap

Consider the following example: you will need the following file at the top level of your project: student_records.txt

We will have a class called Student that will be our key in our HashMap.

Our Value record will be a Record class associated with this Student.

Run the following and see what it generates for output.

Uncomment the hashCode() method and the equals method in the Student class and run it again and see the different results. What is going on here?


import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;

class Student   // Used for Key to HashMap
{
    String firstName;
    String lastName;
    int birthMonth, birthDay, birthYear;

    Student(String f, String l, int m, int d, int y)
    {
        firstName = f;
        lastName = l;
        birthMonth = m;
        birthDay = d;
        birthYear =y;
    }
    public String toString()
    {
        return firstName+" "+ lastName + " "+ birthMonth+" "+ birthDay+" "+ birthYear;
    }
    int MyStringHashCode(String s)
    {
        int h = 1;
        for (int i=0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            if (c != 0)
                h *= c;
        }
        return h;
    }

    /*
    public int hashCode()
    {
// Note the alternative for computing hashCode for a String.
        //int h = firstName.hashCode() * lastName.hashCode();
        int h = MyStringHashCode(firstName) * MyStringHashCode(lastName);
        if (birthMonth != 0)
            h *= birthMonth;
        if (birthDay != 0)
            h *= birthDay;
        if (birthYear != 0)
            h *= birthYear;
        return h;
    }




    public boolean equals(Object obj)
    {
        Student s= (Student)obj;
        if (firstName.equals(s.firstName) &&
            lastName.equals(s.lastName) &&
            birthMonth == s.birthMonth &&
            birthDay == s.birthDay &&
            birthYear == s.birthYear)
            return true;
        else
            return false;
    }
    */
}


class Record  // Used for the Value in the HashMap
{
    String major;
    double gpa;
    ArrayList<CourseGrade> listOfCourses = new ArrayList<CourseGrade>();

    Record(String major)
    {
        this.major = major;
    }

    public String toString()
    {
        return major + " " + String.format("gpa=%.2f", gpa)+ " courses="+listOfCourses;
    }

    void addCourse(String courseName, double grade, int credits)
    {
        listOfCourses.add(new CourseGrade(courseName, grade,credits));
        double totalGrade=0;
        int totalCredits =0;
        for (int i=0; i < listOfCourses.size(); i++)
        {
            CourseGrade cg = listOfCourses.get(i);
            totalGrade += cg.grade*cg.credits;
            totalCredits += cg.credits;
        }
        gpa = totalGrade/totalCredits;
    }
    // ********************  Inner class
    class CourseGrade
    {
        String courseName;
        double grade;
        int credits;

        CourseGrade(String courseName, double grade, int credits)
        {
            this.courseName =courseName;
            this.grade =grade;
            this.credits = credits;
        }
        public String toString()
        {
            return courseName +" grade="+grade +" credits="+credits;
        }
    }
    // *******************  End of Inner class

} // End of Record class


public class StudentRecords {
    HashMap<Student, Record> records = new HashMap<Student, Record>();

    void process()
    {
         if (!addRecords("student_records.txt"))
         {
             System.out.println("Exitting due to error in student_records.txt");
             return;
         }

         Student student1 = new Student("Frank", "Thomas", 4, 20, 1990);
         if (records.containsKey(student1))
             System.out.println("Student Found");
         else
         {
             System.out.println("Student NOT Found: "+ student1);
             records.put(student1, new Record("Math"));
         }

         Set<Student> keys = records.keySet();
         Iterator<Student> iter = keys.iterator();
         while(iter.hasNext())
         {
             Student s = iter.next();
             Record r = records.get(s);
             System.out.println("Student="+ s);
             System.out.println("Record="+r);
         }
    }


    boolean addRecords(String filename)
    {
        Scanner input ;
        try {
            FileInputStream fi = new FileInputStream(filename);
            input = new Scanner(fi);
        } catch (FileNotFoundException e) {
            System.out.println("addRecords error:" + e);
            return false;
        }
        Student student=null;
        Record record=null;
        while (input.hasNextLine())
        {
            String line = input.nextLine();
            StringTokenizer parse = new StringTokenizer(line);
            int count = parse.countTokens();
            switch(count)
            {
            case 3:
                if (record == null)
                {
                    System.out.println("No record class for: "+ line);
                    return false;
                }
                String subject = parse.nextToken();
                double grade = Double.parseDouble(parse.nextToken());
                int numCredits = Integer.parseInt(parse.nextToken());
                record.addCourse(subject, grade, numCredits);
                break;
            case 6:
                if (student != null)
                {
                    records.put(student, record);
                }
                String firstName = parse.nextToken();
                String lastName = parse.nextToken();
                int month = Integer.parseInt(parse.nextToken());
                int day = Integer.parseInt(parse.nextToken());
                int year = Integer.parseInt(parse.nextToken());
                String major = parse.nextToken();
                student = new Student(firstName, lastName, month, day, year);
                record = new Record(major);
                break;
            default:
                System.out.println("Bad line: " + line);
                return false;
            }
            if (student != null)
                records.put(student, record);

        }


        input.close();
        return true;
    }

    public static void main(String[] args)
    {
        StudentRecords sr = new StudentRecords();
        sr.process();

    }

}



SortedMap interface

1. You can change the Dogs.java program to use the TreeMap class instead of the HashMap class.
2. If you try to change the HashMap class to a TreeMap class in StudentRecords.java, you will encounter a problem. You will need to implement the Comparable interface in the Student class. Otherwise, its hard for the TreeMap class to know how to compare students.

interface SortedMap<K,V> extends Map<K,V>

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

After changing the Dogs.java class use a TreeMap to implement a SortedMap.

First change the declaration of dogs to:

SortedMap<String, Dog> dogs = new TreeMap<String, Dog>();

Add the following to the end of the main in Dogs:



      System.out.println(" firstKey="+ dogs.firstKey());
      System.out.println(" lastKey="+ dogs.lastKey());

      System.out.println("****** sortedMap subsets *******");
   //   SortedMap<String, Dog> sortedMap = dogs.headMap("BigRed");
      //SortedMap<String, Dog> sortedMap = dogs.tailMap("Socrates");
      SortedMap<String, Dog> sortedMap = dogs.subMap("BigRed", "Socrates");

      Set<String>sortedSet = sortedMap.keySet();
      Iterator<String> siter = sortedSet.iterator();
      while (siter.hasNext())
      {
          System.out.println(siter.next());
      }


Alternate Exercises:

These are not assigned to you. I keep the following as a list of ideas for future work in this area.

1. See if you can create a MyHashMap class from scratch that has some of the fundamentals in HashMap.
2. See if you can create a MyTreeMap class from scratch that has some of the fundamentals to TreeMap.
3. 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
4. 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.
5. 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.
6. 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).
7. Rerun the previous example using a TreeMap instead of HashMap ---- what changes?.

Last Updated: November 11, 2013 0:50 AM