equals and hashcod methods in java

Hi,

I am going through below link

http://www.programcreek.com/2011/07/java-equals-and-hashcode-contract/

I have not understood below lines
1. If two objects are equal, then they must have the same hash code.
2. If two objects have the same hashcode, they may or may not be equal.

The idea behind a Map is to be able to find an object faster than a linear search. Using hashed keys to locate objects is a two-step process. Internally the Map stores objects as an array of arrays. The index for the first array is the hashcode() value of the key. This locates the second array which is searched linearly by using equals() to determine if the object is found.

The default implementation of hashCode() in Object class returns distinct integers for different objects. Therefore, in the example above, different objects(even with same type) have different hashCode


In this example, a green apple object is stored successfully in a hashMap, but when the map is asked to retrieve this object, the apple object is not found.

i also did not get why green apple did not found.

Please advise
LVL 7
gudii9Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

gurpsbassiCommented:
Because the hashCode() method was not overriden.
0
dpearsonCommented:
The way a hashmap works is it takes the object - runs the "hashCode()" method to get a number and then uses that number as the index for where to put the object in the map.

Remember my analogy about how a hashmap is like a library?  This number tells it which shelf in the library to look at.

If you don't override hashCode() then the map can get confused and end up looking on the wrong shelf when it tries to find your object and so it fails to find it.

Any help?

Doug
0
gudii9Author Commented:
The idea behind a Map is to be able to find an object faster than a linear search. Using hashed keys to locate objects is a two-step process. Internally the Map stores objects as an array of arrays. The index for the first array is the hashcode() value of the key. This locates the second array which is searched linearly by using equals() to determine if the object is found.

please elaborate more on above
0
Fundamentals of JavaScript

Learn the fundamentals of the popular programming language JavaScript so that you can explore the realm of web development.

gudii9Author Commented:
in the example above, different objects(even with same type) have different hashCode.

also please elaborate on above

The way a hashmap works is it takes the object - runs the "hashCode()" method to get a number

runs the "hashCode()" on the object that is taken?(in this example Apple object??)

please advise
0
gudii9Author Commented:
Remember my analogy about how a hashmap is like a library?  This number tells it which shelf in the library to look at.

i remember analogy trying to relate with this code Apple example class.

hashCode is to find the number of the rack to put the book in library shelf

equals is to confirm if i get the right rack number inside the library shelf putting actual book (or Apple object)

please advise
0
dpearsonCommented:
Yes that's right.

For an actual hashmap - hashCode() tells the map which "bucket" to put the object into - where a bucket is usually a linked list of items.

Then "equals" is used to check the items in the "bucket" (list) to see if any of them match exactly.

If the hashCode function is missing it ends up checking the wrong list.
If the equals function is missing it ends up unsure about whether 2 items match.

So you always need to implement both together.

Doug
0
zzynxSr. Software engineerCommented:
So you always need to implement both together.
... and make sure that if your equals() method returns true for a given object (the parameter), then your hashCode() method returns the same result for those two objects.

The idea behind a Map is to be able to find an object faster than a linear search.
A linear search is: starting at the start of the list and traversing the complete list and checking if there is a match with each item you encounter. (= in the library you check all shelves to find the book you're looking for)
In case of a map you use the hashCode() value to limit your search. (=in the library you only have to check one shelf, because you know - due to the way the books are stored - that your book is for sure NOT on the other shelves.)
0
gudii9Author Commented:
Then "equals" is used to check the items in the "bucket" (list) to see if any of them match exactly.

i have not understood this point, when we look for match. please advise
0
dpearsonCommented:
If you break apart a hashmap it works basically like this:

Object get(Object key) {
   // Retrieve the list of items associated with this specific hash code
   int hashcode = key.hashCode() ; 
   List<Object> keys = getBucket(hashcode) ;

   // Check each one to see if it matches exactly with the key you passed in
   for (Object k : keys) {
      if (k.equals(k)) {
           Object value = getValue(k) ;
           return value ;
      }
   }
   return null ;
}

Open in new window


So first it uses hashCode() to figure out which list of items to check.
Then it uses equals() on each one.

The efficiency in the hashmap comes from the fact it has many lists of items.  It doesn't check them all - just the one that matches the hashcode.  But hashcodes are not unique, so 2 different keys can have the same hashcode, so it still has to do an "equals" check on each one once it finds the list.

Does that make sense now?

Doug
0
gudii9Author Commented:
import java.util.HashMap;
 
public class Apple {
	private String color;
 
	public Apple(String color) {
		this.color = color;
	}
 
	public boolean equals(Object obj) {
		if (!(obj instanceof Apple))
			return false;	
		if (obj == this)
			return true;
		return this.color.equals(((Apple) obj).color);
	}
 
	public static void main(String[] args) {
		Apple a1 = new Apple("green");
		Apple a2 = new Apple("red");
 
		//hashMap stores apple type and its quantity
		HashMap<Apple, Integer> m = new HashMap<Apple, Integer>();
		m.put(a1, 10);
		m.put(a2, 20);
		System.out.println(m.get(new Apple("green")));
	}
}

Open in new window


above link code generated below output

null


It is due to non implementation of hashCode() method,

whne i implemented equals() and hashCode() using eclipse option (i got warnings as attached not sure why??)

import java.util.HashMap;
 
public class Apple {
	private String color;
 
	public Apple(String color) {
		this.color = color;
	}
 
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((color == null) ? 0 : color.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Apple other = (Apple) obj;
		if (color == null) {
			if (other.color != null)
				return false;
		} else if (!color.equals(other.color))
			return false;
		return true;
	}
 
	public static void main(String[] args) {
		Apple a1 = new Apple("green");
		Apple a2 = new Apple("red");
 
		//hashMap stores apple type and its quantity
		HashMap<Apple, Integer> m = new HashMap<Apple, Integer>();
		m.put(a1, 10);
		m.put(a2, 20);
		System.out.println(m.get(new Apple("green")));
	}
}

Open in new window


i got correct output as below
10

i do see different hashCodes for Green Apple and OtherColor apple as attached
warningEclipse.png
warningEclipse2.png
warningEclipse3.png
0
gudii9Author Commented:
But hashcodes are not unique, so 2 different keys can have the same hashcode, so it still has to do an "equals" check on each one once it finds the list.

why they are not uniques.

if i have two sting objects with jubled character like "amy" and "may"

both have same hashCode right.(please correct me if i am wrong??) . Making hashCode unique would have avoided lot of issues right. not sure why it was not made unique. please advise

Does hashCode related to memory(since string immutable both above string objects point to different memory location)
0
zzynxSr. Software engineerCommented:
You shouldn't make your hashCode() method more difficult than needed. (and use what java gives you)

Since, all you want is taking into account the color attribute, you can just keep your method as simple as this:

    @Override
    public int hashCode() {
        return color.hashCode();
    }

Open in new window


if i have two sting objects with jubled character like "amy" and "may", both have same hashCode right.
Wrong.
Just add these lines in your main method an see it for yourself:
        System.out.println("may : " + "may".hashCode());
        System.out.println("amy : " + "amy".hashCode());
        System.out.println("yam : " + "yam".hashCode());

Open in new window


why they are not uniques.
It depends on how the hashCode() is generated, but uniqueness cannot always be guaranteed. (which is no problem, since hashCode() ànd equals() are both used)

A good article to read is: The 3 things you should know about hashCode()
(where you can read that "Aa" and "BB" have the same hash code 2112
Try it out yourself:
        System.out.println("Aa : " + "Aa".hashCode());
        System.out.println("BB : " + "BB".hashCode());

Open in new window

)
0
dpearsonCommented:
Making hashCode unique would have avoided lot of issues right. not sure why it was not made unique. please advise

That's a very reasonable question.  There's 2 reasons hashCode can't be unique.

First it's an integer and there are only 2^32 of those.  That's a big number, but it's a finite set and there are an infinite number of possible strings you can create.  Each string has to map to the same hash code each time you run the hashCode() method so you've got an infinite number of things mapping to a finite number of values.  This means they can't each get a unique code - some (in fact an infinite number of them) will share the same hash codes.

(In case that's a little hard to understand, imagine a much simpler case.   Say you are trying to map 20 things to 10 unique values - you can see it's not possible to give each one a unique value.  Same idea).

So it's just not possible - because hash code has a finite size.

On top of that, remember the hash code is used to select the "bucket" (or shelf) where the values are stored.
This is usually done by something like this:

int bucket = hashCode() % number_buckets ;

This way a hash map doesn't need to have 1 bucket for every possible hash code (all 2^32 of them).
It can decide to say only have 1,000 buckets and still use the hashCode() to figure out which bucket to look in.

So that's why hashCode() isn't unique.

But really a very good question to ask.

Doug
0
gudii9Author Commented:
Do not use hashCode in distributed applications
Moreover, you should be aware that the implementation of a hashCode function may change from one version to another. Therefore your code should not depend on any particular hash code values. For example, your should not use the hash code to persist state. Next time you run the application, the hash codes of the “same” objects may be differen

can please elaborate on this
0
gudii9Author Commented:
his phenomenon is called the Birthday paradox.

please elaborate on this as well.

I like the picture in the link

http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/

which shows different hashCodes() for each rack or bucket which could have different object like A , A and U etc

so equals() method looks for those A, A, U to get the match to put some other object back to same rack/bucket with that hashCode right?
0
zzynxSr. Software engineerCommented:
>> Do not use hashCode
>> can please elaborate on this
Base line: don't write code that makes decisions based on the value hashCode() returns.
The result of hashCode() is intended to be used by java's hash algorithm as already explained.
Don't use that result for anything else is the main message.

>> his phenomenon is called the Birthday paradox.
>> please elaborate on this as well.
All information you need is in the article and the link to wikipedia. I can't explain it any better.
0
dpearsonCommented:
The birthday paradox is explained in detail here:
http://betterexplained.com/articles/understanding-the-birthday-paradox/

It's basically just the chance that 2 people in a group will have the same birthday.  Turns out you don't need a very big group.

The application to hashCodes is the chance of 2 objects having the same hashCode is larger than you might expect.

Doug
0
gudii9Author Commented:
is library shelf/rack/cell is same as bucket..i am confused with word bucket in many literatures. please advise
0
dpearsonCommented:
Yes that's right.  The term "bucket" is the normal one used for hash maps.

Objects are placed into a bucket based on the hashcode and then you search through the bucket to find the specific matching value.

It's not a great analogy because I never met anyone who stores real things in buckets...
0
gudii9Author Commented:
then uses that number as the index for where to put the object in the map.

Map is key value based collection right. only list, set deals with index right?
when you say
uses that number as the index
you mean key? please advise

Is this hashCode() applicable to List, Set, Queue and also Map interface derived classes. please advise
0
dpearsonCommented:
Map is key value based collection right. only list, set deals with index right?
when you say
uses that number as the index
you mean key? please advise

Yes that's right - only things like lists that have an order can be looked up by index.  I was using "index" in the more general sense here - like the index at the back of a book which you use to find an entry inside the book.

But yes you're right that only lists have index methods.
And they don't require objects put into them to implement hashCode().

(Sets on the other hand don't have order and do require hashCode() - you can see it in the name of a typical Set implementation which is HashSet).

Doug
0
gudii9Author Commented:
Yes that's right - only things like lists that have an order can be looked up by index.

List has the insertion order right as they allow duplicates. Set do not have the insertion order as they do not allow duplicates. But sorted set has the default order(if numerical ascending if sting a to z right) or custom order using comparator right?

How about queue and stack do they also use index?

Map do not have order or index right as they are different beasts dealing with key and values righ does not even fall under collection interface?


can you please advise on my post ID: 40740424 as well i think i need clarity on that


At a glance hashmap related classes uses hashing related data structures which creates specific hashCode for each object to identify specific object quickly in the bag of objects using the hasCode right. and equals(0 to double check the object is same one while picking object from bag(hasMap of group of collection object) of objects
0
dpearsonCommented:
How about queue and stack do they also use index?
Not really because for queues and stacks they're designed so you can only add things and take them off from the ends, not in the middle.

At a glance hashmap related classes uses hashing related data structures which creates specific hashCode for each object to identify specific object quickly in the bag of objects using the hasCode right. and equals(0 to double check the object is same one while picking object from bag(hasMap of group of collection object) of objects

Yes that's a sign you've got a good grasp on hashmaps.

Doug
0
zzynxSr. Software engineerCommented:
can you please advise on my post ID: 40740424 as well i think i need clarity on that
On what aspect of that post exactly do you need clarity?
0
gudii9Author Commented:
import java.util.HashMap;
 
public class Apple {
	private String color;
 
	public Apple(String color) {
		this.color = color;
	}
 
	public boolean equals(Object obj) {
		if (!(obj instanceof Apple))
			return false;	
		if (obj == this)
			return true;
		return this.color.equals(((Apple) obj).color);
	}
 
	public static void main(String[] args) {
		Apple a1 = new Apple("green");
		Apple a2 = new Apple("red");
 
		//hashMap stores apple type and its quantity
		HashMap<Apple, Integer> m = new HashMap<Apple, Integer>();
		m.put(a1, 10);
		m.put(a2, 20);
		System.out.println(m.get(new Apple("green")));
	}
}

Open in new window


above code resulted null . why it is returning null

As attached when i used eclipse option and generated code for equals() and hashCode() i got code like below

import java.util.HashMap;
 
public class Apple {
	private String color;
 
	public Apple(String color) {
		this.color = color;
	}
 
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((color == null) ? 0 : color.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Apple other = (Apple) obj;
		if (color == null) {
			if (other.color != null)
				return false;
		} else if (!color.equals(other.color))
			return false;
		return true;
	}
 
	public static void main(String[] args) {
		Apple a1 = new Apple("green");
		Apple a2 = new Apple("red");
 
		//hashMap stores apple type and its quantity
		HashMap<Apple, Integer> m = new HashMap<Apple, Integer>();
		m.put(a1, 10);
		m.put(a2, 20);
		System.out.println(m.get(new Apple("green")));
	}
}

Open in new window

i got warning saying equals selected already then  gave option to select color.
i did selected. when i ran
i got below out put
10
why i got 10 .

i wonder why.

also i see equals() changed from below to

public boolean equals(Object obj) {
            if (!(obj instanceof Apple))
                  return false;      
            if (obj == this)
                  return true;
            return this.color.equals(((Apple) obj).color);
      }

below

@Override
      public boolean equals(Object obj) {
            if (this == obj)
                  return true;
            if (obj == null)
                  return false;
            if (getClass() != obj.getClass())
                  return false;
            Apple other = (Apple) obj;
            if (color == null) {
                  if (other.color != null)
                        return false;
            } else if (!color.equals(other.color))
                  return false;
            return true;
      }

please advise what is the difference.
0
gudii9Author Commented:
Here is attachment
eclipseOption.png
0
dpearsonCommented:
above code resulted null . why it is returning null

Because you forgot to implement hashCode().  Remember you must implement both hashCode() and equals() for hashMaps to work correctly.

why i got 10 .
Because Eclipse added both equals and hashCode, so now the map works correctly and you get back the value matching a green apple - just as you should.

please advise what is the difference (between 2 equals).
The two equals methods are almost equivalent.  The main difference is that the first (shorter) one doesn't work correctly if the color property is null or the other object being tested is null.  In those situations you'll get an exception.  The second one will handle a null correctly for the color or when testing if x.equals(null) for some x.

Beyond that the differences are largely stylistic.

Doug
0
gudii9Author Commented:
The two equals methods are almost equivalent.  The main difference is that the first (shorter) one doesn't work correctly if the color property is null or the other object being tested is null.  In those situations you'll get an exception.  The second one will handle a null correctly for the color or when testing if x.equals(null) for some x.

Beyond that the differences are largely stylistic.

public boolean equals(Object obj) {
if (!(obj instanceof Apple))
return false; 
if (obj == this)
return true;
return this.color.equals(((Apple) obj).color);
}

below

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Apple other = (Apple) obj;
if (color == null) {
if (other.color != null)
return false;
} else if (!color.equals(other.color))
return false; 
return true;
} 

Open in new window


how to begin to understand above code. for me the the similarity or difference is not obvious. please advise



if (this == obj)
return true;
if (obj == null)
return false;

I got above code


what is meaning of below code

if (getClass() != obj.getClass())
return false;
Apple other = (Apple) obj;
if (color == null) {
if (other.color != null)
return false;
} else if (!color.equals(other.color))

also i am not clear on below code

if (!(obj instanceof Apple))
return false;
if (obj == this)
return true;
return this.color.equals(((Apple) obj).color);

why there are 2 return statements. and what is happening in above code.
0
dpearsonCommented:
I think you lost all of the indenting...making it pretty hard to read.

// Check if classes match
if (getClass() != obj.getClass())
    return false;

Apple other = (Apple) obj;

// Check to see if this object has a null color.
// If so, then the other object must be null as well.
if (color == null) {
   if (other.color != null)
      return false;
} else {
     // If this one's color is not null, then we can compare the two colors
     // to see if they are equal.  If they're not, then the objects are not equal
      if (!color.equals(other.color)) {
         return false; 
      }
}

// If we get here then the two colors are equal (or both null)
// and so the objects match
return true;
} 

Open in new window


It's pretty complicated code to write - which is why we usually just let our IDEs do it for us.

Doug
0
gudii9Author Commented:
sure.

public class TestClass {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		  System.out.println("may : " + "may".hashCode());
	        System.out.println("amy : " + "amy".hashCode());
	        System.out.println("yam : " + "yam".hashCode());

	}

}

Open in new window


is generating different hashCodes  as below which is expected

may : 107877
amy : 96717
yam : 119397
0
gudii9Author Commented:
/*	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((color == null) ? 0 : color.hashCode());
		return result;
	}
	*/


why eclipse choose 31 and made more complicated code when we can write simple code as below

	
/*	 @Override
	    public int hashCode() {
	        return color.hashCode();
	    }*/

Open in new window

0
dpearsonCommented:
why eclipse choose 31 and made more complicated code when we can write simple code as below

Again - the difference is what happens when 'color' is null.  In the simple version you get an exception (can't call color.hashCode() when color is null).  In Eclipse's version it works correctly.

Doug
0
zzynxSr. Software engineerCommented:
why eclipse choose 31 and made more complicated code when we can write simple code as below
The answer is explained here: https://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
zzynxSr. Software engineerCommented:
Thanx 4 axxepting
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.