The Collections Framework

So, we’ve learned about abstract classes and interfaces, right?

In reality, we’ll need some examples and some practice to see how they are typically used, before we can be comfortable using them in our own code.

There are many good examples of the use of abstract classes and interfaces in the Java class libraries.  One particularly useful example is how they are used to implement the Java Collections Framework.

A collection is a “container” for a group of elements or items.  It provides operations to allow manipulation of those elements.

The Java Collections Framework is represented by the following set of classes and interfaces (the tree structure represents the inheritance hierarchy):

Package java.util:

Interfaces:

Collection
    List
    Set
        SortedSet
Comparable (in package java.lang)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

Classes:

Object
    AbstractCollection (implements Collection)
        AbstractList (implements List)
            AbstractSequentialList
                LinkedList
            ArrayList
            Vector
                Stack
        AbstractSet (implements Set)
            HashSet
            TreeSet (implements SortedSet)
    AbstractMap (implements Map)
        HashMap
        TreeMap (implements SortedMap)
        WeakHashMap
    Dictionary
        Hashtable (implements Map)
            Properties

There’s clearly lots to talk about!

What is a Collections Framework?

A Collections Framework is a unified architecture for representing and manipulating collections.  All collections frameworks include:

• Interfaces: abstract data types representing collections.
• Implementations: concrete implementations of the collection interfaces.
• Algorithms: methods that perform useful computations (such as sorting and searching) on objects that implement collection interfaces.

The benefits of a Collections Framework are:

• Reduces programming effort
• Increases program speed and quality
• Allows interoperability among unrelated APIs
• Reduces effort to learn and use new APIs
• Reduces effort to design new APIs
• Fosters software reuse

Vector & Enumeration

The Vector class and the Enumeration interface have been part of Java since its very first version.  They are heavily used in lots of Java code.

However, they represent an “old style” which has been replaced with a new set of classes and interfaces that were introduced in Java version 1.2.  They still exist in the Java class library, but are deprecated in favor of the “new style”.

Vector Class

Vector is a class that implements a kind of dynamic array.  

Object
    Dictionary (abstract)
        Hashtable
            Properties
    Vector
        Stack

You can add instances of any class to it, using methods:

• add(…)
• addElement(…)
• etc…

and then retrieve them using a number of methods:

• elementAt()
• firstElement()
• lastElement()
• toArray()
• etc.

You can remove elements from the Vector :

• remove()
• removeElementAt()
• removeAll()
• removeRange()
• etc.

and you can replace an element with another element:

• set()
• setElementAt()

You can also obtain the elements stored in a Vector by using an Enumeration, returned from the Vector by calling the method:

• elements()

Note that Vector is being replaced by ArrayList.  (see later).

Enumeration Interface

Enumeration is an interface which allows you to enumerate through a collection of items:

Enumeration

package java.util;

/* Comments omitted */
public interface Enumeration 
{
    /**
     * Tests if this enumeration contains more elements.
     *
     * @return  <code>true</code> if this enumeration contains more elements;
     *          <code>false</code> otherwise.
     * @since   JDK1.0
     */
    boolean hasMoreElements();

    /**
     * Returns the next element of this enumeration.
     *
     * @return     the next element of this enumeration. 
     * @exception  NoSuchElementException  if no more elements exist.
     * @since      JDK1.0
     */
    Object nextElement();
}

Vector‘s elements() method returns an instance of a class that implements the Enumeration interface.

Note that Enumeration is being replaced by Iterator.  (see later).

Vector/Enumeration Example

Here’s an example of how one could use an instance of class Vector, and the interface Enumeration.  

This code will run under all versions of the Java SDK.

package examples;
import java.util.Enumeration;
import java.util.Vector;
public class VectorExample
{
  public static void main(String[] args)
  {
    Vector vector = new Vector();
    vector.add("Mary");
    vector.add("Frank");
    vector.add("Joe");
    vector.add("Sylvia");
    vector.add("Vanessa");
    for (int i = 0; i < vector.size(); i++)
    {
      String name = (String) vector.elementAt(i); // Note required cast
      System.out.println(i + ": " + name);
    }
    for (Enumeration en = vector.elements(); en.hasMoreElements(); )
    {
      String name = (String) en.nextElement(); // Note required cast
      System.out.println(name);
    }
  }
}

which outputs the following:

0: Mary
1: Frank
2: Joe
3: Sylvia
4: Vanessa
Mary
Frank
Joe
Sylvia
Vanessa

Note the two ways of obtaining the elements of the vector:

• Access each element by its index, using the elementAt(int index) method
• Access each element through an Enumeration object, supplied by the Vector. (Remember, Enumeration is an interface.)

This works, but is considered “old style”.   So what’s the “new style”?   

To learn about that, you’ll have to learn some more background…

Collections Interfaces

There are a number of collections framework interfaces used to manipulate collections and pass them from one method to another.

Collection: Defines properties that all collections must have.  For example, it defines a size() method to return the number of elements currently in the collection.

List: Extends Collection, and adds additional properties that define ordered lists.  For example, the ability to retrieve an element based on an index.  (A list is sometimes called a sequence.)  A List can contain duplicate elements.

Set: Extends Collection, and adds additional properties that define a set.  A set cannot contain duplicate elements.

SortedSet: Extends Set, and adds support for ordering the set in a particular sequence.

Map: Defines properties that map keys to values.  A Map cannot contain duplicate keys. (Note that a Map does not extend Collection, and so is not a true collection.)

SortedMap: Extends Map, and adds properties that support ordering of the map in ascending key order.

Iterator: Defines the properties necessary to iterate through a Collection.

ListIterator: Extends Iterator, and defines the properties necessary to iterate through a List.

The Collection Interface

The Collection interface (not to be confused with the Collections class — see later) defines the top-level methods for all collection objects (that is, all objects that implement the Collection interface).  

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

It defines the following methods (this is the original source, minus many comments):

package java.util;

public interface Collection 
{
    // Query Operations

    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator iterator();
    Object[] toArray();
    Object[] toArray(Object a[]);

    // Modification Operations

    boolean add(Object o);
    boolean remove(Object o);

    // Bulk Operations

    boolean containsAll(Collection c);
    boolean addAll(Collection c);
    boolean removeAll(Collection c);
    boolean retainAll(Collection c);
    void clear();

    // Comparison and hashing

    boolean equals(Object o);
    int hashCode();
}

Note that the Collection interface itself does not enforce any policy, such as no duplicates or ordering.  Such policies are enforced by sub-interfaces of the Collection interface.

The List Interface

The java.util.List interface (not to be confused with the java.awt.List class, which represents an AWT GUI component):

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

The List interface defines additional methods which support the concept of ordering within the collection:

package java.util;

public interface List extends Collection 
{
    // Modification Operations
    boolean addAll(int index, Collection c);

    // Positional Access Operations

    Object get(int index);
    Object set(int index, Object element);
    void add(int index, Object element);
    Object remove(int index);

    // Search Operations

    int indexOf(Object o);
    int lastIndexOf(Object o);

    // List Iterators

    ListIterator listIterator();
    ListIterator listIterator(int index);

    // View

    List subList(int fromIndex, int toIndex);
}

A List defines methods which are analogous to what class Vector defined in JDK 1.1.  

In JDK 1.2 and beyond, Vector extends the class AbstractList, which makes Vector a kind of List.

Object
    AbstractCollection (implements Collection)
        AbstractList (implements List)
            AbstractSequentialList
                LinkedList
            ArrayList
            Vector
                Stack
        AbstractSet (implements Set)
            HashSet
            TreeSet (implements SortedSet)
    AbstractMap (implements Map)
        HashMap
        TreeMap (implements SortedMap)
        WeakHashMap
    Dictionary
        Hashtable (implements Map)
            Properties

The Iterator Interface

The Iterator interface is designed to provide the interface for a class that can iterate through a collection.  It is designed to replace the Enumeration interface

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

The Iterator interface defines the following methods:

package java.util;

public interface Iterator 
{
    /**
     * Returns true if the iteration has more elements. (In other
     * words, returns true if next would return an element
     * rather than throwing an exception.)
     *
     * @return true if the iterator has more elements.
     */
    boolean hasNext();

    /**
     * Returns the next element in the iteration.
     *
     * @returns the next element in the iteration.
     * @exception NoSuchElementException iteration has no more elements.
     */
    Object next();

    /**
     * 
     * Removes from the underlying collection the last element returned by the
     * iterator (optional operation).  This method can be called only once per
     * call to next.  The behavior of an iterator is unspecified if
     * the underlying collection is modified while the iteration is in
     * progress in any way other than by calling this method.
     *
     * @exception UnsupportedOperationException if the remove
     *		  operation is not supported by this Iterator.
     
     * @exception IllegalStateException if the next method has not
     *		  yet been called, or the remove method has already
     *		  been called after the last call to the next
     *		  method.
     */
    void remove();
}

Note that it is reminiscent of Enumeration, but with two differences:

• Method names have changed:
  • hasMoreElements() becomes hasNext()
  • nextElement() becomes next()
• Iterator allows the caller to remove elements from an underlying collection during the iteration, with well-defined semantics.  (Enumeration does not support this.)

The ListIterator Interface

The ListIterator interface defines the additional methods necessary to support iteration though a List.  

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

It adds the ability to traverse the list in either direction, and to modify the list during iteration:

package java.util;

public interface ListIterator extends Iterator 
{
    // Query Operations

    boolean hasPrevious();
    Object previous();
    int nextIndex();
    int previousIndex();


    // Modification Operations
    
    void set(Object o);
    void add(Object o);
}

ArrayList/Iterator Example

An ordered collection is called a List.  A concrete implementation of a List is ArrayList:

Object
    AbstractCollection (implements Collection)
        AbstractList (implements List)
            AbstractSequentialList
                LinkedList
            ArrayList
            Vector
                Stack
        AbstractSet (implements Set)
            HashSet
            TreeSet (implements SortedSet)
    AbstractMap (implements Map)
        HashMap
        TreeMap (implements SortedMap)
        WeakHashMap
    Dictionary
        Hashtable (implements Map)
            Properties

ArrayList implements the List as a resizeable array, but that is just one possible implementation of a List.  There are others.

Here’s an example of how one could use an instance of class ArrayList.  It will run only under JDK 1.2 and beyond:

package examples;
import java.util.ArrayList;
import java.util.Iterator;
public class ArrayListExample
{
  public static void main(String[] args)
  {
    ArrayList list = new ArrayList();
    list.add("Mary");
    list.add("Frank");
    list.add("Joe");
    list.add("Sylvia");
    list.add("Vanessa");
    for (int i = 0; i < list.size(); i++)
    {
      String name = (String) list.get(i); // Note required cast
      System.out.println(i + ": " + name);
    }
    for (Iterator iter = list.iterator(); iter.hasNext(); )
    {
      String name = (String) iter.next(); // Note required cast
      System.out.println(name);
    }
  }
}

which produces the output:

0: Mary
1: Frank
2: Joe
3: Sylvia
4: Vanessa
Mary
Frank
Joe
Sylvia
Vanessa

The output is exactly the same as for the earlier Vector/Enumeration example.

Again, note the two ways of obtaining the elements of the list:

• Access each element by its index, using the get(int index) method
• Access each element through an Iterator object, supplied by the ArrayList. (Remember, Iterator is an interface.)

This is the “new style”.

LinkedList Example

Another concrete implementation of a List is LinkedList:

Object
    AbstractCollection (implements Collection)
        AbstractList (implements List)
            AbstractSequentialList
                LinkedList
            ArrayList
            Vector
                Stack
        AbstractSet (implements Set)
            HashSet
            TreeSet (implements SortedSet)
    AbstractMap (implements Map)
        HashMap
        TreeMap (implements SortedMap)
        WeakHashMap
    Dictionary
        Hashtable (implements Map)
            Properties

LinkedList implements the List, as you might expect, as a linked list of nodes.  As a result, the performance of insertions into the middle of the list is expected to be better than that of the ArrayList.  On the other hand, the performance of retrieving a particular entry in the list is expected to be better for ArrayList than for LinkedList.

When designing an application, it is very important to choose an appropriate implementation for the performance demands of your application.  This choice can make a significant difference, sometimes by orders of magnitude!

Here’s an example of how one could use an instance of class LinkedList.  It will run only under JDK 1.2 and beyond:

package examples;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class LinkedListExample
{
  public static void main(String[] args)
  {
    List list = new LinkedList();
    list.add("Mary");
    list.add("Frank");
    list.add("Joe");
    list.add("Sylvia");
    list.add("Vanessa");

    for (int i = 0; i < list.size(); i++)
    {
      String name = (String) list.get(i); // Note required cast
      System.out.println(i + ": " + name);
    }

    for (ListIterator iter = list.listIterator(); iter.hasNext(); )
    {
      String name = (String) iter.next(); // Note required cast
      System.out.println(name);
    }
  }
}

Note the fact that I have changed the code in a somewhat subtle way:

List list = new LinkedList();

as opposed to:

LinkedList list = new LinkedList();

Why did I do this?  Why might it be a good thing?

This program produces the output:

0: Mary
1: Frank
2: Joe
3: Sylvia
4: Vanessa
Mary
Frank
Joe
Sylvia
Vanessa

The output is exactly the same as for the earlier ArrayList example.

Again, note the two ways of obtaining the elements of the list:

• Access each element by its index, using the get(int index) method
• Access each element through an ListIterator object, supplied by the LinkedList. (Remember, ListIterator is an interface.)

The Stack Class

The Stack class implements a Last In, First Out (LIFO) stack.  It extends Vector, and so is a kind of List.

Object
    AbstractCollection (implements Collection)
        AbstractList (implements List)
            AbstractSequentialList
                LinkedList
            ArrayList
            Vector
                Stack
        AbstractSet (implements Set)
            HashSet
            TreeSet (implements SortedSet)
    AbstractMap (implements Map)
        HashMap
        TreeMap (implements SortedMap)
        WeakHashMap
    Dictionary
        Hashtable (implements Map)
            Properties

Stack adds the following methods beyond what its super-classes provide:

package java.util;

public class Stack extends Vector 
{
    // Constructs an empty stack
    public Stack() {}
    // Pushes an item onto the stack
    public Object push(Object item) {...)
    // Pops the top item off the stack
    public synchronized Object pop() {...}
    // Peeks at the top item on the stack, without removing it.
    public synchronized Object peek() {...}
    // Returns whether the stack is empty.
    public boolean empty() {...}
    // Returns the 1-based position where an object is on the stack.
    public synchronized int search(Object o) {...}
}

Here’s an example of the use of a Stack:

package examples;

import java.util.Stack;

public class StackExample
{
  public static void main(String[] args)
  {
    Stack stack = new Stack();
    stack.push("Mary");
    stack.push("Frank");
    stack.push("Joe");
    stack.push("Sylvia");
    stack.push("Vanessa");

    while ( !stack.empty() )
    {
      String name = (String) stack.pop(); // Note required cast
      System.out.println(name);
    }
  }
}

This program outputs the following:

Vanessa
Sylvia
Joe
Frank
Mary

which is in the exact reverse order of the elements pushed onto the stack.

Note that I’ve used the empty method, which is in the JDK 1.1 version of Stack.  If I had used the isEmpty method, this would have restricted the class to working only under JDK 1.2 and beyond.

Algorithms

As mentioned earlier, a collections framework provides interfaces, implementations and algorithms.

An example of an algorithm is a sort.   Sorting algorithms have been the subject of an immense amount of research in computer science over the years.  You most likely have already studied several sort algorithms in a Data Structures and Algorithms class.

By its very nature, a sort can only be applied to a collection that has a defined ordering.  That is, one element of the collection can be compared against another element to determine which order to place them in.  There are two interfaces which support such comparisons:  Comparable and Comparator.

The Comparable Interface

The Comparable interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class’s natural ordering, and the class’s compareTo method is referred to as its natural comparison method.

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

Comparable defines the following methods:

package java.lang;

public interface Comparable 
{
    public int compareTo(Object o);
}

where the compareTo method returns:

• a negative integer if this object is less then the specified object
• zero if this object is equal to the specified object
• a positive integer if this object greater than the specified object.

The Comparator Interface

The Comparator interface is for imposing an ordering in the case where you might wish to compare two objects that do not implement the Comparable interface (or even on objects that do, if you wish).

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

Comparator defines the following methods:

package java.util;

public interface Comparator 
{
    int compare(Object o1, Object o2);
    boolean equals(Object obj);
}

As with the Comparable compareTo method, the Comparator compare method returns:

• a negative integer if the first argument is less than the second argument
• zero if the first argument is equal to the second argument
• a positive integer if the first argument is greater than the second argument

The equals method may or may not need to be implemented in the class that implements Comparator, because the Object class implements such an equals method, which suffices for most purposes.  However, you may wish to override this method to improve performance by allowing programs to determine that two distinct Comparators impose the same order.

The Collections Class

The Collections class (in the java.util package) defines a set of methods and constants that are useful for working with collections and maps.  

Object
    Collections

The Collections class consists only of static methods and constants, and may not be instantiated. It should not be confused with the Collection (singular!) interface.

Collections implements the following public methods:

package java.util;

public class Collections 
{
    // Algorithms

    // sort sorts the specified list into ascending order, 
    // according to the natural ordering of its elements.
    // (uses a modified merge sort)
    public static void sort(List list) {...}
    public static void sort(List list, Comparator c) {...}
    // binarySearch searches the specified list for the specified object 
    // using the binary search algorithm
    public static int binarySearch(List list, Object key) {...}
    public static int binarySearch(List list, Object key, Comparator c) {...}
    // reverse reverses the order of the elements in the specified list.
    public static void reverse(List l) {...}
    // shuffle randomly permutes the specified list
    public static void shuffle(List list) {...}
    public static void shuffle(List list, Random rnd) {...}
    // fill replaces all of the elements of the specified list 
    // with the specified element.
    public static void fill(List list, Object o) {...}
    // copy copies all of the elements from one list into another.
    public static void copy (List dest, List src) {...}
    // min returns the minimum element of the given collection, 
    // according to the natural ordering of its elements.
    public static Object min(Collection coll) {...}
    public static Object min(Collection coll, Comparator comp) {...}
    // max returns the maximum element of the given collection, 
    // according to the natural ordering of its elements.
    public static Object max(Collection coll) {...}
    public static Object max(Collection coll, Comparator comp) {...}

    // Unmodifiable Wrappers

    public static Collection unmodifiableCollection(Collection c) {...}
    public static Set unmodifiableSet(Set s) {...}
    public static SortedSet unmodifiableSortedSet(SortedSet s) {...}
    public static List unmodifiableList(List list) {...}
    public static Map unmodifiableMap(Map m) {...}
    public static SortedMap unmodifiableSortedMap(SortedMap m) {...}

    // Synch Wrappers

    public static Collection synchronizedCollection(Collection c) {...}
    public static Set synchronizedSet(Set s) {...}
    public static SortedSet synchronizedSortedSet(SortedSet s) {...}
    public static List synchronizedList(List list) {...}
    public static Map synchronizedMap(Map m) {...}
    public static SortedMap synchronizedSortedMap(SortedMap m) {...}

    // Miscellaneous

    /**
     * The empty set (immutable).  This set is serializable.
     */
    public static final Set EMPTY_SET = ...;

    /**
     * The empty list (immutable).  This list is serializable.
     */
    public static final List EMPTY_LIST = ...;

    /**
     * Returns an immutable set containing only the specified object.
     * The returned set is serializable.
     *
     * @return an immutable set containing only the specified object.
     */
    public static Set singleton(final Object o) {...}

    /**
     * Returns an immutable list consisting of n copies of the
     * specified object.  This method is useful in combination 
     * with the List.addAll method to grow lists.
     * The returned list is serializable.
     *
    public static List nCopies(final int n, final Object o) {...}

    /**
     * Returns a comparator that imposes the reverse of the natural
     * ordering on a collection of objects that implement the
     * Comparable interface.  (The natural ordering is the ordering
     * imposed by the objects' own compareTo method.)  This enables a
     * simple idiom for sorting (or maintaining) collections (or arrays) of
     * objects that implement the Comparable interface in
     * reverse-natural-order.  For example, suppose a is an array of
     * strings. Then:
     * 		Arrays.sort(a, Collections.reverseOrder());
     * sorts the array in reverse-lexicographic (alphabetical) order.
     *
     * The returned comparator is serializable.
     */
    public static Comparator reverseOrder() {...}

    /**
     * Returns an enumeration over the specified collection.  This provides
     * interoperability with legacy APIs that require an enumeration
     * as input.
     */
    public static Enumeration enumeration(final Collection c) {...}
}

where “...” represents implementation code, the details of which have been omitted.

A Comparable Example

Here’s an example of sorting, using the Comparable interface.

Note that String is defined to implement Comparable in JDK 1.2 and beyond.  We are using String‘s natural ordering, as defined by its compareTo method.

package examples;

import java.util.Collections;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ComparableSorter
{
  public static void main(String[] args)
  {
    List list = new ArrayList();
    list.add("abc");
    list.add("DEF");
    list.add("ghi");

    // Do the sort
    Collections.sort(list);

    // See results
    Iterator iter = list.iterator();
    while (iter.hasNext())
    {
      System.out.println(iter.next());
    }
  }
}

which outputs:

DEF
abc
ghi

As you can see, the natural ordering for Strings is case-sensitive.

A Comparator Example

Here’s an example of sorting using a Comparator interface.

It’s basically the same as the previous example, except that it uses a class that implements Comparator. We’re using it to implement a case-insensitive compare.

In other words, if we want to sort using a non-natural ordering, we must use a Comparator.

package examples;

import java.util.Collections;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ComparatorSorter
{
  public static void main(String[] args)
  {
    List list = new ArrayList();
    list.add("abc");
    list.add("DEF");
    list.add("ghi");

    // Do the sort
    Collections.sort(list, new CaseInsensitiveComparator() );

    // See results
    Iterator iter = list.iterator();
    while (iter.hasNext())
    {
      System.out.println(iter.next());
    }
  }
}

class CaseInsensitiveComparator implements Comparator
{
  public int compare(Object o1, Object o2)
  {
    String s1 = (String) o1;
    String s2 = (String) o2;
    return s1.toLowerCase().compareTo( s2.toLowerCase() );
  }
}

which outputs:

abc
DEF
ghi

You can see the changes from the previous example, highlighted.

General Applicability

I could add a number of examples, using other algorithms such as:

• binarySearch
• reverse
• shuffle
• fill
• copy
• min
• max
• etc.

but the main point of this collections framework is consistency:

If you know how to call one algorithm, you know how to use them all;  only minor changes have to be made.

This makes learning the framework a breeze, once you’ve learned the basics!

Sets

Mathematically, a set is a collection of elements each of which has a unique value.  That is, the value of no element in the set duplicates the value of another element in the set.

For example, {1,2,3,4} is a set, because every element is unique.  On the other hand, {a,b,c,d,e,a} is not a set, because there are two elements ‘a’.The Collections Framework includes support for such sets.  Here’s how…

The Set Interface

The Set interface enforces the rule that the collection not contain duplicates:

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

Note that Set is a sub-interface of Collection. 

The HashSet Class

The HashSet class is an implementation of Set that uses a hash table:

Object
    AbstractCollection (implements Collection)
        AbstractSet (implements Set)
            HashSet

Here is our previous example that used ArrayList, changed to using HashSet.

The example only uses the Iterator approach to obtaining the elements from the collection, because there is no inherent ordering in a Set.

Note that I have added an additional call to add, which attempts to add a duplicate element for “Frank”.

package examples;

import java.util.HashSet;
import java.util.Iterator;

public class HashSetExample
{
  public static void main(String[] args)
  {
    HashSet set = new HashSet();
    set.add("Mary");
    set.add("Frank");
    set.add("Joe");
    set.add("Sylvia");
    set.add("Vanessa");
    set.add("Frank");   // Duplicate

    for (Iterator iter = set.iterator(); iter.hasNext(); )
    {
      String name = (String) iter.next(); // Note required cast
      System.out.println(name);
    }
  }
}

It outputs the following:

Vanessa
Joe
Frank
Mary
Sylvia

which shows that no duplicate element was added.  It also shows that the contents are returned in no particular order

The SortedSet Interface

If you want a set that is ordered, then you can use a SortedSet interface:

Collection
    Set
        SortedSet

The SortedSet interface adds the following methods to those already specified by Set:

The TreeSet Class

An implementation of a SortedSet is the TreeSet class, which uses a tree as its implementation:

Object
    AbstractCollection (implements Collection)
        AbstractSet (implements Set)
            TreeSet (implements SortedSet)

package examples;

import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetExample
{
  public static void main(String[] args)
  {
    TreeSet set = new TreeSet();
    set.add("Mary");
    set.add("Frank");
    set.add("Joe");
    set.add("Sylvia");
    set.add("Vanessa");
    set.add("Frank");   // Duplicate

    for (Iterator iter = set.iterator(); iter.hasNext(); )
    {
      String name = (String) iter.next(); // Note required cast
      System.out.println(name);
    }
  }
}

Note the minimal changes to the program from the earlier HashSet example. This is a consequence of the consistent use of interfaces, and having different implementations that use the same interface.

Here’s the output of the example:

Frank
Joe
Mary
Sylvia
Vanessa

which shows that we still have no duplicates, but that the elements are now returned in the proper order (in this case, alphabetically).

TreeSet with Comparator

If we wish, we can impose a different ordering, by specifying a Comparator. 

In the following example, we reverse the ordering by the use of an explicit ReverseOrderComparator class:

package examples;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

public class ReversedTreeSetExample
{
  public static void main(String[] args)
  {
    TreeSet set = new TreeSet( new ReverseOrderComparator() );
    set.add("Mary");
    set.add("Frank");
    set.add("Joe");
    set.add("Sylvia");
    set.add("Vanessa");
    set.add("Frank");   // Duplicate

    for (Iterator iter = set.iterator(); iter.hasNext(); )
    {
      String name = (String) iter.next(); // Note required cast
      System.out.println(name);
    }
  }
}

class ReverseOrderComparator implements Comparator
{
  public int compare(Object o1, Object o2)
  {
    String s1 = (String) o1;
    String s2 = (String) o2;
    return -(s1.compareTo(s2));
    // Reverse order by reversing comparison
  }
}

which outputs:

Vanessa
Sylvia
Mary
Joe
Frank

As you can see, the results are in reverse alphabetical order.

Maps

A map is an object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

Here’s where we see how the Collections Framework supports maps.

The Map Interface

The Map interface defines methods that map keys to values.  A Map cannot contain duplicate keys.

Note that Map is at the root of a distinct interface hierarchy, and so it is not strictly speaking a true collection.   

Collection
    List
    Set
        SortedSet
Comparable (in java.lang package)
Comparator
Enumeration
Iterator
    ListIterator
Map
    SortedMap

A Map is not really a collection of elements, but a mapping of keys to values.

Map defines the following methods:

package java.util;

public interface Map 
{
    // Query Operations

    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    Object get(Object key);

    // Modification Operations

    Object put(Object key, Object value);
    Object remove(Object key);

    // Bulk Operations

    void putAll(Map t);
    void clear();

    // Views

    /**
     * Returns a set view of the keys contained in this map.  
     */
    public Set keySet();

    /**
     * Returns a collection view of the values contained in this map.  
     */
    public Collection values();

    /**
     * Returns a set view of the mappings contained in this map.  
     */
    public Set entrySet();

    /**
     * A map entry (key-value pair).  
     */
    public interface Entry 
    {
	Object getKey();
	Object getValue();
	Object setValue(Object value);
	boolean equals(Object o);
	int hashCode();
    }

    // Comparison and hashing

    /**
     * Compares the specified object with this map for equality.  
     */
    boolean equals(Object o);

    /**
     * Returns the hash code value for this map.  
     */
    int hashCode();
}

The HashMap Class

The HashMap class implements the Map interface, using a hash table:

Object
    AbstractMap (implements Map)
        HashMap

Because of the implementation, the entries in a HashMap have no inherent ordering.

Here’s an example of using the HashMap class.  

Note that in this example the key is the person’s name, and the value is the person’s telephone number.  In general, the key and the associated value are not limited to strings:

package examples;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class HashMapExample
{
  public static void main(String[] args)
  {
    HashMap map = new HashMap();
    map.put("Mary", "555-1234");
    map.put("Frank", "555-5678");
    map.put("Joe", "555-9012");
    map.put("Sylvia", "555-3456");
    map.put("Vanessa", "555-7890");
    map.put("Frank", "555-0987");   // Duplicate

    for (Iterator iter = map.entrySet().iterator(); iter.hasNext(); )
    {
      Map.Entry entry = (Map.Entry) iter.next(); // Note required cast
      String key = (String) entry.getKey(); // Note required cast
      String value = (String) entry.getValue(); // Note required cast
      System.out.println(key + ":" + value);
    }
  }
}

which outputs:

Vanessa:555-7890
Joe:555-9012
Frank:555-0987
Mary:555-1234
Sylvia:555-3456

Note the similarities to the previous code.  This is not accidental.  Again, it results from the consistent use of the appropriate set of interfaces.

Also, we can tell from the output of the program that the final put has the effect of replacing the value for Frank that was entered earlier.

In particular, note the fact that a Map does not have a direct way of obtaining an iterator.  Instead, it defines an interface, Entry, nested within the Map class.  It also defines a method entrySet() which returns a Set object (that is, an instance of a class that implements Set) corresponding to the entries in the Map  You can then obtain an iterator from that Set object.  The iterator returns Entry objects, from which you can obtain the key and value.

The SortedMap Interface

The SortedMap interface is a sub-interface of Map. 

SortedMap is a map that further guarantees that it will be held in ascending key order, sorted according to the natural ordering of its keys (see the Comparable interface), or by a comparator provided at sorted map creation time.

SortedMap adds the following methods to those specified by Map:

The TreeMap Class

The TreeMap class implements a SortedMap, which means that it keeps the entries in key order. 

TreeMap uses a tree to implement the SortedMap:

Object
    AbstractMap (implements Map)
        TreeMap (implements SortedMap)

Here’s an example of its use:

package examples;

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample
{
  public static void main(String[] args)
  {
    TreeMap map = new TreeMap();
    map.put("Mary", "555-1234");
    map.put("Frank", "555-5678");
    map.put("Joe", "555-9012");
    map.put("Sylvia", "555-3456");
    map.put("Vanessa", "555-7890");
    map.put("Frank", "555-0987");   // Duplicate

    for (Iterator iter = map.entrySet().iterator(); iter.hasNext(); )
    {
      Map.Entry entry = (Map.Entry) iter.next(); // Note required cast
      String key = (String) entry.getKey(); // Note required cast
      String value = (String) entry.getValue(); // Note required cast
      System.out.println(key + ":" + value);
    }
  }
}

which, as you can see, is minimally different from the HashMap example.

It outputs:

Frank:555-0987
Joe:555-9012
Mary:555-1234
Sylvia:555-3456
Vanessa:555-7890

which is in order by key, and also shows that the value associated with the second key value of “Frank” is the one that survives, causing the original “Frank” to be removed.

TreeMap with Comparator

To change the order in which the TreeMap orders its elements, you can use a Comparator object, as before:

package examples;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class ReversedTreeMapExample
{
  public static void main(String[] args)
  {
    TreeMap map = new TreeMap( new ReverseOrderKeyComparator() );
    map.put("Mary", "555-1234");
    map.put("Frank", "555-5678");
    map.put("Joe", "555-9012");
    map.put("Sylvia", "555-3456");
    map.put("Vanessa", "555-7890");
    map.put("Frank", "555-0987");   // Duplicate

    for (Iterator iter = map.entrySet().iterator(); iter.hasNext(); )
    {
      Map.Entry entry = (Map.Entry) iter.next(); // Note required cast
      String key = (String) entry.getKey(); // Note required cast
      String value = (String) entry.getValue(); // Note required cast
      System.out.println(key + ":" + value);
    }
  }
}

class ReverseOrderKeyComparator implements Comparator
{
  public int compare(Object o1, Object o2)
  {
    String s1 = (String) o1;
    String s2 = (String) o2;
    return -(s1.compareTo(s2));
    // Reverse order by reversing comparison
  }
}

which outputs the following:

Vanessa:555-7890
Sylvia:555-3456
Mary:555-1234
Joe:555-9012
Frank:555-0987

showing the expected reverse order by key.