• Post Reply Bookmark Topic Watch Topic
  • New Topic

how do you implement the equality and hashCode method if the class has reference type members java?  RSS feed

 
Riaz Ud Din
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to implement the following example to override the equality and hashCode method if the class has reference type member. I do get the expected result "true" for equal and "false" for non-equal objects. But the print statement in the Circle's equal method is not executed when the objects values are not equal. I don't know what i am missing, though i get the equality result "false" as expected for non equal objects. Thanking you all in advance.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Riaz Ud Din wrote:I am trying to implement the following example to override the equality and hashCode method if the class has reference type member. I do get the expected result "true" for equal and "false" for non-equal objects. But the print statement in the Circle's equal method is not executed when the objects values are not equal. I don't know what i am missing, though i get the equality result "false" as expected for non equal objects. Thanking you all in advance.


With a hashing collection, the equals() method is only needed/called if the hashing lands the objects into the same bucket. If the hash codes are different, then the objects are different, so there is no need to check objects in different buckets for equality.

In your example, the contains() method likely hashed the object to an empty bucket, so obviously, the instance is not contained in the collection.

Henry
 
J. Kevin Robbins
Bartender
Posts: 1801
28
Chrome Eclipse IDE Firefox Browser jQuery Linux MySQL Database Netbeans IDE
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For some reason you had an opening code tag but no closing tag, so I fixed that for you.

Welcome to the Ranch!
 
Riaz Ud Din
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Henry Wong thanks very much. It explains every thing...
 
Riaz Ud Din
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@ J. Kevin Robbins Thanks. i didn't notice, there are some opening and closing tags.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Riaz Ud Din wrote:I am trying to implement the following example to override the equality and hashCode method...

Slightly off-topic, but your hashCode() method seems a bit tortuous to me. It's possible that all those multiplies give it a slightly better "spread", but if it was me, I think I'd have just done both the same way (x ^ (y*37)). HashSet/HashMap also "mangles" your hashcode in order to work out a bucket index, so too much "massaging" of a hashcode could (if you're very unlucky) actually have the opposite effect to the desired one.

Another (very geeky) point: some compilers can optimize multiplication of a number x by known (usually small) Mersenne/Fermat primes (2ⁿ±1) like 17 or 31 (but not 37), because it's simply a shift + ±x.

Normally, I wouldn't mention it, but since hashCode() can potentially be used a LOT, it's sometimes worth considering.

Winston
 
Campbell Ritchie
Marshal
Posts: 56585
172
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you have got that utility method why not use it? Your two primitives will be automatically boxed to Integer objects and their hash code methods called. It probably starts from 0, using 0 for nulls and the result of a hashCode call for non‑nulls, multiplying by 31 after each addition.
 
Riaz Ud Din
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Winston Gutkowski , @Campbell Ritchie. Thanks very much for your feed back. I really appreciate it. I am new to java and your feed back is really very helpful.
I checked the system generated hashcode were quite big and mine were very small, that's why i used the big number, but now after knowing its side effect, i will be careful.
Campbell Ritchie its really a good idea to use the hash code util, i didn't know about that... Thanking you guys once again...
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Riaz Ud Din wrote:I checked the system generated hashcode were quite big and mine were very small, that's why i used the big number...

And your instincts (AFAIK) are correct. There are some well-known large primes that work very well as "bit manglers" when used as multipliers, but you don't need to overdo it. Don't forget that for something like a String, you might have to repeat the process many times, which is why hash functions are often benchmarked on strings; and multiplication is quite a bit slower than XOR or addition.

However, it IS micro-optimisation which, as anyone will tell you, is "the root of all evil" - and a perfectly valid alternative may be to "cache" the hash value (ie, only calculate it when needed; otherwise have hashCode() simply return the calculated value). Then you don't have to care so much about the "efficiency" and can concentrate on making it really good.

Winston
 
Campbell Ritchie
Marshal
Posts: 56585
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Remember how hash codes are used by hash‑based collections. You use the hash code (hereinafter called the int h) and the capacity (int c) which is the length of an array. You start with an array length c and if you fill the collection, double the size of the array. Start with c being an exact power of 2, e.g. 1, 2, 4, 8, 16, 32. I think 16 is common. You work out the index in the array with the bitwise and operator:-
array[h & c - 1] = value;
Remember that − has a higher priority than &.

In the case of a HashSet or a HashMap, the type of value is probably a Map.Entry. The & operator has a disadvantage over %:-
  • It will only give an even distribution of outputs if c is an exact power of 2.
  • … and two advantages:-
  • 1: It never gives a negative result if c ≤ 2³⁰
  • 2: It can probably be executed much faster, in one clock cycle.
  • Now, try it out with different sizes of array. You find that with the smallest array which has different elements at all (c == 2), that a difference of 1 in h will guarantee the two values go in different locations. You will find that the biggest difference you can imagine (−)2³¹ will never put your values in different places in the array, however large your array.

    So when it comes to hash codes,
    Less is more and more is less.
    A difference of 1 has no less effect on the collection than a larger difference, and larger differences may have less effect! So the biggest difference you can have between hash codes is 1! And (−)2³¹ is the smallest difference!
    That is why you try to get the variability into the least‑significant bits in the hash code. If you use a 16‑element array as the default in your hash‑based collection, then any difference at all in the lowest four bits (b₂₈…b₃₁) will guarantee the values go in difference array indices.

    By the way: where did you find that hash algorithm? Why are you using composite numbers in it?
     
    Campbell Ritchie
    Marshal
    Posts: 56585
    172
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Riaz Ud Din wrote: . . .
    I checked the system generated hashcode were quite big and mine were very small, that's why i used the big number, . . .
    I have explained why I don't quite agree with Winston on that one. With hash codes, it is quite possible that
    Small is Beautiful
    And, “You're welcome ” Interesting discussion.

    Cached hash codes are only reliable for immutable objects. You can calculate the hash code in the constructor and store it as a field, or store it the first time it is requiredThere is a 1 in 2³² chance that the hash code really will be 0 and will have to be calculated every time!

    You are allowed small hash codes:-
    System.out.printf("%h%n", Integer.valueOf(1));
     
    Winston Gutkowski
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:Cached hash codes are only reliable for immutable objects...

    As are hashed collections, which is the main use for the hashCode() method to begin with. The only way to guarantee that a mutable object will work in a hashed collection is to have its hashCode() method return a constant - which, of course, defeats the whole purpose of a hash code. It will work correctly though.

    However, there is another reasonable use for a hash calculation: as the "first cut" of an equality check.

    This is based on the premise that calculating a hash is generally a LOT quicker than comparing fields; so If you have a complex object, comparing all its fields to see if they're "the same" as another's could be quite a lengthy process.
    If, on the other hand, you have a hashcode method that, let's say, takes a quarter of the time, your equals() method can simply compare hashcodes first, and only go on to compare fields if they are equal. And if your hashcode method is good, the chances of it returning equal hashcodes for non-"equal" objects should be very low - so, Bingo: you have an equals() method that basically works 4 times [*] as fast for the addition of one check.

    For that reason, if I'm writing a mutable class, I will often have its hashCode() method return a constant (personally, I like this.getClass().hashCode()), and add an equalityHash() method that does a more "traditional" calculation.

    But not everyone will agree with me on this one, I'm sure...

    Winston

    [* edit] That should be "twice as fast", since hashCode() has to be called twice.
     
    S Majumder
    Ranch Hand
    Posts: 349
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Riaz ,


    When you open the HashSet implementation of the add() method in Java Apis that is rt.jar , you will find the following code in it:

    So , we are achieving uniqueness in Set,internally in java through HashMap . Whenever you create an object of HashSet it will create an object of HashMap .
    As Wong told contains() method put the object in an empty bucket that's why Circle'r equals() is not being called.

    If I add this :


    The object will try to go the same bucket location that the previous object stored and here the equals() method gets called.

    Hope you understand .

    Thanks,
    Satya


     
    Riaz Ud Din
    Ranch Hand
    Posts: 34
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    By the way: where did you find that hash algorithm? Why are you using composite numbers in it?

    I just came up with that hash algorithm, after reading an example in a java book (Java SE 7 Programmer II (1Z0-804 exam) By S G Ganesh and Tushar Sharma).
    I never thought of composite no., it was just a random no. though in the example prime no. was recommended.
    Thank you guys. I am really glad that i post this question on Java Ranch, it helped me a lot to understand hashcode much better than before.
     
    Campbell Ritchie
    Marshal
    Posts: 56585
    172
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You're welcome; it has made for an interesting discussion
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!