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 add, remove 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