Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
The moose likes Beginning Java and the fly likes How does set ensures uniqueness Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Java Interview Guide this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "How does set ensures uniqueness" Watch "How does set ensures uniqueness" New topic

How does set ensures uniqueness

Raj Kumar Bindal
Ranch Hand

Joined: Apr 15, 2006
Posts: 418
I tried looking code for Set and Hashset ,but from that i could not find out how set ensures duplicates elements are not present in it.Can someone tell.
Taariq San
Ranch Hand

Joined: Nov 20, 2007
Posts: 192
Generally the javadoc is easier to read than the code.

public boolean add(E e)

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

That's from HashSet.
Because HashSet allows a null element, it checks if there's already a null element if the new one is null. If it's not null, it uses the equals() method found in Object. That implementation returns true if the 2 references are the same and typically a class would override this method and check if the 2 instances are meaningfully equal.

Say your class SomeObject has a String or 2, it might compare each of those Strings using String's .equals() implementation.
Campbell Ritchie

Joined: Oct 13, 2005
Posts: 46437
HashSet uses a Map implementation, which I think is a HashMap; it inserts your value as the "K" in the Map and a "dummy" Object instance as the "V"; I think it is the same "V" throughout.
All you have to do in this instance is go through the Map and see whether it already contains the "K". If it hasn't, add it and return true; if it's already there return false.
Ilja Preuss

Joined: Jul 11, 2001
Posts: 14112
And the relevant code from HashMap.put is this (as of JDK 1.6):

The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Campbell Ritchie

Joined: Oct 13, 2005
Posts: 46437
Originally posted by Ilja Preuss:
And the relevant code from HashMap.put is this . . .
You can see it doesn't alter the key; in the case of a HashSet, the value is always a reference to the same "dummy" Object, so that doesn't actually change either. Its correct operation is however dependent on the equals() and hashCode() methods being overridden correctly.
I agree. Here's the link:
subject: How does set ensures uniqueness
It's not a secret anymore!