Sunday, July 14, 2013

Java Collections Framework Part 4 - Sets

This is the sixth part of the tutorial, and this link goes to the previous post  java collections framework part 3


A Set implements the interface java.util.Set, it has the same methods as those of the Collection interface.
Sets do not accept duplicate elements, if the add() method is called with an object that already is in the set it should return false. The elements of the set must have a good implementation of the equals() method.

There are different implementations of the Set interface they can have order, can be sorted, or neither this is they can be unordered and unsorted.


The class java.util.HashSet is an implementation of the Set interface, it is not sorted and it doesn't have an order. If the hashset is iterated it states that it does not guarantee that the order will remain constant over time.

The elements of this type of set must implement the the hashcode() and the equals() methods, this is because it is implemented as a hash table in which elements are stored at a position derived from their contents. So, Two elements are considered equal or duplicate if they return the same hash code from the hashcode() method and they return true from testing them with the equals() method.

The Set first gets the hash code from the element then places the element in a bucket of the hash table for that hash code, if the bucket already has an element then it tests for duplicity the elements with their equals().


In the previous example the Element class has two implementations of the hashcode() method one that uses the hashcode of its value attribute of type String and other that generates random integers, if the implementation that uses the String is used then the Set would not accept duplicate elements this is because same strings should generate the same hashcode so the ouptut with this implementation should not contain any duplicate element as this:
[3, 2, 1, 4]
But if the implementation that generates random integer is used then the Set would accept duplicate elements because it would be placing each element in a different bucket of its hash table, the output would be something like this:.
[3, 2, 1, 4, 1]


The class java.util.LinkedHashSet extends from the class HashSet and therefore is an implementation of the Set interface. LinkedHashSet is hash table and a doubly-linked list, it has an order, its iterators will return their elements in the order in which they were added.
The LinkedHashSet doesn't define any new method, it just adds the linked functionality to the HashSet class.


In the previous example the output should in the order in which the elements were added, so it should print this:
[ 6, 5, 3, 4, 1, ]


The class java.util.TreeSet is an implementation of the Set interface, it also implements the java.util.NavigableSet and java.util.SortedSet interfaces, it is an sorted collection and guarantees that the elements will be in ascending order, according to their natural order, or by a Comparator provided at set creation time, depending on which constructor is used.

The TreeSet class implements methods that help navigate the set, and some of these methods are:

ceiling(e): Returns the lowest element >= e
higher(e): Returns the lowest element > e
floor(e): Returns the highest element <= e
lower(e): Returns the highest element < e
pollFirst(): Returns and removes the first entry
pollLast(): Returns and removes the last entry
NavigableSet  descendingSet(): Returns a NavigableSet in reverse order


The example should print

The TreeSet class also has more methods that return section of its collection, some of this methods are:

NavigableSet headSet(e, b*): Returns a subset ending at element e and exclusive of e
NavigableSet tailSet(e, b*): Returns a subset starting at and inclusive of element e
NavigableSet subSet(s, b*, e, b*): Returns a subset starting at element s and ending just before element e

The collections that return this methods are backed collections, this means when an element is added to the original or to the backed collection, the new entries were automatically added to the other collection


The example should print
Set: [a, b, c, d, g]
Sub set: [c, d]
Set: [a, b, c, d, e, g]
Sub set: [c, d, e]
Note that the subset was modified and also the set is modified, this is because subset is a backed collection of the set.

Go to part 5

No comments:

Post a Comment