• 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
  • Tim Cooke
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Liutauras Vilda
  • Henry Wong
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Mikalai Zaikin
  • Himai Minh

need algorithm for tuple comparison

 
Ranch Hand
Posts: 145
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have a tuple class:



I want to override the hashCode method such that it gives a distinct value. However, if num1/num2 are interchanged it should return the same value for the hash code.

example if, if the hash code is n, then when and , the hash code should be n.
BUT
if and then hash code should be m where n!=m

I don't have the brains to find an algorithm to implement this If anybody can give me an algorithm, I would appreciate it.
Thanks.

PS. this is not a student assignment or anything. I was asked this in a job interview question and I still don't have the answer, that is why I am posting it.
 
Marshal
Posts: 27286
87
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


Mathew Kuruvilla wrote:BUT if... then hash code should be m where n!=m



It's not necessary for objects which aren't equal to have different hash codes, so that requirement is not necessary. And in your example, if the hash code must be based on two integers then since the hash code is an integer there must be two unequal objects which have the same hash code no matter what calculation you use.
 
Bartender
Posts: 1845
10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Okay.
This is java ranch, so we expect you to at least TRY before you get the answer.

So what is your best guess?
Do you have any ideas of what this hashcode method should look like?
What any hashcode method should look like?

 
Mathew Kuruvilla
Ranch Hand
Posts: 145
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Some combination of the comparing the product of the numbers in addition to the comparing the squares of the two numbers might be good enough.
I didn't think of that earlier. Hope that is good enough ....
 
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

Mathew Kuruvilla wrote:I want to override the hashCode method such that it gives a distinct value. However, if num1/num2 are interchanged it should return the same value for the hash code.


Just as an additional point, you'd better make absolutely sure that Tuple.equals() ALSO doesn't care which order the values are - ie:
  Tuple.of(3,4).equals(Tuple.of(4,3))
MUST return true.

Winston
 
Bartender
Posts: 5021
186
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Winston
Why? As Paul writes, if T(3, 4) is unequal to T(4,3), then their hashcodes need not be different.

My advice is: let your IDE come up with some good hashcodes. As soon as you override the equals-method, it will suggest a hashcode function too. Have a look at what it suggests, then you have some idea about how it can be done.
 
Winston Gutkowski
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

Piet Souris wrote:@Winston
Why? As Paul writes, if T(3, 4) is unequal to T(4,3), then their hashcodes need not be different.


Very true. My mistake.

Winston
 
Piet Souris
Bartender
Posts: 5021
186
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nothing to be ashamed for...

At least for one hour after I sent in my reply, I was wondering if I was correct. Well, if two objects are equal, then their hashcodes MUST be equal. No doubt about that.
Does that mean that, if the hashcodes MUST be equal (as wished by OP), then the objects MUST also be equal? This is complicated stuff, with all these necessary and/or sufficient conditions...

But all this is nothing compared to what it takes to get a Comparator<Map.Entry<K, V>> for a Map<K, V> that compares first on values, then on keys. Just completed it, took me more that two hours...
Easy once you know how, nearly impossible if you don't.
 
Winston Gutkowski
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

Piet Souris wrote:Nothing to be ashamed for...


Thanks, but I should know better.

Oddly enough, for Mathew's specific case, it might actually make sense for equals() to make the distinction, since there are only two possible variants of a Tuple with the same values, which theoretically means that each bucket in a hashed collection might contain two objects. But no more (hopefully).

Winston
reply
    Bookmark Topic Watch Topic
  • New Topic