SetsS2C Home « Sets

In the first of three lessons on the different collection types within the Collection hierarchy we look at Sets which are probably the easiest collection type to understand, and as such, a good starting point. So what type of collection is a Set? A Set doesn't allow duplicates so every entry within a Set must be unique and as the name implies the interface models the mathematical set abstraction. In practical terms this means that we can never have more than one element within the Set referencing the same object or more than one element within the Set referencing two objects that are considered equal. See the Checking Object Equality section from the OO Concepts - The Object Superclass section of the site for a reminder of what constitutes object equality. We can also only have a maximum of one entry within the set with a value of null.

Set Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the Set hierarchy and covers the interfaces and classes we will study in this lesson. The diagram has several interfaces missing and also the java.util.EnumSet<E> concrete implemetation which is not covered on the site, but should help in visualisation:

Set hierarchy

Set Interfaces & Classesgo to top of page Top

The table below gives a description of each interface and class within the above diagram. Click a link to go to detailed information about a particular class:

Interface/Class Description
Collection<E>The root interface in the Collection hierarchy which the Set<E> interface extends. There is no direct implementation of the Collection<E> interface within the JDK.
Set<E>Interface for unique collections of elements.
HashSet<E>Implementation of the Set<E> interface using a HashMap instance.
LinkedHashSet<E>Hash table and linked list implementation of the Set<E> interface that implements all optional set operations and permits all elements, including null.
SortedSet<E>Interface for unique collections of sorted elements.
TreeSet<E>Implementation of the Set<E> interface using a TreeMap instance.

Set Types and Orderinggo to top of page Top

The table below extrapolates the commented information about ordering from the diagram above into a more readable tabular format:

Collection Type Ordering
SetOrderedSorted
HashSet<E>NoNo
LinkedHashSet<E>By insertion orderNo
TreeSet<E>SortedNatural/bespoke order

HashSetsgo to top of page Top

A HashSet is an unordered and unsorted implementation of the Set<E> interface, backed by a hash table using a HashMap instance. This type of set makes no guarantees over iteration order and in particular no guarantees that the iteration order will remain constant over time.

The hashcode of the object being inserted into the collection is used so the more efficient your override of the hashCode() method of the Object class is, the more efficient the HashSet. This also means that if you want to find out if an object exists within the set, or you want to delete an object from the set, then you need a reference to the object in question.

This type of set is a good choice when you want a collection with no duplicates and fast access and the order doesn't matter when iterating over it.

HashSet<E> Method Overviewgo to top of page Top

The table below shows the declarations of all the methods for the HashSet<E> class implemented from the Set<E> interface:

Method Declaration Description
Used in the example below
public boolean add(E o) Adds the specified element to this HashSet if it is not already present.
public void clear()Removes all of the elements from this HashSet.
public boolean contains(Object o)Returns true if this HashSet contains the specified element.
public boolean isEmpty()Returns true if this HashSet contains no elements.
public boolean remove(Object o)Removes the specified element from this HashSet if it is present.
public int size()Returns the number of elements in this HashSet, ie. its cardinality.
Not used in the example below
public Object clone()Creates and returns a shallow copy of this HashSet although the elements themselves are not cloned.
public Iterator<E> iterator()Returns an iterator over the elements in this HashSet.

Usage for the the first six methods is shown in the example below. For more information on the other methods in the HashSet<E> class the following link will take you to the online version of documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. Take a look at the documentation for the HashSet<E> class which you can find by scrolling down the lower left pane and clicking on HashSet.

HashSet<E> Examplego to top of page Top

Lets write a simple class that creates a HashSet and uses some of the methods from the HashSet<E> class:


/*
  Simple class to create a HashSet and use several methods from the class 
*/
import java.util.*; // Import the java.util package

public class HashSetClass {

    public static void main (String[] args) {
        Set<String> hs = new HashSet<String>();
        String s = "hello";
        hs.add(s);
        hs.add("goodbye");
        hs.add(s+s);
        System.out.println("hash set size = " + hs.size());
        // Use enhanced for loop to iterate over the collection
        for (String str : hs) { 
            System.out.println(str);  // Print element
        }        
        hs.remove(s);  
        System.out.println(hs.contains(s));  
        System.out.println("hash set size = " + hs.size());
        // Use enhanced for loop to iterate over the collection
        for (String str : hs) { 
            System.out.println(str);  // Print element
        }        
        // Check for empty set, clear set and then check again
        System.out.println(hs.isEmpty());
        hs.clear();  
        System.out.println(hs.isEmpty());
    }
}

Save, compile and run the HashSetClass class in directory   c:\_Collections in the usual way.

Run hash set class

The above screenshot shows the results of creating and running our HashSetClass class and using several of the methods contained within the HashSet<E> class.

LinkedHashSetsgo to top of page Top

A LinkedHashSet is a Hash table and linked list implementation of the Set interface with predictable iteration order and differs from a HashSet by maintaintaining a doubly-linked list running through all of its elements. The linked list defines the iteration order of a LinkedHashSet by the order in which elements are inserted into the set.

This type of set is a good choice when you want a collection with no duplicates and fast access and you want to maintain an insertion order when iterating over it.

LinkedHashSet<E> Method Overviewgo to top of page Top

The table below shows the declarations of all the methods for the LinkedHashSet<E> class that are inherited directly from the HashSet<E> class:

Method Declaration Description
Used in the example below
public boolean add(E o) Adds the specified element to this LinkedHashSet if it is not already present.
public void clear()Removes all of the elements from this LinkedHashSet.
public boolean contains(Object o)Returns true if this LinkedHashSet contains the specified element.
public boolean isEmpty()Returns true if this LinkedHashSet contains no elements.
public boolean remove(Object o)Removes the specified element from this LinkedHashSet if it is present.
public int size()Returns the number of elements in this LinkedHashSet, ie. its cardinality.
Not used in the example below
public Object clone()Creates and returns a shallow copy of this LinkedHashSet although the elements themselves are not cloned.
public Iterator<E> iterator()Returns an iterator over the elements in this LinkedHashSet.

Usage for the the first six methods is shown in the example below.

LinkedHashSet<E> Examplego to top of page Top

Lets write a simple class that creates a HashSet and uses some of the methods from the HashSet<E> class:


/*
  Simple class to create a LinkedHashSet and use several methods inherited from the HashSet class 
*/
import java.util.*; // Import the java.util package

public class LinkedHashSetClass {

    public static void main (String[] args) {
        Set<String> lhs = new LinkedHashSet<String>();
        String s = "one";
        lhs.add(s);
        lhs.add("two");
        lhs.add(s+s);
        System.out.println("linked hash set size = " + lhs.size());
        // Use enhanced for loop to iterate over the collection
        for (String str : lhs) { 
            System.out.println(str);  // Print element
        }        
        lhs.remove(s);  
        System.out.println(lhs.contains(s));  
        System.out.println("linked hash set size = " + lhs.size());
        // Use enhanced for loop to iterate over the collection
        for (String str : lhs) { 
            System.out.println(str);  // Print element
        }        
        // Check for empty set, clear set and then check again
        System.out.println(lhs.isEmpty());
        lhs.clear();  
        System.out.println(lhs.isEmpty());
    }
}

Save, compile and run the LinkedHashSetClass class in directory   c:\_Collections in the usual way.

Run linked hash set class

The above screenshot shows the results of creating and running our LinkedHashSetClass class and using several of the methods contained within the HashSet<E> class.

TreeSetsgo to top of page Top

A TreeSet is a sorted implementation of the Set<E> interface, backed by a TreeMap instance. This type of set guarantees that the set will be sorted in ascending order, according to the natural order of the elements contained within it, or by a custom comparator/comparable, dependant upon the type of constructor used on creation.

The ordering maintained by a set whether through natural order of the elements contained within it or by a custom comparator/comparable, must be consistent with the equals() method override rules of the Object class if it is to correctly implement the Set<E> interface and obey the rules of equality.

This type of set is a good choice when you want a sorted collection with no duplicates with the option of custom sorting.

TreeSet<E> Method Overviewgo to top of page Top

The table below shows the declarations of all the methods for the TreeSet<E> class implemented from the Set<E> and SortedSet<E> interfaces:

Method Declaration Description
Used in the example below
public boolean add(E o) Adds the specified element to this TreeSet if it is not already present.
public void clear()Removes all of the elements from this TreeSet.
public boolean isEmpty()Returns true if this TreeSet contains no elements.
public boolean remove(Object o)Removes the specified element from this TreeSet if it is present.
public int size()Returns the number of elements in this TreeSet, ie. its cardinality.
Not used in the example below
boolean addAll(Collection<? extends E> c)Adds all of the elements in the specified collection to this TreeSet.
public Object clone()Creates and returns a shallow copy of this TreeSet although the elements themselves are not cloned.
public boolean contains(Object o)Returns true if this TreeSet contains the specified element.
public Comparator<? super E> comparator()Returns the comparator used to order this TreeSet, or null if this TreeSet uses its elements natural ordering.
public E first()Returns the first element within this TreeSet.
public SortedSet<E> headSet(E toElement)Returns an aspect of this TreeSet whose elements are strictly less than toElement.
public Iterator<E> iterator()Returns an iterator over the elements in this TreeSet.
public E last()Returns the last element within this TreeSet.
public SortedSet<E> subSet(E fromElement, E toElement)Returns an aspect of this TreeSet whose elements range from fromElement inclusive, to toElement exclusive.
public SortedSet<E> tailSet(E fromElement)Returns an aspect of this TreeSet whose elements are greater than or equal to fromElement.

We will go use the first five methods in in the example below. For more information on the other methods in the TreeSet<E> class the following link will take you to the online version of documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. Take a look at the documentation for the TreeSet<E> class which you can find by scrolling down the lower left pane and clicking on TreeSet.

TreeSet<E> Examplego to top of page Top

Lets write a simple class that creates a TreeSet and uses some of the methods from the TreeSet<E> class:


/*
  Simple class to create a TreeSet and use several methods fron from the class 
*/
import java.util.*; // Import the java.util package

public class TreeSetClass {

    public static void main (String[] args) {
        Set<Object> ts = new TreeSet<Object>();
        String s = "one";
        ts.add(s);
        ts.add(123);  // Autoboxed to Integer
        ts.add("two");
        ts.add(s+s);
        System.out.println("tree set size = " + ts.size());
        // Use enhanced for loop to iterate over the collection
        for (Object o : ts) { 
            System.out.println(o);  // Print element
        }
        ts.remove(s);
        // Use enhanced for loop to iterate over the collection
        for (Object o : ts) { 
            System.out.println(o);  // Print element
        }        
        // Check for empty set, clear set and then check again
        System.out.println(ts.isEmpty());
        ts.clear();  
        System.out.println(ts.isEmpty());
    }
}

Save, compile and run the TreeSetClass class in directory   c:\_Collections in the usual way.

Run tree set class

The above screenshot shows the results of creating and running our TreeSetClass class. We get a ClassCastException and the reason for this is that if a collection is to be sorted, then the objects within it need to be mutually comparable and the String and Integer objects are not. We will talk more about sorting collection, comparables, comparators and natural order in much more detail in the Sorting Collections lesson. For now remove the add() to the TreeSet for the Integer object and save, compile and run the TreeSetClass class again.

Run tree set class 2

The above screenshot shows the results of creating and running our TreeSetClass class and it now works.

Lesson 3 Complete

In this lesson we looked at Sets.


What's Next?

In the second of three lessons on the different collection types within the Collection hierarchy we look at three of the concrete implementations of the List<E> interface.

go to home page Homepage go to top of page Top