In Java, a Set cannot contain two unique objects where as a List doesn't have that restriction. What is the mechanism in a Set which identifies unique objects. Most probably it might be the implementation of the equals method or hashCode method or both of the objects which are being added. Does anyone know what's the actually mechanism of identifying unique objects. Is it the equals method, hashcode method or both the methods or something else ?
2 Answers
It depends on the Set implementation. For HashSet and LinkedHashSet, it uses both equals and hashCode methods. For TreeSet, it uses the natural Comparator of the object or a specific provided Comparator.
Basically, the Set javadoc explains this (emphasis mine):
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.
The Set interface places additional stipulations, beyond those inherited from the Collection interface, on the contracts of all constructors and on the contracts of the add, equals and hashCode methods.
TreeSet has another behavior since it implements SortedSet (this interface extends the Set interface). From its javadoc (emphasis mine):
A Set that further provides a total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order.)
Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface (See the Comparable interface or Comparator interface for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method.
Comments
HashSet Source: seems the elements are stored as keys in a HashMap (which requires unique keys) and the put method in HashMap checks the following:
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
So it compares both the hash and runs equals.
TreeSet uses a TreeMap to back its data and TreeMaps put uses a comparator.
1 Comment
Luiggi Mendoza
This source code probably won't be compatible for other JVM implementations like JRockit or IBM's JVM.