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

Set Basics

In this set of notes we will go over the fundamentals of the Set Interface and the SortedSet Interface. If you are Mathematician and understand Mathematical Sets, then the Set interface is a close implementation of this concept.

interface Set extends Collection

The methods in the Set inteface are the same as the Collection interface. We will explain the Set interface by comparing it with the List interface which are both derived from the Collection interface.

Set has the following properties:

1. A Set does not allow duplicates, while the List interface does allow duplicates.
2. A Set is not ordered, while a List is ordered.
3. A Set allows a null entry to be added. However only one null can be added (remember each element must be unique)
4. HashSet is the one class that Java provides that implements the Set interface. Hashing algorithms are famous for fast lookup, but do not keep things in any particular order.
5. Because the methods are the same as collection, I have repeated them below.

interface Collection or interface Set

Note I am not showing all of the required methods ... just a few representative ones to give you the idea of what you have to work with.

Proto-Type | Description
boolean add(E e) | Ensures that this collection contains the specified element (optional operation).
void clear() | Removes all of the elements from this collection (optional operation).
boolean contains(E e) | Returns true if this collection contains the specified element.
boolean isEmpty() | Returns true if this collection contains no elements.
Iterator<E> iterator() | Returns an iterator over the elements in this collection.
boolean remove(E e) | Removes a single instance of the specified element from this collection, if it is present (optional operation). boolean retainAll(Collection c) Retains only the elements in this collection that are contained in the specified collection (optional operation).
int size() | Returns the number of elements in this collection.
Object[] toArray() | Returns an array containing all of the elements in this collection.
Object[] toArray(Object[] a) | Returns an array containing all of the elements in this collection whose runtime type is that of the specified array.

There are 3 classes which implement the Set interfaces: HashSet, LinkedHashSet, and TreeSet (actually implements SortedSet which extends Set).

What must a class do to provide a good implementation of the Set interface .... it must be quick to identify whether an object is in the Set to avoid duplicates.

TryOutSetInterface.java


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


public class TryOutSetInterface {

    public static void main(String[] args) {

//HashSet iterates in a random fashion
        Set<String> set = new HashSet<String>();
//LinkedHashSet maintains the ordering of the insertion
        //Set<String> set = new LinkedHashSet<String>();
//TreeSet maintains the ordering sorted by "Natural Ordering"
        //Set<String> set = new TreeSet<String>();

        set.add("one");
        set.add("two");
        set.add(null); // Yes some of the Set implementations allow a null  ... but only one

        if (set.add("three"))
            System.out.println("three was added");

        if (!set.add("three"))
            System.out.println("three was not added again because it is a duplicate");

        if (set.contains("two"))
            System.out.println("set should contain two");

        if (!set.contains("fifty"))
            System.out.println("set should not contain fifty");

        set.add("four");
        set.add("five");
        set.add("six");
        set.add("seven");
        set.add("eight");

        System.out.println("******* iteration dump ********");
        Iterator<String> iter = set.iterator();
        while (iter.hasNext())
        {
            System.out.println(iter.next());
        }
    }

}



SortedSet Interface

1. This interface extends the Set interface, so it doesn't allow duplicates.
2. The major change between a SortedSet interface and a Set interface is that the SortedSet always keeps its elements sorted unlike the Set interface.
3. Because of the Sorted property, each element must be mutually comparable, which means that they have to be of the same type so they can be compared against one another. If you create your own class (remember the Pet/Dog/Cat classes in the ArrayList notes), then be prepared to implement the Comparable interface in your class.
4. Because of the Sorted property, the interface has some methods that allow you to return subsections of the SortedSet.
5. Java provides the TreeSet class which implements SortedSet. The TreeSet class uses a binary tree mechanism to maintain the sorted ordering of the Set.

interface SortedSet extends Set

Proto-Type | Description
E first() | Returns the first (lowest) element currently in this sorted set.
SortedSet headSet(E toElement) | Returns a view of the portion of this sorted set whose elements are strictly less than toElement.
E last() | Returns the last (highest) element currently in this sorted set.
SortedSet subSet(E fromElement, E toElement) | Returns a view of the portion of this sorted set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet tailSet(E fromElement) | Returns a view of the portion of this sorted set whose elements are greater than or equal to fromElement.

The following example will try out the above methods:

TryOutSortedSetInterface.java


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


public class TryOutSortedSetInterface {

    static void dump(SortedSet<String> ss)
    {
        Iterator<String> iter = ss.iterator();
        while (iter.hasNext())
        {
            System.out.println(iter.next());
        }
        System.out.println("********************************");
        System.out.println();
    }


    public static void main(String[] args) {
        String[] greek={"zeta", "epsilon", "delta", "alpha", "pi", "rho", "gamma", "tau", "eta",
                "alpha", "theta", "sigma", "phi", "omega", "gamma", "lambda"};

        SortedSet<String> sortedSet = new TreeSet<String>();
        for (int i=0; i < greek.length; i++)
        {
            if (!sortedSet.add(greek[i]))
            {
                System.out.println("The following was a duplicate: "+ greek[i]);
            }
        }

        System.out.println("***** Total Iteration dump *****");
        dump(sortedSet);

        // Methods from SortedSet:
        System.out.println("first() = " + sortedSet.first());
        System.out.println("last() = " + sortedSet.last());

        System.out.println("***** headSet(gamma) *****");
        SortedSet ss = sortedSet.headSet("gamma");
        dump(ss);

        System.out.println("***** tailSet(rho) *****");
        ss = sortedSet.tailSet("rho");
        dump(ss);

        System.out.println("***** subSet(gamma, rho) *****");
        ss = sortedSet.subSet("gamma", "rho");
        dump(ss);
    }
}



Hash based data structures: How about storing your own classes like the Dog class:


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

class Dog
{
    String name;
    int age;
    Dog(String n, int a)
    {
        name=n;
        age = a;
    }
    public String toString()
    {
        return name +":" + age;
    }
    public boolean equals(Object obj)
    {
        if (obj == null)
            return false;
        if (obj != null)
        {
            Dog otherDog = (Dog)obj;
            if (name.equals(otherDog.name) && age == otherDog.age)
                return true;
        }
        return false;
    }
    /*
     public int hashCode()
     {
         return age * name.hashCode();
     }
     */

}

public class TryOutDogHashSet {

    public static void main(String[] args) {

        Set<Dog> set = new HashSet<Dog>();
        //Set<Dog> set = new LinkedHashSet<Dog>();

        set.add(new Dog("Pooch",2));
        Dog spike = new Dog("Spike",1);
        set.add(spike);
        set.add(null); // Yes you can store a Null in a Set ... but only one

        Dog spot = new Dog("Spot", 3);
        if (set.add(spot))
            System.out.println(spot+ " was added");

        if (!set.add(new Dog("Spot", 3)))
            System.out.println(spot+ " was not added again because it is a duplicate");

        if (set.contains(new Dog("Spike",1)))
            System.out.println("set should contain " + spike);

        set.add(new Dog("Fred",2));
        set.add(new Dog("Barney",3));
        set.add(new Dog("Fido",4));
        set.add(new Dog("Bruno",5));
        set.add(new Dog("Max",6));

        System.out.println("******* iteration dump ********");
        Iterator<Dog> iter = set.iterator();
        while (iter.hasNext())
        {
            System.out.println(iter.next());
        }
    }
}



TreeSet data structure: How about storing your own classes like the Dog class:



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

    class Dog
    //class Dog implements Comparable<Dog>
    {
        String name;
        int age;
        Dog(String n, int a)
        {
            name=n;
            age = a;
        }
        public String toString()
        {
            return name +":" + age;
        }
        public boolean equals(Object obj)
        {
            if (obj == null)
                return false;
            if (obj != null)
            {
                Dog otherDog = (Dog)obj;
                if (name.equals(otherDog.name) && age == otherDog.age)
                    return true;
            }
            return false;
        }
    /*
        public int compareTo(Dog d) {
            int retval = name.compareTo(d.name);
            if (retval != 0)
                return retval;
            return (age - d.age);
        }
    */


    }

    public class TryOutDogTreeSet {

        public static void main(String[] args) {

            Set<Dog> set = new TreeSet<Dog>();

            set.add(new Dog("Pooch",2));
            Dog spike = new Dog("Spike",1);
            set.add(spike);

            Dog spot = new Dog("Spot", 3);
            if (set.add(spot))
                System.out.println(spot+ " was added");

            if (!set.add(new Dog("Spot", 3)))
                System.out.println(spot+ " was not added again because it is a duplicate");

            if (set.contains(new Dog("Spike",1)))
                System.out.println("set should contain " + spike);

            set.add(new Dog("Fred",2));
            set.add(new Dog("Barney",3));
            set.add(new Dog("Fido",4));
            set.add(new Dog("Bruno",5));
            set.add(new Dog("Bruno",1));
            set.add(new Dog("Max",6));

            System.out.println("******* iteration dump ********");
            Iterator<Dog> iter = set.iterator();
            while (iter.hasNext())
            {
                System.out.println(iter.next());
            }

        }

    }


Last Updated: July 22, 2014 9:51 PM