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

[Rashmi Jaik]

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.

  

import java.util.*;

class Dog{

	public Dog(String n ){ name = n; }
	public String name;

	public boolean equals(Object o){

		if((o instanceof Dog) &&
				(((Dog)o).name == name)){
			//Notice above, == is used 

			return true;
		}else{
			return false;
		}

	}

	public int hashCode(){ return name.length();}

}

class MapTest2{

	static public void main(String[] args){

		Map<Object, Object> m = new HashMap<Object, Object>();

		Dog d = new Dog("clover");
		//reference d is pointing to Dog("clover")
		//hashcode value is 6

		m.put(d, "dogvalue");

		System.out.println(m.get(d));
		//Existing reference
		//output - dogvalue
		System.out.println(m.get(new Dog("clover")));
		//New object
		//output - dogvalue


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

		d.name = "arthur";
		//6 characters - matches hashcode
		//doesn't fail equals() !
		System.out.println(m.get(d)); // #1
		//ouput - dogvalue ( Doesn't fail Dog's equal test - even though the names are different, why?
		System.out.println(m.get(new Dog("clover")));
		//ouput - null 

	}

}


  

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

[Christophe Verré]

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()

[Rashmi Jaik]

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é]

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]

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().

[Ryan Beckett]

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.

 public Dog(String n ){ name = n; }
	public String name;   

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.

 	public Dog(String n ){ name = new String(n); }
	public String name;   

Good luck.

[Rashmi Jaik]

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:

d.name = "arthur";
System.out.println(m.get(d));
//output - dogvalue

d.name = "123456";
System.out.println(m.get(d));
//output - dogvalue

d.name = "abcdef";
System.out.println(m.get(d));
//output - dogvalue

//All of the above d.name have the same length as "clover"

the map behaves differently in this case:

d.name = "arthur";
System.out.println(m.get(new Dog("clover")));
//output - [b]null[/b]

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

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

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]

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.

  

Set<Object> keySet = hashMap.keySet();
Iterator<Object> keyIt = keySet.iterator();

while(keyIt.hasNext()){
        Dog dog = (Dog)keyIt.next();
        System.out.println("key hashCode() = " + dog.hashCode());
        System.out.println("key equals() = " + dog.equals(b));
        System.out.println("dog name = " + dog.name);
}

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

  
d.name = "magnolia";
System.out.println(m.get(d));
//prints null - instead of dogvalue
//if both d and the map's key are pointing to the same object
//it should not return null  

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

[Ruben Soto]

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:

class Dog{

        public Dog(String n ){ name = n; }
        public String name;

        public boolean equals(Object o){

                if((o instanceof Dog) &&
                                (((Dog)o).name == name)){
                        return true;
                }else{
                        return false;
                }

        }

        public int hashCode(){ return name.length();}

}

public class DogTest {
   public static void main(String[] args) {
      Dog d1 = new Dog("test1");
      Dog d2 = new Dog("test1");

      System.out.println(d1.equals(d2)); // Output is "true"

      StringBuffer sb1 = new StringBuffer("1tset");
      StringBuffer sb2 = new StringBuffer("tes");
      sb2.append("t1");
      sb1.reverse();
      Dog d3 = new Dog(sb1.toString());
      Dog d4 = new Dog(sb2.toString());

      System.out.println(d3.equals(d4)); // Output is "false"
   }
}

[Himalay Majumdar]

Yeah Ruben..it should be

public boolean equals(Object o){   
  
                if((o instanceof Dog) &&   
                                (((Dog)o).name.equals(name))){   
                        return true;   
                }else{   
                        return false;   
                }   
  
        }   

[Rashmi Jaik]

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]

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]

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]

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]

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]

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.