• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

What have I done that causes HashSet to permit the addition of a duplicate to itself?

 
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I created the following static inner class:



When I add a coordinate to a HashSet already containing the same coordinate, the HashSet adds it anyway. I debugged and found that the equals method of Coordinate is never actually used. In other words, equality of two coordinates is being assessed by some other means. Is this assessment fair? I have reason to say "no", because the @Overrides annotation isn't flagged by my IDE (implying that Coordinate's equals method does actually override the one in Object).

More generally, can the community help me identify why HashSet adds an existing coordinate?

EDIT: I read a post, which oferred that


The equals() documentations states (emphasis added):

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.



I factored in the comment given here by deleting my overriden equals method and falling back onto the equals() method supplied by Object. By using the original method, I reasoned, I could avoid having to redefine hashCode().

Even with this change, my HashSet still adds a duplicate to itself.
 
Marshal
Posts: 28245
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Show us the code which demonstrates what you mean by "a duplicate", then.

However you'd be better off just taking the advice from that other thread, and implementing a hashCode() method which returns equal values for objects which are equal according to your extremely sensible equals() method.
 
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you try to add an element a second time, the HashSet.add() method does nothing and returns false instead of true.


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.

Specified by:
add in interface Collection<E>
Specified by:
add in interface Set<E>
Overrides:
add in class AbstractCollection<E>
Parameters:
e - element to be added to this set
Returns:
true if this set did not already contain the specified element



As the previous poster as mentioned, you need to define the hashcode method as well.

You may want to have a look at this thread where the matter was discussed:
https://coderanch.com/t/654653/java/java/remove-specific-object-ArrayList

 
Aahan Agrawal
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This is the code that results in the addition of a duplicate:





Here, again, is my class for reference:



______________

Also, how should I construct a hashCode() method such that every unique coordinate returns a unique integer? Is there some mathematical function that, using both x and y, could return a distinct output for every distinct combination of x and y?

Some function of the form x^n + y^m comes to mind, but I'm not sure how to determine if this would map a unique int to every x and y?
 
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Aahan Agrawal wrote:

Also, how should I construct a hashCode() method such that every unique coordinate returns a unique integer? Is there some mathematical function that, using both x and y, could return a distinct output for every distinct combination of x and y?

Some function of the form x^n + y^m comes to mind, but I'm not sure how to determine if this would map a unique int to every x and y?



The goal of a hashcode is not to assign a unique value to every possible object. A perfect hashcode function would certainly do that, but the hashcode value is finite in size so can only have a finite number of values. In the general case an object can often have an infinite number of values. Take for example a String. In concept at least a string could be infinite in length. Implementation details will impose an arbitrary size (the maximum amount of memory available to store the string in, or restrictions on the maximum size of array available if it is backed by a character array), but in theory at least there is no such thing as the longest possible string. So there are inevitably going to be cases where two none-equal objects have to have the same hash code.

And if we look at your example specifically, you need to create a hash code based on two ints. In Java an int is 32-bits long, so it has 2^32 possible values. Therefore your coordinate system has 2^64 possible values. Now a hashcode is also an int, so it can only have 2^32 values. Each coordinate is going to have to share its hashcode with on average 2^32 other coordinates.

And this is backed up by the contract of equals() and hashcode() in object. Two equal objects must have the same hashcode, but there is no stipulation that two non-equal objects must have different hashcodes.

As to how to write a good hashcode function, a search in a search engine would explain it better than I ever could. However from my limited knowledge, something equivalent to x*31 + y should work. The key concept is introducing the prime number, specifically Mersene primes I believe.
 
Bartender
Posts: 2236
63
IntelliJ IDE Firefox Browser Spring Java Linux
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Also note that your equals() method violates the contract of Object.equals().Line 3 throws java.lang.NullPointerException while it should print false.
Line 4 throws java.lang.ClassCastException while it should print false.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Paweł Baczyński wrote:Also note that your equals() method violates the contract of Object.equals()...


Which is very important to read and understand - as is the one for Object.hashCode().

And I should warn you that neither of them are simple. Indeed, this excellent article warns us that:
    "The authors of a 2007 paper concluded that almost all implementations of equals() are faulty."
And that includes ones written by us supposed "experts". :-)

My suggestion: Before you go any further, read those contracts thoroughly, and come back if you have any questions about them.

Also: Look up the instanceof operator.

It's also worth noting that if you override equals(), you should also override hashCode(). It's not an absolute rule, but it's true so often that it's a good habit to get into.

HIH

Winston
 
Marshal
Posts: 79278
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Actually the general contract for Object#hashCode says it must return the same result from two objects returning true from equals, so maybe it is an absolute rule after all.
The hash code method is necessary for the correct behaviour of hash tables as used by HashSet, so if there is any incorrectness in equals or hash code methods the hash set, hash map or other type of collection class will not work correctly.

As well as the Odersky Spoon and Venners article which Winston has given you a link to, please read the appropriate part of Effective Java™ by Joshua Bloch (referenecs 1 and 5 of Odersky Spoon and Venners) and Angelika Langer's work: 1 2 (I think I have managed to find her work in English ‍). Although the three authors cover similar territory, there are features unique to each so it is worth reading all three.
 
Campbell Ritchie
Marshal
Posts: 79278
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote: . . . this excellent article[/url] warns us that:
    "The authors of a 2007 paper concluded that almost all implementations of equals() are faulty."
. . .

Unfortunately they do not give enough information to find that paper, so one cannot verify that assertion at the source. Angelika Langer is a bit more optimistic about equals() methods and lists some correct and incorrect implementations; you may need to follow that link to next section several times to find that piece.
 
She'll be back. I'm just gonna wait here. With this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic