Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

hashcode question  RSS feed

 
Marcus Deviln
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
import java.util.*;
class MapEQ {
public static void main(String[] args) {

Map<ToDos>, String> m = new ToDos("Monday");
ToDos t1 = new ToDos("Monday");
ToDos t2 = new ToDos("Monday");
ToDos t3 = new ToDos("Tuesday");
m.put(t1, "doLaundry");
System.out.println(m.size());
}}
class ToDos {
String day;
ToDos(String d) { day = d ;}
public boolean equals(Object o) {
return ((ToDos)o.day == this.day
}
// public int hashCode() {return 9;}
}

The book says as the code stands the output will be 3 and if the hashCode method is uncommented the output will be 2. Now I have only a basic understanding of hashcode. It is used to make it easier or quicker to find stuff in a collection. I get the overall mission of it. I do not however understand how the heck this code resulted in what it did. If you uncomment the hashcode then what calculation is done to arrive at this result or in the event you don't uncomment then precisely what is going on?
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, I assume this line:

is a typo for this line:

Because the code doesn't make sense otherwise (ToDos as far as I can see does not implement the Map<ToDos, String> interface).

That said:
HashMaps only allow unique Objects into the map. It bases that uniqueness on two things - first the hashCode() then the equals().

When you put an object in a a HashMap the HashMap distributes them into 'buckets' based on their hashCode(). Once in a bucket the Object is compared to other Objects in the same bucket based on their equals() method. When you do not override the hashCode() method then your ToDos inherit Object's hashCode() method, which pretty much assures that each ToDos has its own bucket. So each ToDos Object gets its own bucket, there are no other Objects in the bucket so each one is kept.

When you override the hashCode() and make it return a constant value, what do you think happens next?
 
Patricia Samuel
Ranch Hand
Posts: 300
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Marcus,

Kindly use the Code tag while pasting code on the forum. It helps us.

This questions is form K&B and you have not pasted the entire problem here. You forgot these lines

if you have read the explanation that says, if you don't uncomment the hashcode function, it would return the size = 3. Because all the object will be saved in different buckets and there is no way left to know whether these two are equals.

And when you uncomment hashcode it returns a constant value and making these three object eligible to be stored in a single bucket and now equal can check whether these are equals or not. t1= t2 based on "Monday" string. Hence map will store it only once. t3 will be stored as seperate object. So it returns size = 2 in this case.

Just to clear , (I hope you know it) - you can not have duplicate keys in the map. When it see monday twice as a key it saves it only once and last entry is preserved.

I hope it will clear you doubts. Please let us know if it does not help.

Cheers
Patricia
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Marcus Deviln wrote:
The book says as the code stands the output will be 3 and if the hashCode method is uncommented the output will be 2.


The book is wrong. As the code stands the contract for hashCode (defined in the API documentation to the Object class) is broken. This means the output is undefined.

How is hashCode broken? One of the rules for hashCode states that if two objects are equal when compared with the equals method then both must return the same hashCode. This is not the case. The objects held by t1 and t2 are equal if you compare them using equals (because they're both Monday objects) but they won't return the same hashCode as they should. Why do they return different hashCodes? It's because the original hashCode of Object is exectuted and this hashCode calculates the hashCode based on the object reference and since t1 and t2 hold different objects the hashCodes will be different. Or the hashCodes may be equal by pure chance because that can also happen even though it's unlikely.

This changes when you uncomment the hashCode method. Now you override the hashCode of Object and supply your own. This hashCode always returns 3 which is a valid hashCode because it doesn't break the hashCode contract. It's a stupid choise of hashCode but that's another story.

So as the code stands the output will be undetermined (for example 3 or something else like 1 or so) because the hashCode contract is broken. When hashCode is uncommented the hashCode contract is fixed and the behaviour of the Map is as defined. And this says that Map doesn't store doubles. If you enter Monday, Monday, Tuesday only the second Monday and Tuesday will stick. So 2 it is.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ulrika Tingle wrote:
The book is wrong. As the code stands the contract for hashCode (defined in the API documentation to the Object class) is broken. This means the output is undefined.


I think it is a little strong to say that the book is wrong. 1) the point of the example is to demonstrate that the hashCode contract is broken, and what the practical effects of that could be. 2) the API for Object's hashCode method says "As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects." To which you should be able to say, with 'reasonable practicality' that each of the 3 distinct Objects will have distinct hashCodes which will put them in distinct buckets, which makes it reasonably practical to say the example will give a size of 3.

It also isn't wrong to point out that this 'reasonably practical' assumption may not always hold true, there could be cases where the result is something other than 3. But I think that is a far different situation than saying the book is wrong.
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Luke wrote:
I think it is a little strong to say that the book is wrong.


I didn't just say the book was wrong. I qualified my statement by pointing out exactly what's wrong. When you insert objects with a broken hashCode in a hash based collection you just cannot predict how many objects will actually show up. And if the book gives the impression you can, it's wrong. Or not entirely correct if that sounds better.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ulrika Tingle wrote:
Steve Luke wrote:
I think it is a little strong to say that the book is wrong.


I didn't just say the book was wrong. I qualified my statement by pointing out exactly what's wrong.


Sorry about that, I must've misread.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!