Set and its implementations in Java

• Tweet

• Tweet

Set that we studied in our math classes in high school, contains no duplicates. Unlike list, a set doesn’t remember where you inserted the elements means it does not remember the insertion order.

• Set cares about uniqueness
• Does not allow duplicates
• equal() method determines whether two object are equal or not.

A set is an interface in java that contains no duplicates elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2) and at most one null element.
Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.

ITCuties – Java – Set

Concrete classes for Set

• HashSet
• LinkedHashSet
• TreeSet

HashSet

Class HashSet<E>
E – the type of elements maintained by this set

• Unsorted (no guarantees as to the iteration order of the set) and Unordered (not guarantee that the order will remain constant over time) set.
• Permit null element
• This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.
• It uses the hashcode of the object being inserted, so the more efficient your hashCode() implementation the better access performance you’ll get.

This implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.

The iterators returned by this class’s iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. (We’ll see this with example)

Examples:
HashSetOfNames.java – demonstrate the basic use of HashSet

package com.javalatte.itcuties.setinterface;

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

public class HashSetOfNames {

    public static void main(String[] JavaLatte) {
        //Constructs a new, empty set; the backing HashMap instance has default 
        //initial capacity (16) and load factor (0.75).
        Set<String> names = new HashSet<String>();
        System.out.println("Is Charlie added " + names.add("Charlie"));
        System.out.println("Is Kumar added " + names.add("Kumar"));
        System.out.println("Is Cuties added " + names.add("Cuties"));
        System.out.println("Is Robert added " + names.add("Robert"));
        System.out.println("Is Bill added " + names.add("Bill"));
        System.out.println("Is William added " + names.add("William"));

        // Notice the output of this Hashset and in what order element are added
        System.out.println();//space
        System.out.println(names);

        //we'll try to add null element
        System.out.println();//space
        System.out.println("Is null added " + names.add(null));

        //We'll try to add duplicate
        System.out.println();//space
        System.out.println("Is Kumar added again " + names.add("Kumar"));

        //remove, contains and size method
        System.out.println();//space
        System.out.println("Is Java element present: " + names.contains("Java"));
        System.out.println("Size of HashSet : " + names.size());
        if (names.remove("Kumar")) {
            System.out.println("Kumar is removed, Size : " + names.size());
        } else {
            System.out.println("Kumar is not removed, Size : " + names.size());
        }
    }
}

HashSetIteratorDemo.java – demonstrate the use of Iterator and ConcurrentModificationException

package com.javalatte.itcuties.setinterface;

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

public class HashSetIteratorDemo {

    public static void main(String[] JavaLatte) {
        //Constructs a new, empty set; the backing HashMap instance has the 
        //specified initial capacity and default load factor (0.75).
        Set<String> sites = new HashSet<String>(10);
        sites.add("Facebook");
        sites.add("Twitter");
        sites.add("Instagram");
        sites.add("500px");
        sites.add("PinInterest");
        sites.add("Tumbler");
        sites.add("Google+");

        Iterator iter = sites.iterator();
        //This will throw ConcurrentModificationException exception as iterator
        //is alread created.
        sites.add("Test"); // comment it to excute 
        sites.remove("500px"); // comment it to excute

        while (iter.hasNext()) {
            System.out.print(iter.next() + " ");
        }
        System.out.println();

    }
}

LinkedHashSet

Class LinkedHashSet<E>
E – the type of elements maintained by this set

• A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements.
• Use this class instead of HashSet when you care about the iteration order.
• This linked list defines the iteration ordering, which is the order in which elements were inserted into the set.
• Permit null element.

Note that insertion order is not affected if an element is re-inserted into the set.
This implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.

The iterators returned by this class’s iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. (We’ll see this with example)

Examples:
LinkedHashSetDemo.java – demonstrate the basic use of LinkedHashSet

package com.javalatte.itcuties.setinterface;

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetDemo {

    public static void main(String[] JavaLatte) {
        //Constructs a new, empty linked hash set with the default initial 
        //capacity (16) and load factor (0.75).
        Set<String> tech = new LinkedHashSet<String>();
        tech.add("Java");
        tech.add("Oracle");
        tech.add("PHP");
        tech.add("C++");
        tech.add(".Net");
        tech.add("JavaScript");

        //Notice the output of this LinkedHashset and in what order element 
        //are added. Insertion order is maintained
        System.out.println(tech);

        //we'll try to add null element
        System.out.println();//space
        System.out.println("Is null added " + tech.add(null));

        //We'll try to add duplicate
        System.out.println();//space
        System.out.println("Is Java added again " + tech.add("Java"));

        //remove, contains and size method
        System.out.println();//space
        System.out.println("Is Java element present: " + tech.contains("Java"));
        System.out.println("Size of HashSet : " + tech.size());
        if (tech.remove("PHP")) {
            System.out.println("PHP is removed, Size : " + tech.size());
        } else {
            System.out.println("PHP is not removed, Size : " + tech.size());
        }
    }
}

LinkedHashSetIterator.java – demonstrate the use of Iterator and ConcurrentModificationException

package com.javalatte.itcuties.setinterface;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class LinkedHashSetIterator {

    public static void main(String[] JavaLatte) {
        List<String> compNames = new ArrayList<String>();
        compNames.add("Dell");
        compNames.add("HP");
        compNames.add("Sony");
        compNames.add("Lenovo");
        compNames.add("Lenovo");

        //LinkedHashSet(Collection<? extends E> c)
        //Constructs a new linked hash set with the same elements as the specified collection.
        Set<String> tech = new LinkedHashSet<String>(compNames);

        System.out.println(tech);
        System.out.println("Size : " + tech.size());

        Iterator iter = tech.iterator();
        //This will throw ConcurrentModificationException exception as iterator
        //is alread created.
        tech.add("Test"); // comment it to excute 

        while (iter.hasNext()) {
            System.out.print(iter.next() + " ");
        }
        System.out.println();

    }
}

TreeSet

Class TreeSet<E>
E – the type of elements maintained by this set

The TreeSet is one of two sorted collections (the other being TreeMap). It uses a Red-Black tree structure, and guarantees that the elements will be in ascending order, according to natural order.

• The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.
• This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
• TreeSet will not allow null object. If you try to add null value i will be throw NullPointerException.

This implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.

The iterators returned by this class’s iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. (We’ll see this with example)

Examples:
TreeSetOrderDemo.java – demonstrate the ordering of TreeSet.

package com.javalatte.itcuties.setinterface;

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

public class TreeSetOrderDemo {

    public static void main(String[] JavaLatte) {
        //Constructs a new, empty tree set, sorted according to the 
        //natural ordering of its elements.
        Set<String> names = new TreeSet<String>();
        names.add("Charlie");
        names.add("Kumar");
        names.add("Cuties");
        names.add("Robert");
        names.add("Bill");
        names.add("William");

        //Notice the output of TreeSet would be in natural order
        System.out.println(names);

        Set<Integer> numbers = new TreeSet<Integer>();
        numbers.add(13);
        numbers.add(1);
        numbers.add(124);
        numbers.add(-10);
        //Notice the output of TreeSet would be in natural order i.e, numeric
        System.out.println(numbers);

    }
}

TreeSetComparator.java, TreeSetLengthComparator.java – demonstrate how to use comparator with TreeSet.

package com.javalatte.itcuties.setinterface;

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

public class TreeSetComparator {

    public static void main(String[] JavaLatte) {
        Set<String> str = new TreeSet<String>(new TreeSetLengthComparator());
        str.add("ABCDE");
        str.add("ABC");
        str.add("BC");
        str.add("G");
        str.add("GHIJKLK");
        str.add("ABD");

        //Output will be sorted according to the Comparator i.e, according to
        // length of the String
        System.out.println(str);

    }
}

package com.javalatte.itcuties.setinterface;

import java.util.Comparator;

public class TreeSetLengthComparator implements Comparator<String> {

    public int compare(String o1, String o2) {
        return o1.length() - o2.length();
    }

}

TreeSetBasicOperationDemo.java – demonstrate the basic methods of TreeSet.

package com.javalatte.itcuties.setinterface;

import java.util.TreeSet;

public class TreeSetBasicOperationDemo {

    public static void main(String[] JavaLatte) {
        TreeSet<Integer> integerSet = new TreeSet<Integer>();
        integerSet.add(100);
        integerSet.add(45);
        integerSet.add(454);
        integerSet.add(1);
        integerSet.add(5);
        integerSet.add(4);
        integerSet.add(453);
        integerSet.add(-5);
        integerSet.add(11);
        //output of TreeSet would be in natural order i.e, numeric
        System.out.println(integerSet);
        System.out.println();

        //Returns the first (lowest) element currently in this set.
        System.out.println("first (lowest) element : " + integerSet.first());
        System.out.println();

        //Returns the last (highest) element currently in this set.
        System.out.println("last (highest) element : " + integerSet.last());
        System.out.println();

        //Returns the greatest element in this set less than or equal to the 
        //given element, or null if there is no such element.
        System.out.println("greatest element <= 5 : " + integerSet.floor(5));
        System.out.println();

        //Returns the greatest element in this set strictly less than the 
        //given element, or null if there is no such element.
        System.out.println("greatest element < 5 : " + integerSet.lower(5));
        System.out.println();

        //Retrieves and removes the first (lowest) element, 
        //or returns null if this set is empty.
        System.out.println(integerSet);
        integerSet.pollFirst();
        System.out.println("After pollFirst : " + integerSet);
        System.out.println();

        //Retrieves and removes the last (highest) element, 
        //or returns null if this set is empty.
        System.out.println(integerSet);
        integerSet.pollLast();
        System.out.println("After pollLast : " + integerSet);

    }
}

Download this sample code here.