This week's book giveaway is in the Cloud forum.
We're giving away four copies of Terraform in Action and have Scott Winkler on-line!
See this thread for details.
Win a copy of Terraform in Action this week in the Cloud forum!
  • 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:
  • Tim Cooke
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Rob Spoor
  • Bear Bibeault
Saloon Keepers:
  • Jesse Silverman
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Al Hobbs
  • salvin francis

HashMap Key

 
Ranch Hand
Posts: 162
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In a HashMap, following are the required things:

1) if k1.equals(k2) == true then k1.hashcode() == k2.hashcode() should be true;

This is because hash code decides the bucket which is to be hit. Equals selects the element within a bucket. So if equals() says true, hash code must be same.

2) if k1.hashCode() != k1.hashCode() then k1.equals(k2) should be false.

If the buckets aren't same, i realise that there cannot be two equal objects. So k1 and k2 equals is false.

Just to increase my clarity over the matter, I'm thinking that if two hashCode() are unequals, their buckets are always different. But why should it be mandatory to have k1.equals(k2) as false? Shouldn't it be optional?


-333
 
Sheriff
Posts: 22510
122
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

amol deshpande wrote:Just to increase my clarity over the matter, I'm thinking that if two hashCode() are unequals, their buckets are always different.


They can be different. If there are just 10 buckets available, there are bound to be objects with different hash codes in each bucket. In an ideal world there is one bucket for each hash code, but that would mean there would be need for 2^32 buckets

But why should it be mandatory to have k1.equals(k2) as false? Shouldn't it be optional?


From a logical point of view, A => B implies !B => !A. In normal words: if A is true, then B must be true. So if B is false, A could never have been true, or B would be true as well.

In this case, k1.equals(k2) => k1.hashCode() == k2.hashCode(). Therefore, if !(k1.hashCode() == k2.hashCode()) (or simply put, k1.hashCode() != k2.hashCode()), k1.equals(k2) must return false.


If k1.hashCode() == k2.hashCode() then k1.equals(k2) can return either true or false. Since there are only 2^32 unique hash codes available there is bound to be some collision. And the following example is a perfectly legal (but terrible) hashCode() implementation:
Equality is based on == (inherited from Object), but the hashCode() will always return 42. Therefore, for all instances k1 and k2 of MyObject, k1.hashCode() == k2.hashCode() will be true.
 
author
Posts: 23909
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

Just to increase my clarity over the matter, I'm thinking that if two hashCode() are unequals, their buckets are always different. But why should it be mandatory to have k1.equals(k2) as false? Shouldn't it be optional?



IMHO, these two rules are just the same rule, worded differently (okay, it's debateable).

Anyway, if rule two is optional, meaning equality is optional -- then you'll break rule one, is it would be possible to have k1 equal to k2, and have different hashcodes.

Henry
 
amol deshpande
Ranch Hand
Posts: 162
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Good thought.

My thought went on these lines....

If we have two keys k1 and k2 such that we want them to be treated same by hashing, then we need
2 conditions for them satisfy our needs....1 ) they should pass equals method test...2) they should have same hashCode() results.

But when I have two keys here k1 and k2 such that at k1.hashCode() is never equal to k2.hashCode(), these are anyway not going to be same in the eyes of hashing....so why the requirement of equals == false.

Second rule is like first stated with NOT gate applied. So i'll burn this in the brain .... I'm thinking that if k1.hashCode() != k2.hashCode(), there exists no change that k1 and k2 will be treated same by hashing even if k1.equals(k2) = true.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic