Saturday, December 13, 2014

Sets: HashSet, TreeSet and LinkedHashSet

Summarized from http://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/ 


A Set contains no duplicate elements. There are three commonly used implementations of Set" HashSet, TreeSet and LinkedHashSet. 

Set interface extends Collection interface. In a set, no duplicates are allowed. If a duplicate element is inserted, the original element will be removed from the set. 

HashSet is implemented using a hash table (beautiful invention!). Elements are not ordered. The add, remove and contains methods have O(1) complexity. 

TreeSet is implemented using a tree structure. The elements in a set are sorted. The addremove and contains methods have O(log(n)) complexity. It offered methods to deal with ordered set like first(), last(), headSet(), tailSet(), etc. 

To define a class, because TreeSet is sorted, the corresponding object need to implement java.lang.Comparable's compareTo()

class XXX implements Comparable<Dog>
{
...
public int compareTo(Object o)
{
...
}
}

And the output of the object will be ordered. 

LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table with a linked list running through it, so it provides the order of insertion. The time complexity of basic methods is O(1)

No comments:

Post a Comment