hashMap table hashCode equals

Hi,

I am trying below example
http://www.enterjava.com/search?updated-min=2015-01-01T00:00:00%2B05:30&updated-max=2016-01-01T00:00:00%2B05:30&max-results=6

why hashMap has table inside that. what is table is it is hashTable.
How the bucket is assigned when we add more than 3,4 employee objects. More the hash code bigger the bucket it gets in hash map table?

Some times i see same bucket occupied by say employee2 is replaced by later employee3? why it happens like that?
sometimes i see only 2 or objects out of all 4 as below
[null, Employee [id=2, name=Tom2]=second, null, null, null, Employee [id=4, name=Tom4]=fouth, null, Employee [id=3, name=Tom3]=third, null, null, null, null, null, null, null, null]

As attached why it is showing only 3 objects not the fourth object for below code

package OverrdideHashCode;
import java.util.HashMap;

/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
 private int id;
 private String name;

 public Employee(int id, String name) {
  super();
  this.id = id;
  this.name = name;
 }
 public int getId() {
  return id;
 }
 public void setId(int id) {
  this.id = id;
 }
 public String getName() {
  return name;
 }
 public void setName(String name) {
  this.name = name;
 }
 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + id;
  result = prime * result + ((name == null) ? 0 : name.hashCode());
  return result;
 }
 @Override
 public String toString() {
  return "Employee [id=" + id + ", name=" + name + "]";
 }
}
public class Demo1 {
 public static void main(String[] args) {
  HashMap<Employee, String> map = new HashMap<Employee, String>();
  Employee emp1 = new Employee(1, "John1");
  Employee emp2 = new Employee(2, "Tom2");
  Employee emp3 = new Employee(3, "Tom3");
  Employee emp4 = new Employee(4, "Tom4");
  map.put(emp1, "first");
  map.put(emp2, "second");
  map.put(emp3, "third");
  map.put(emp4, "fouth");
  System.out.println(map);
 }
}

Open in new window



From the above output it is clear that even though the contents of the both objects are same and hashcode is also same , they are added in same bucket. The problem here is both the objects are added. The reason is that the Object class has the equals implementation which checks the address and as these are two different objects they are different.

i wonder how it added both objects(Tom2, John1) to same bucket as attached ?

Also why they choose HashMap  value as same name field of employee class? Is it not confusing? it it done usually done like that?
I thought HashMap value should be something different than object second field name.

  Employee emp1 = new Employee(1, "John1");
  Employee emp2 = new Employee(2, "Tom2");
  Employee emp3 = new Employee(3, "Tom3");
  Employee emp4 = new Employee(4, "Tom4");
  map.put(emp1, "first");
  map.put(emp2, "second");
  map.put(emp3, "third");
  map.put(emp4, "fouth");


when i override both equals and hashcode as below

package overrideBothEqualsHashCode;

import java.util.HashMap;

/**
 * 
 * @author Ganesh.Rashinker
 * 
 */
class Employee {
	private int id;
	private String name;

	public Employee(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + id;
		result = prime * result + ((name == null) ? 0 : name.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;
		Employee other = (Employee) obj;
		if (id != other.id)
			return false;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Employee [id=" + id + ", name=" + name + "]";
	}
}

public class Demo1 {
	public static void main(String[] args) {
		HashMap<Employee, String> map = new HashMap<Employee, String>();
		Employee emp1 = new Employee(1, "John1");
		Employee emp2 = new Employee(1, "John1");
		map.put(emp1, "first");
		map.put(emp2, "second");
		System.out.println(map);
	}
}

Open in new window


i got below output

{Employee [id=1, name=John1]=second}


what is meaning of above output?
second has first?


Now you can see that only one object has been added.

Conclusion:
It is neccessary to override equals and hashcode function for the class which is added as key in HashMap.

i have not clealu understoodr conclusion ?
also what it mean by only one object added

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.

krakatoaCommented:
Conclusion:
It is neccessary to override equals and hashcode function for the class which is added as key in HashMap.


i have not clealu understoodr conclusion ?
also what it mean by only one object added

We dealt with this entire question in your previous gigantic question about the same topic, and the answers have not changed since then.

Here is a (badly drawn) diagram of how HashMap and TreeMap handle hashCode() and equals()

HashMap handling of hashCode() and equals()

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
gudii9Author Commented:
As attached why it is showing only 3 objects not the fourth object for below code

  Employee emp1 = new Employee(1, "John1");//missing in debug console
  Employee emp2 = new Employee(2, "Tom2");
  Employee emp3 = new Employee(3, "Tom3");
  Employee emp4 = new Employee(4, "Tom4");
  map.put(emp1, "first");
  map.put(emp2, "second");
  map.put(emp3, "third");
  map.put(emp4, "fouth");
please advise
krakatoaCommented:
I don't appear to have any problem with the output. When I run the Employee class, I get this printed out to my console :

C:\EE_Q_CODE>java Employee
{Employee [id=1, name=John1]=first, Employee [id=2, name=Tom2]=second, Employee
[id=3, name=Tom3]=third, Employee [id=4, name=Tom4]=fouth}
Determine the Perfect Price for Your IT Services

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden with our free interactive tool and use it to determine the right price for your IT services. Download your free eBook now!

gudii9Author Commented:
import java.util.HashMap;

/**
 * 
 * @author Ganesh.Rashinker
 * 
 */
class Employee {
	private int id;
	private String name;

	public Employee(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + id;
		result = prime * result + ((name == null) ? 0 : name.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;
		Employee other = (Employee) obj;
		if (id != other.id)
			return false;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Employee [id=" + id + ", name=" + name + "]";
	}
}

public class Demo1 {
	public static void main(String[] args) {
		HashMap<Employee, String> map = new HashMap<Employee, String>();
		Employee emp1 = new Employee(1, "John1");
		Employee emp2 = new Employee(1, "John1");
		map.put(emp1, "first");
		map.put(emp2, "second");
		System.out.println(map);
	}
}

Open in new window


are you running above code?
i get below output

{Employee [id=1, name=John1]=second}

please advise
krakatoaCommented:
Well that is what you would expect, since, as you know, the second Employee (emp2), will overwrite the first one. Do you see that?
krakatoaCommented:
Employee emp1 = new Employee(1, "John1"); //make a new Employee called emp1
            Employee emp2 = new Employee(1, "John1");//make a new Employee called emp2 with the same field values as emp1
            map.put(emp1, "first");//put emp1 in the map
            map.put(emp2, "second");//put emp2 in the map. As it has the same values as emp1, it will overwrite it.
krakatoaCommented:
So replace that part with this slightly modified version below, and see the difference in the output.

Employee emp1 = new Employee(1, "John1");
            Employee emp2 = new Employee(2, "John1");
            map.put(emp1, "first");
            map.put(emp2, "second");

(IN my last comment, it should read that the two emps have the same keys, not the same values).

But in the Employee class you are using, hashCode and equals are overridden, and sono duplicates are permitted. If they were not overridden then your map would contain both of them.
gudii9Author Commented:
import java.util.HashMap;

/**
 * 
 * @author Ganesh.Rashinker
 * 
 */
class Employee {
	private int id;
	private String name;

	public Employee(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + id;
		result = prime * result + ((name == null) ? 0 : name.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;
		Employee other = (Employee) obj;
		if (id != other.id)
			return false;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Employee [id=" + id + ", name=" + name + "]";
	}
}

public class Demo1 {
	public static void main(String[] args) {
		HashMap<Employee, String> map = new HashMap<Employee, String>();
		/*Employee emp1 = new Employee(1, "John1");
		Employee emp2 = new Employee(1, "John1");
		map.put(emp1, "first");
		map.put(emp2, "second");*/
		
		//{Employee [id=1, name=John1]=first, Employee [id=2, name=Tom2]=second, Employee
		//		[id=3, name=Tom3]=third, Employee [id=4, name=Tom4]=fouth}
		
		Employee emp1 = new Employee(1, "John1");
        Employee emp2 = new Employee(2, "Tom2");
    	Employee emp3 = new Employee(3, "Tom3");
        Employee emp4 = new Employee(4, "Tom4");
        map.put(emp1, "first");
        map.put(emp2, "second");
        map.put(emp3, "third");
        map.put(emp4, "fourth");
		System.out.println(map);
	}
}

Open in new window


i got now
{Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fourth, Employee [id=3, name=Tom3]=third}
krakatoaCommented:
Well you would, wouldn't you, because they all have different id and name field values, and so when they are used as keys, they are all unique because hashCode and equals are overridden.

So now do this :

Employee emp1 = new Employee(1, "John1");
        Employee emp2 = new Employee(2, "Tom2");
          Employee emp3 = new Employee(2, "Tom2");
        Employee emp4 = new Employee(4, "Tom4");
        map.put(emp1, "first");
        map.put(emp2, "second");
        map.put(emp3, "third");
        map.put(emp4, "fourth");
            System.out.println(map);

and see what you get .. ... clue : the two Tom2 s are identical . . . and with hashCode and equals overridden, the Map will overwrite the first key/value entry with the second.
gudii9Author Commented:
i did not understand that link completely on what author trying ot say from demo1,2,3,4 w.r.t stack and single linked list. i guess i need to re-read few more times
gudii9Author Commented:
I am re-reading over and over. I wonder how attached code resulted in intersection point? please advise
a5.png
gudii9Author Commented:
equals and hashcode method
Why it is necessary to override equals and hashcode?

This is one of the popular interview question. So lets understand the same practically.
I have class Employee having id and name member variables and I am trying to put few Employee object as key in HashMap.
In this example I am not overriding hashcode and equals method.

Demo1:(Without hashcode and equals)


Possible Output 1:
{Employee [id=2, name=Tom2]=second, Employee [id=3, name=Tom3]=third, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth}
Possible Output 2:
{Employee [id=3, name=Tom3]=third, Employee [id=4, name=Tom4]=fouth, Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first}


From the above output it is clear that every time you execute the code , it will generate different hashcode for your objects and they will go in different buckets.
The hashcode implementation of Object class is native









Demo 2:(With hashcode and Without equals)


Output:
{Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth, Employee [id=3, name=Tom3]=third}
As we have overriden hashcode and the calculation of hashcode value is on the basis of id and name , everytime you execute it will generate the same hashcode and it will go in the same bucket.

Now lets try to understand why we need equals method.




Demo 3:(With hashcode and Without equals)
Output:
{Employee [id=1, name=John1]=second, Employee [id=1, name=John1]=first}

From the above output it is clear that even though the contents of the both objects are same and hashcode is also same , they are added in same bucket. The problem here is both the objects are added. The reason is that the Object class has the equals implementation which checks the address and as these are two different objects they are different.








Now lets override equals method.

Demo 4:(With hashcode and equals)

Output:
{Employee [id=1, name=John1]=second}



Now you can see that only one object has been added.

Conclusion:
It is neccessary to override equals and hashcode function for the class which is added as key in HashMap.





Demo 1 is cleare to me. what is difference between Demo2, and Demo3. Demo 4 output is not clear to me as above. please advise
krakatoaCommented:
This question has already been answered in this and other questions of yours concerning Maps.

And I made a diagram of the effect of equals and hashcode on my earlier comment in this question. Have you read it? What do you not understand in it?

And as CEHJ said in another question - just forget about 'buckets' (at least for now) - they are not going to help you understand how Maps work. And in other questions, Doug has outlined may times the analogy of books on library shelves, and the use of hashCode.

hashCode is just a rough place to look for something, and equals then does a test on that neighbourhood to see if it's the actual thing you are looking for. It's like a ZIP or postcode - one code covers several houses or buildings and the postman shoves the letter through the actual correct letterbox.
krakatoaCommented:
As for the intersection point, all that code does in your .png is to iterate through the Set to see where that data is equal to an existing node, achieved by evaluating the boolean that is returned from an attempted "add()" call.
gudii9Author Commented:
hashCode is just a rough place to look for something, and equals then does a test on that neighbourhood to see if it's the actual thing you are looking for. It's like a ZIP or postcode - one code covers several houses or buildings and the postman shoves the letter through the actual correct letterbox.

i like this analogy far bettter than any other explanation on hashCode i found till now.
:)
krakatoaCommented:
Well that *is* good to hear. Of course the under-the-hood stuff is deeper than that, but for a high-level language like Java you mostly, and primarily, "only" need to understand why the two methods are important (hashCode and equals() that is), and when you must override them - which in the case of using them as custom object keys, is important to get right, although not *always* easy.
gudii9Author Commented:
As for the intersection point, all that code does in your .png is to iterate through the Set to see where that data is equal to an existing node, achieved by evaluating the boolean that is returned from an attempted "add()" call.

why they used negation in the front as below

  if (!set.add(temp)) {

rather than without negation as below (which i thought should be)
  if (set.add(temp)) {//no negation in front
krakatoaCommented:
Because . . .

API lit:
"Returns: true if this set did not already contain the specified element"

. . .  so it would add the member if it is not already there, and return 'true' to tell you the job was done. So if it didn't add it, it means the member is already there - and that's your intersection.
gudii9Author Commented:
i understand hashCode and equals() high level concept. But with respect to this link example i have below questions. Please advise
equals and hashcode method
Why it is necessary to override equals and hashcode?

This is one of the popular interview question. So lets understand the same practically.
I have class Employee having id and name member variables and I am trying to put few Employee object as key in HashMap.
In this example I am not overriding hashcode and equals method.

Demo1:(Without hashcode and equals)


Possible Output 1:
{Employee [id=2, name=Tom2]=second, Employee [id=3, name=Tom3]=third, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth}
Possible Output 2:
{Employee [id=3, name=Tom3]=third, Employee [id=4, name=Tom4]=fouth, Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first}


From the above output it is clear that every time you execute the code , it will generate different hashcode for your objects and they will go in different buckets.
The hashcode implementation of Object class is native









Demo 2:(With hashcode and Without equals)


Output:
{Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth, Employee [id=3, name=Tom3]=third}
As we have overriden hashcode and the calculation of hashcode value is on the basis of id and name , everytime you execute it will generate the same hashcode and it will go in the same bucket.

Now lets try to understand why we need equals method.




Demo 3:(With hashcode and Without equals)//demo2 also says 'Demo 2:(With hashcode and Without equals)' how it is different from demo 2???
Output:
{Employee [id=1, name=John1]=second, Employee [id=1, name=John1]=first}

From the above output it is clear that even though the contents of the both objects are same and hashcode is also same , they are added in same bucket. The problem here is both the objects are added. The reason is that the Object class has the equals implementation which checks the address and as these are two different objects they are different.








Now lets override equals method.

Demo 4:(With hashcode and equals)

Output:
{Employee [id=1, name=John1]=second}



Now you can see that only one object has been added.//why only one object addedd??

Conclusion:
It is neccessary to override equals and hashcode function for the class which is added as key in HashMap.
krakatoaCommented:
But where are your questions?? You've just provided one huge quote.

WHY can't you look at the diagram I provided earlier? It *tells you* what the effects are of having or not having hashCode and equals.
gudii9Author Commented:
equals and hashcode method
Why it is necessary to override equals and hashcode?

This is one of the popular interview question. So lets understand the same practically.
I have class Employee having id and name member variables and I am trying to put few Employee object as key in HashMap.
In this example I am not overriding hashcode and equals method.

Demo1:(Without hashcode and equals)


Possible Output 1:
{Employee [id=2, name=Tom2]=second, Employee [id=3, name=Tom3]=third, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth}
Possible Output 2:
{Employee [id=3, name=Tom3]=third, Employee [id=4, name=Tom4]=fouth, Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first}


From the above output it is clear that every time you execute the code , it will generate different hashcode for your objects and they will go in different buckets.
The hashcode implementation of Object class is native









Demo 2:(With hashcode and Without equals)


Output:
{Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth, Employee [id=3, name=Tom3]=third}
As we have overriden hashcode and the calculation of hashcode value is on the basis of id and name , everytime you execute it will generate the same hashcode and it will go in the same bucket.

Now lets try to understand why we need equals method.




Demo 3:(With hashcode and Without equals)//demo2 also says 'Demo 2:(With hashcode and Without equals)' how it is different from demo 2???
Output:
{Employee [id=1, name=John1]=second, Employee [id=1, name=John1]=first}

From the above output it is clear that even though the contents of the both objects are same and hashcode is also same , they are added in same bucket. The problem here is both the objects are added. The reason is that the Object class has the equals implementation which checks the address and as these are two different objects they are different.








Now lets override equals method.

Demo 4:(With hashcode and equals)

Output:
{Employee [id=1, name=John1]=second}



Now you can see that only one object has been added.//why only one object addedd??

Conclusion:
It is neccessary to override equals and hashcode function for the class which is added as key in HashMap.
gudii9Author Commented:
i highligted my couple of questions as above. please advise
krakatoaCommented:
/demo2 also says 'Demo 2:(With hashcode and Without equals)' how it is different from demo 2???

OK. If you override hashCode(), you MUST override equals() as well. It's not any use doing one without the other. You already KNOW the reason for this, which is that hashCode() is the neighbourhood, and equals is the postman. Try getting letters delivered without one or other.

And the reason why, in answer to your second question, that there is then only one object added, is because when hashCode and equals() ARE overridden, that this stops duplicates being added to the Map.

If I could say also that going to other sites for further examples and help with all your questions is fine, but this site, especially in Java, offers one of the best line-ups of expert talent that you can wish for. You would be far better off concentrating on what CEHJ, Doug, ozo, mccarl, zzynx and kaufmed - and sometimes I - have to say about all these things . . . and here is a good example. Why, after what Doug has already rehearsed many times, are you still not happy to accept that all you have to do to use custom objects as keys, is to ensure you override hashCode and equals()? LOOK AT my diagram for the HashMap - see the effect of the flowchart on when you do, and when you do not, override hashCode and equals().
gudii9Author Commented:
/demo2 also says 'Demo 2:(With hashcode and Without equals)' how it is different from demo 3???

i made a typo in my question(please read as 3 instead of 3 as highlighted above). Let me re-read your comment which is more interesting here
that there is then only one object added, is because when hashCode and equals() ARE overridden, that this stops duplicates being added to the Map.
krakatoaCommented:
For the fourth time of asking : have you LOOKED AT my diagram??
gudii9Author Commented:
For the fourth time of asking : have you LOOKED AT my diagram??

yes..i took two printouts and pinned also in front of me. i am trying to understand that diagram too in complete way
gudii9Author Commented:
Demo 4:(With hashcode and equals)




since they overrideen  both equals and hashCode as below


@Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + id;
  result = prime * result + ((name == null) ? 0 : name.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;
  Employee other = (Employee) obj;
  if (id != other.id)
   return false;
  if (name == null) {
   if (other.name != null)
    return false;
  } else if (!name.equals(other.name))
   return false;
  return true;
 }



Based on your diagram No duplicates.
Output:
{Employee [id=1, name=John1]=second}

as they are trying to add duplicate value(John1)

 Employee emp1 = new Employee(1, "John1");
  Employee emp2 = new Employee(1, "John1");


which makes sense.



It is neccessary to override equals and hashcode function for the class which is added as key(in this case Employee) in HashMap.

So Demo4 is clear now.

And also Demo1 is also clear.

I have not able to find difference between Demo2 and Demo 3 yet?
Please advise
krakatoaCommented:
It is neccessary to override equals and hashcode function for the class which is added as key(in this case Employee) in HashMap.
krakatoaCommented:
I have not able to find difference between Demo2 and Demo 3 yet?
Please advise

In my opinion, Demos 2 and 3 are a waste of time for you now, because you know that using a custom object as a key requires equals and hashCode to be overridden. So the two Demo examples are only going to serve to take your mind back to a point which you already passed - so forget about them, and practice the overrides as they should be done - you don't need the other examples.
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.