• 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

Is equals() meaningless for HashSets?

 
Ranch Hand
Posts: 1274
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I wondered what happens, if the equals method of a class always returns true, while the hashCode outputs a random int.
Clearly, the contract about equals and hashCode is violated. But why is it possible to add more than one of this objects?
In this example, you can even add one animal twice:


produces:
size:2
[ani905676, ani389047]

API says about Sets:

More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.


By the way: The same happens, if I change the equals return to false...

So how can this be?

puzzled,
Bu.
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you break the hashCode/equals contract for the key class, HashMaps and HashSets simply don't work. The result of calling any method on them is undefined; they are broken.

HashSets/Maps work by sorting keys into "buckets" using some function of their hashCode -- for example, using "hashCode % 10" would sort into ten piles. Then the equals() function is used to make key comparisons only within a single pile. If the pile-sorting step maps equal keys into different buckets -- as is likely in the scenario you describe -- then the equals comparison will never even be done between the two keys.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

By the way: The same happens, if I change the equals return to false...

So how can this be?



When you change the equals() to return false, then they are always different objects, so you can add as many as you like.

When you are returning a random hashcode, you are pretty much messing up the collection. The reason you can add more than one is because they are going into different buckets. And there is no reason to check whether two objects, in two different buckets, are equal or not.

Henry
 
Burkhard Hassel
Ranch Hand
Posts: 1274
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi ranchers,

Ernest Friedman-Hill posted November 29, 2006 11:39 AM

If the pile-sorting step maps equal keys into different buckets -- as is likely in the scenario you describe -- then the equals comparison will never even be done between the two keys.



and Henry Wong posted November 29, 2006 11:42 AM

The reason you can add more than one is because they are going into different buckets. And there is no reason to check whether two objects, in two different buckets, are equal or not.



Ah, yes!
I forgot that the hashCode / bucket step will be performed first. Before the equals. And with a 1 Mio : 1 chance, the bucket will contain only one animal.
If nothing else is in the bucket, then there will be no equals test at all. And the animal (presumably unique) added to the set.


Thanks for your replies,
Bu.
 
reply
    Bookmark Topic Watch Topic
  • New Topic