aspose file tools*
The moose likes Beginning Java and the fly likes Head First Java HashSet Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Head First Java HashSet" Watch "Head First Java HashSet" New topic
Author

Head First Java HashSet

Ivan Turner
Ranch Hand

Joined: Feb 27, 2012
Posts: 37
I don't understand how the HashSet class is allowing duplicates in this code. In the text, the output of the HashSet has duplicates! A Set in Java is unique, correct?

Thanks
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18887
    
    8

Yes, that's right. It can't contain two objects for which a.equals(b) is true. So if you see "duplicates", that means that they aren't duplicates in that sense. Perhaps you should review your implementation of the "equals(Object)" method of your SongBad class.
Ivan Turner
Ranch Hand

Joined: Feb 27, 2012
Posts: 37
Thanks for pointing me in the right direction. That wasn't obvious on pp 559. My new question is when and from where are these methods called? Is equals() as well as hashCoce() (provided the comment is removed) being overridden?
The equals method lives in java.lang.Object. I assume I'm overriding. hashCode() lives in the same place and returns a hash code value for the object. Am I correct? Is there anything you can add for clarity?

public int hashCode() {
return title.hashCode();
}

Oops, I believe this is explained on pp 561. But all input is appreciated!!
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18887
    
    8

You should be overriding equals(). Whether you are in fact doing that, of course we can't tell.

However if you're using the hashCode of "title" -- which I assume is the title of the song -- then your implementation of equals() should say that two songs are "equal" if and only if their titles are equal.

(Apparently you're assuming that anybody answering your question is going to have a copy of the book you refer to. You shouldn't assume that.)
Saurabh Pillai
Ranch Hand

Joined: Sep 12, 2008
Posts: 509
Ivan, UseCodeTags

When you add to HashSet it calls to equals method. http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add%28E%29

Can you show us your SongBad class?
Ivan Turner
Ranch Hand

Joined: Feb 27, 2012
Posts: 37
Saurabh Pillai wrote:Ivan, UseCodeTags

When you add to HashSet it calls to equals method. http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add%28E%29

Can you show us your SongBad class?

The whole enchilada!!!

Ivan Turner
Ranch Hand

Joined: Feb 27, 2012
Posts: 37
I added this print statement and uncommented hashCode()



and got this output:

[Pink Moon, Somersault, Shiva Moon, Circles, Deep Channel, Passenger, Listen, Listen, Listen, Circles]
[Circles, Circles, Deep Channel, Listen, Listen, Listen, Passenger, Pink Moon, Shiva Moon, Somersault]
true
true
true
[Listen, Circles, Somersault, Shiva Moon, Passenger, Pink Moon, Deep Channel]

Which is three less songs which are the duplicate songs. I'm surprised I didn't see false in my print statement.

I don't exactly understand what's going on here. The text says "If the add() method returns false, you know the new object was a duplicate of something already in the set.

I'm new and quick on the draw. I did some detailed reading on pp 561 and found something like this: "Override hashcode() with a custom version to make sure the objects have the same value. HashSet finds a matching hashcode for two objects, HashSet will call one of the object's equal() methods to see if these hashcode-matched objects really ARE equal."
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Saurabh Pillai wrote:
When you add to HashSet it calls to equals method


Only after calling hashCode(), and only if that leads it to a non-empty bucket.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Ivan Turner wrote:
I don't exactly understand what's going on here. The text says "If the add() method returns false, you know the new object was a duplicate of something already in the set.

I'm new and quick on the draw. I did some detailed reading on pp 561 and found something like this: "Override hashcode() with a custom version to make sure the objects have the same value. HashSet finds a matching hashcode for two objects, HashSet will call one of the object's equal() methods to see if these hashcode-matched objects really ARE equal."


I'm not sure what your question is, so I'll just give you a couple of key pointers.

  • equals() is for determining if two objects are "equal" by whatever that means for your particular class. In the simple case, it might just be that 2 objects are equal if they're of the same class and all their fields are equal. In other cases, it might be if they're both of some higher-level abstract type and they have some semantic equality defined in terms of that type, without regard for specific field values. For instance, if two objects both implement Set and both have equal elements, the two Sets are equal. One might be a HashSet and the other a TreeSet, so their fields will be totally different, and they're not the same class, but as long as they're both Sets and every elment in one is also present in the other, they're equal


  • hashCode() is like an overview or summary of an object that can be used to pick a smaller set out of a crowd for further comparison using equals. For instance, when a HashSet or HashMap looks up an object, first it uses its hashCode to find which bucket it's in, which it can do very quickly. Then, if we have a decent hashing function, we should have only a few items to search through and call equals() on looking for a match.


  • Putting the above two points together, we can conclude (and it is documented in hashCode()'s and/or equals()'s javadocs), that if two objects are equal, then they MUST have the same hashCode, but that two objects can have the same hashCode without necessarily being equal. That is, hashCode() does not provide unique values.


  • We can further conclude that we cannot use anything for computing hashCode() that isn't also used for equals(). If you use field X in hashCode() but not in equals(), then two objects for which equals() returns true may have different hashCode() values (due to different X values), which violates the contract and leads to incorrect behavior in hash-based data structures. Note that the reverse is not true. We can use a field in equals() but leave it out of hashCode(), although generally it's better not to, in order to get a better distribution of hashCode() values.


  • return 42; is a perfectly legal implementation of hashCode(), in terms of functionality. It will always produce correct results. Of course, it turns O(1) operations into O(n), and for large hash-based data structures, can make our code run so slowly as to be unusable. So don't actually do it, but do understand why it will "work".


  • Whenever we override one or the other of equals() and hashCode(), we should always override both. hashCode() is useless without equals() (or near enough as makes no difference), and, while equals() can be used without hashCode(), it's bad practice to override it alone and assume your class will always be used that way.


  • So, what is it you're still having trouble with?
    Ivan Turner
    Ranch Hand

    Joined: Feb 27, 2012
    Posts: 37
    Thanks Jeff. My original question was why the HashSet values weren't unique (generating duplicates). I was directed to remove the comments on the call to the hashCode method to get unique values. I decided to put a print statement in the equals() method and was expecting to see false but I saw true. I now understand when hashCode() had the same hash values it called equals() to test the values further with different criteria. Thank you again. Your post is useful.
     
    wood burning stoves
     
    subject: Head First Java HashSet