Introduction to Sets in java

A Set is a Collection that cannot contain duplicate elements. Set models the mathematical set abstraction. The Set interface contains no methods other than those inherited from Collection. It adds the restriction that duplicate elements are prohibited. Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set objects with different implementation types to be compared meaningfully. Two Set objects are equal if they contain the same elements.

Operations on SortedSet

The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:

• The Iterator returned by the iterator operation traverses the sorted set in order.
• The array returned by toArray contains the sorted set’s elements in order.

Although the interface doesn’t guarantee it, the toString method of the JDK’s SortedSet implementations returns a string containing all the elements of the sorted set, in order.

ConcurrentSkipList class in java

There are two new interfaces in Java 6 SE called “NavigableMap” and “NavigableSet” which facilitate navigating through collections. NavigableSet extends SortedSet and is implemented by TreeSet and concurrentSkipListSet (a new class in Java collection).
ConcurrentSkipListSet is one of the class that implements NavigableSet and it is used to return the closest matches of elements. It includes methods to return iterators in ascending and descending orders, as well as methods that return a sorted or navigable set for a special portion of data.

NavigableSet nset = new ConcurrentSkipListSet();

nset.add("20");

nset.add("60");

nset.add("50");

nset.add("40");

nset.add("30");

nset.add("80");
// Returns an iterator over the elements in navigable set, 
//in ascending order.
Iterator iterator = nset.iterator(); 

//set in ascending order

while (iterator.hasNext())

{ //Ascending order list

    System.out.print(iterator.next() + " ");

}

//Descending order list

System.out.println("In descending order : " + nset.descendingSet() + "\n");
//remove element
nset.pollLast();

Range-view Operations on SortedSet

The Range-view operations are somewhat analogous to those provided by the List interface, but there is one big difference. Range-views of a sorted set remain valid even if the backing sorted set is modified directly. This is feasible because the endpoints of a range view of a sorted set are absolute points in the element-space, rather than specific elements in the backing collection (as is the case for lists). A range-view of a sorted set is really just a window onto whatever portion of the set lies in the designated part of the element-space. Changes to the range-view write back to the backing sorted set and vice-versa. Thus, it’s OK to use range-views on sorted sets for long periods of time (unlike range-views on lists). Sorted sets provide three range-view operations. The first, subSet takes two endpoints (like subList). Rather than indices, the endpoints are objects. They must be comparable to the elements in the sorted set (using the set’s Comparator or the natural ordering of its elements, whichever the set uses to order itself). Like subList the range is half-open, including its low endpoint but excluding the high one.
Thus, the following one-liner tells you how many words between “doorbell” and “pickle”, including “doorbell” but excluding “pickle”, are contained in a SortedSet of strings called dictionary:

int count = dictionary.subSet("doorbell", "pickl

See also post –Operations on SortedSet

Standard Constructors for SortedSet interface

By convention, all Collection implementations provide a standard constructor that takes a Collection, and SortedSet implementations are no exception. This constructor creates a SortedSet object that orders its elements according to their natural order. Additionally, by convention, SortedSet implementations provide two other standard constructors:

• One that takes a Comparator and returns a new (empty) SortedSet sorted according to the specified Comparator.
• One that takes a SortedSet and returns a new SortedSet containing the same elements as the given SortedSet, and sorted according to the same Comparator (or using the elements’ natural ordering, if the specified SortedSet did too). Note that the compile-time type of the argument determines whether this constructor is invoked in preference to the ordinary Set constructor, and not the runtime type!

The first of these standard constructors is the normal way to create an empty SortedSet with an explicit Comparator. The second is similar in spirit to the standard Collection constructor: it creates a copy of a SortedSet with the same ordering, but with a programmer-specified implementation type.

Operations on SortedSet

The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:

• The Iterator returned by the iterator operation traverses the sorted set in order.
• The array returned by toArray contains the sorted set’s elements in order.

Although the interface doesn’t guarantee it, the toString method of the JDK’s SortedSet implementations returns a string containing all the elements of the sorted set, in order.

See also post – RangeView operations on SortedSet

Set implementations in java

Being a Collection subtype all methods in the Collection interface are also available in the Set interface.
Since Set is an interface you need to instantiate a concrete implementation of the interface in order to use it. You can choose between the following Set implementations in the Java Collections API:

• java.util.EnumSet
• java.util.HashSet
• java.util.LinkedHashSet
• java.util.TreeSet

Each of these Set implementations behaves a little differently with respect to the order of the elements when iterating the Set, and the time (big O notation) it takes to insert and access elements in the sets

HashSet class in java

Introduction

• Set interface implemented using a hash table
• doesn’t guarantee to iterate the elements in any specific order
• constant time access to elements assuming good hash
  function

HashSet class Constructors

HashSet is implemented with an underlying HashMap. In addition to implemented the Set interface methods, HashSet has the following constructors.

Result	Constructor	Description
hset =	new HashSet()	Creates a new HashSet with default initial capacity 16 and load factor 0.75.
hset =	new HashSet(initialCapacity)	Creates a new HashSet with the specified initial int capacity.
hset =	new HashSet(initialCapacity, loadFactor)	Creates a new HashSet with the specified capacity which will not exceed a specified (float) load factor.
hset =	new HashSet(coll)	Creates a new HashSet with elements from the Collection coll

TreeSet class constructors in java

Introduction

• Set interface implemented as a tree
• Iterator return elements in natural order (see later)

Constructors of TreeSet Class

TreeSet implements the Set and SortedSet interface methods. TreeSet is implemented with an underlying TreeMap (balanced binary tree). If the element type has a natural order (eg, String) elements will be ordered by that, but often you will supply a Comparator object that tells how two elements compare. It has the following constructors.

Result	Constructor	Description
tset =	new TreeSet()	Creates new TreeSet. Elements sorted by natural order.
tset =	new TreeSet(comp)	Creates new TreeSet using Comparator comp to sort elements.
tset =	new TreeSet(coll)	Creates new TreeSet from Collection coll using natural ordering.
tset =	new TreeSet(sset)	Creates new TreeSet from SortedSet smp using element ordering from sset.

SortedSet interface methods in java

The SortedSet interface is used by TreeSet and adds additional methods to reflect that a TreeSet is sorted.

SortedSet sset;

Result	Method	Description
comp =	sset.comparator()	Returns Comparator used to compare elements. null if natural ordering used (eg, String).
obj =	sset.firstKey()	First element (in sorted order).
obj =	sset.lastKey()	Last element (in sorted order).
sset =	sset.headMap(obj)	Returns SortedSet of all elements less than obj.
sset =	sset.tailMap(obj)	Returns SortedSet of all elements greater than or equal to obj.
sset =	sset.subMap(from, to)	Returns SortedSet of all elements greater than or equal to from and less than to.