aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes equals() doesn't fail for 2 different strings of the same hashCode Pages 583, 584, 585 of SCJP6 Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "equals() doesn Watch "equals() doesn New topic
Author

equals() doesn't fail for 2 different strings of the same hashCode Pages 583, 584, 585 of SCJP6

Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
This is somewhat related to - Using Maps , on page 585

At the line marked //#1 below, shouldn't the overriden equals() in the Dog object return false?


About 1/2 of the code below is from the SCJP6 book and the other 1/2 is mine.



The outcome is the same if == is replaced with .equals in the Dog's overriden equals() method
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14688
    
  16

You are using the same object, the one you have stored in the Map. So, if you change it's name, the object in the Map, which is the same, will also have its name changed. Names will always match.

The outcome is the same if == is replaced with .equals in the Dog's overriden equals() method

Use equals()


[My Blog]
All roads lead to JavaRanch
Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
Hmm... in that case on line 43 in the above code, the output should have been "dogvalue" instead of null ? no?


d.name = "magnolia";
//8 characters - does not match hashcode
System.out.println(m.get(d));

---------------------
regarding using == or .equals in the the Dog's equals() override , I meant to say the output of the System.out.printlns don't change regardless of whether == or .equals is used
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14688
    
  16

The java.util.Map API states the following :
Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on a such a map.
Arka Guhathakurta
Ranch Hand

Joined: Mar 01, 2009
Posts: 46
Hi,
I have found a few issues that needs to be pointed out. Lets look at the hashCode() implementation. It returns the length of the String name. Hence the hashCode for abcd and mnop will be same allthough they are unequal. One principle is that if equals return true for two Objects then there hashCode() must also return similar values for the 2 objects. This principle is violated.
Another thing that I have found is that if you use equals() instead of "==" inside the equals() implementation will that make sense? I mean you are using the equals() method to override equals(). I am not sure if this will be recursive call or will it call the equals() of Object class.Note that equals of Object class does nothing other than simple equality test "==". I guess this explains why "==" results same as equals().


regards,
Arka
Ryan Beckett
Ranch Hand

Joined: Feb 22, 2009
Posts: 192
Arka,

Hence the hashCode for abcd and mnop will be same allthough they are unequal. One principle is that if equals return true for two Objects then there hashCode() must also return similar values for the 2 objects. This principle is violated.


That is a perfectly legal hash code implementation. If two unequal objects have the same hash value, when using a hash structure, searching becomes O(n) instead of O(1). Therefore, its inefficient. When two equal objects come back with different hash codes, the rules have been violated.

Another thing that I have found is that if you use equals() instead of "==" inside the equals() implementation will that make sense?


It's a good idea to use String.equals here, but '==' will also return the correct answer since we're not dealing with String objects.



In the code above, there are no String objects created. The constructor argument is placed in the String pool. And, if another Dog is created with the same argument, its name variable will reference the pre-existing literal in the pool. You'll notice that if we change the code, '==' will make Dog.equals return incorrect results.



Good luck.
Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
Christophe Verré wrote:The java.util.Map API states the following :
Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.


The above statement from the API probably explains why the Map value (instead of null) is being returned even when the Dog object's name variable is changed.

as in:



the map behaves differently in this case:


but if the hashCode of the name of the Dog object key stored in the Map does not match the name of the Dog object used to lookup the (key, value) then the map lookup fails the first test for mismatched hashCode ( even before the test for equals()) , that's why the output is null in this case




Christophe Verré wrote:A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on a such a map.
Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
Christophe Verré wrote:You are using the same object, the one you have stored in the Map. So, if you change it's name, the object in the Map, which is the same, will also have its name changed. Names will always match.


This is correct, I verified this by printing the actual key object in the map, each time after the key object's (Dog) name was changed.



The output of the above shows that whenever the d reference changes the name, the change is reflected in the Map's key.


I find it is very strange that this line of code (in the original code above) returns null


Since d is referencing to the exact same object that the Map's key is referencing, why does it return null?




Ruben Soto
Ranch Hand

Joined: Dec 16, 2008
Posts: 1032
I just wanted to add to this discussion that it might be a good idea, as already mentioned, to use String.equals(Object) in the Dog.equals(Object) code. String literals are interned automatically, but if you construct a Dog object in some other way than passing a String literal, you get into trouble:



All code in my posts, unless a source is explicitly mentioned, is my own.
Himalay Majumdar
Ranch Hand

Joined: Sep 28, 2008
Posts: 324
Yeah Ruben..it should be



SCJP 1.6, SCWCD 5.0, SCBCD 5.0 [loading..]
Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
Yes using .equals instead of == is definitely a best practice but, the goal of SCJP is to test on how the code behaves - thats why I just left == as it is in my original post , since it is also like this in the book.

The discussion on why .equals is better than == is very helpful.


Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
I'll just reply to my question about why setting d.name = "magnolia" ( a 8 character hash code) , makes the map not return
"dogvalue" but returns null.

The reason is because when the HashMap is created the keys are associated with hash buckets.

In this case the reference d is associated with hash bucket ( corresponding to hash code 4)

When d.name = "magnolia" is assigned, the key in the Map is still referencing to the same object as d,
and the value of d.name is still "magnolia" in the key, however the hash code has now changed to 8, but the key
is still associated with the hash bucket 4 , when the key changes the hashbucket does not change it remains 4,
that is why when the map tries to lookup the value it gets null because there's nothing in hashbucket 4

I didn't find this explanation in the java 6 API , but got this answer on a different forum.

I should have remembered how data structures work - from computer science college days - http://en.wikipedia.org/wiki/Hashtable
Himalay Majumdar
Ranch Hand

Joined: Sep 28, 2008
Posts: 324


I think this concept is clearly explained in K&B in a two step process. Pg 586

1. Hashbased Collections Hashcode is used as key to find the bucket.
2. And then the object in the bucket is found.

By setting..d.name = "magnolia", you are changing the hashcode from 4 to 8. So you are trying to search the object in a different bucket 8, which is obviously null.
Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
edit: Pages 585 and 586 do talk about this, but what they talk about is slightly different because they use a new Dog object ( and not the reference to the existing Dog object on the heap)

d.name = "magnolia";
that is System.out.println(m.get(new Dog("clover")));

as opposed to
d.name = "magnolia";
System.out.println(m.get(d));

which have different meanings

---------------------------------------------

I was reading this http://mindprod.com/jgloss/hashtable.html to understand more about HashMaps and Hashtables in java.

It appears that internally the Maps are rehashed when the load/capacity increases.

I guess at some unpredictable point (only when and if the load on the HashMap increases), the hash bucket for the key with d.name="magnolia" may change to correspond to 8, at that time the map would be able to return the value for this key.

But all this rehashing is unpredictable and only depends on the Map's load/capacity, it can't be relied upon, so it is not a good idea to change anything in the Map's key (object) after it has been inserted into the HashMap or Hashtable, because the value can't be retrieved in a predictable manner.

Himalay Majumdar
Ranch Hand

Joined: Sep 28, 2008
Posts: 324
Rehashing is usually performed internally to balance HashMap capacity with LoadFactor.

A Map with

2 buckets with 3 entries each, and
2 buckets with 1 entry each, and
default settings for HashMap (load factor = 0.75, capacity I think = 16)
will have

8 entries
Occupied capacity = 0.5
12 empty buckets

Now, if you add 4 entries you get to 12 entries, you have occupied capacity = 0.75, same as the load factor, so it will recalculate all the hashcodes(ReHashing), and create more buckets. It says the capacity is approximately doubled in the HashMap API, so you get

capacity = 32
load factor = 0.75 (no change)
occupied capacity = 0.375
size = 12 (as before)
empty buckets = anything between 20 and 31.

I dont think rehashing is part of the exam, just knowing hashcode searches for a bucket and equals searches for the object inside the bucket will do the trick.
Rashmi Jaik
Ranch Hand

Joined: Oct 04, 2008
Posts: 50
Himalay Majumdar wrote:

I dont think rehashing is part of the exam, just knowing hashcode searches for a bucket and equals searches for the object inside the bucket will do the trick.


It is not part of the exam.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: equals() doesn't fail for 2 different strings of the same hashCode Pages 583, 584, 585 of SCJP6