• Post Reply Bookmark Topic Watch Topic
  • New Topic

need algorithm for tuple comparison  RSS feed

 
Ranch Hand
Posts: 145
  • Mark post as helpful
  • send pies
  • 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.
 
Sheriff
Posts: 22846
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • 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: 1840
10
  • Mark post as helpful
  • send pies
  • 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
  • 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: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • 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
 
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • 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: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • 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
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • 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: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • 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
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!