can you please this doubt about hashcode()

[Kaleeswaran Karuppusamy]

in k&b in exam tips mentioned like this
------------------------------------------------------------------
In real-life hashing, it�s not uncommon to have more than one entry in a
bucket. Hashing retrieval is a two-step process.
1. Find the right bucket (using hashCode())
2. Search the bucket for the right element (using equals() ).
-----------------------------------------------------------------------

its makes me more confuse.please explain me

[Punit Singh]

Hashing means generating a int value for the object. Java has given hashCode() function you can override and write your algorithm to generate this int value.

HashSet, HashMap all Hash based collection uses hashCode() to store the objects.

suppose you have a class:

import java.util.*;
public class Person{
private String name;
 
public Person(String name){
this.name=name;
}
 
public int hashCode(){
return name.length();
}
 
public boolean equals(Object o){
return this.name.equals(((Person)o).name);
}

public String toString(){
return this.name;
}
public static void main(String args[]){
 
Map<Person,String> map=new HashMap<Person,String>();
 
Person p1=new Person("Punit");
Person p2=new Person("Kaleeswaran");
Person p3=new Person("Karuppasamy");
 
map.put(p1, "ranch hand Member # 184009");
map.put(p2, "ranch hand Member # 152434");
map.put(p3, "ranch hand Member # 152434");
System.out.println(p2 +" is "+map.get(p2));
}
}

Here I have written my algorithm to generate hashCode() that is the length of String name.

You can understand working of HashMap, HashSet etc using buckets.

Suppose you are a HashMap and you have lots of buckets at your home and you have assigned numbers to all the buckets suppose 25 buckets and you have assigned number from 1 to 25.
Now

map.put(p1, "ranch hand Member # 184009");

Now first of all you will take this p1 object and call
p1.hashCode();. Calling this code you will get value 5 as "Punit" length is 5. Then you will find bucket no 5 and put this p1 in that bucket.

same for p2 and p3. Thus p2 "Kaleeswaran" will be in bucket no 11 and p3 "Karuppasamy" will also be in bucket no 11.

no 5 bucket : p1("Punit");
no 11 bucket: p2("Kaleeswaran"), p3("Karuppasamy");

Now suppose anybody wants to know the p2's status on javaranch.com, then
he will ask you by calling your method get(p2).

like: map.get(P2);
System.out.println(p2 +" is "+map.get(p2));

What will you do?
1. you will take p2 object.
2. you will call p2.hashCode() and will get 11.
3. you will find bucket no. 11. But you see that bucket 11 has 2 objects, now you are confused which object to return which one is for p2?
4. But you have an idea. You have equals() method for rescue.
You will call p2.equals(p3_stored_in_bucket), and p2.equals(p2_stored_in_bucket).
5. You will find p2.equals(p2) return true, you will return "ranch hand Member # 152434" stored with key p2_stored_in_bucket.


[ December 19, 2008: Message edited by: punit singh ]
[ December 19, 2008: Message edited by: punit singh ]

[Mukesh Bhojwani]

Kaleeswaran,

Firstly, you need to understand the contract of implementing hashCode() method which is as follows:

1. The hashCode generated for a particular object should consistently return same value(Assuming no state information is updated mean while).

2. For the pair of objects, if the equals(Object o) method returns true then the hashCode method MUST return same value for both.

3. For the pair of objects, if the equals(Object o) method returns false then it is NOT REQUIRED that hashCode method return distinct value for both the objects. However for the efficient searching the hashCode method MUST return distinct value.

Now, consider the following case:
Below is the program which calculates the hashCode based on the cumulative sum of ASCII value. Which is many to one correspondence. Moreover, see it is legal by the above mentioned contract.

E.g.
"Hello" : 72 + 101 + 108 + 108 + 110 = 500
"eHello" :101 + 72 + 108 + 108 + 110 = 500

The above both are unequal but still lead to same hashCode. That means they will fall in different buckets. The map implementations forms some data structure which will resemble to this bucketing idea. So if there are 100 objects but evaluating them form only 5 unique hash codes, that means on an average 20 elements in each bucket so once the bucket has been identified, so for the searching process the crowd reduced from 100 to 20 only. Now the 20 elements will be iterated, and at any iteration if the equals method return true the found element will be returned, else null.

  
import java.util.*;
 
class MyKey
{
public static boolean isFind = false;
String key;
 
public MyKey(String key)
{
this.key = key;
}
 
public String getKey()
{
return this.key;
}
public boolean equals(Object o)
{
if(o instanceof MyKey)
{
MyKey myKey = (MyKey)o;
if(this.key.equals(myKey.key))
{
if(isFind)
{
System.out.println("Identified the Element!");
}
return true;
}
 
}
return false;
}
 
public int hashCode()
{
int hashCode = 0;
for(int i=0; i<this.key.length(); i++)
{
hashCode +=(int)this.key.charAt(i);
}
if(isFind)
{
System.out.println("HashCode is: "+hashCode);
System.out.println("Identified the Bucket!");
}
return hashCode;
}
 
}
 
public class Test
{
public static void main(String[] args)
{
MyKey myKey1 = new MyKey("Hello");
MyKey myKey2 = new MyKey("eHllo");
 
Map<MyKey, Object> map = new HashMap<MyKey, Object>();
 
//Put to the map
map.put(myKey1, new String("Object1"));
map.put(myKey2, new String("Object2"));
 
//Find the element
MyKey.isFind = true;
System.out.println("Find Process");
System.out.println("-------------------------------------");
System.out.println("The key is: \""+myKey1.getKey()+"\"");
System.out.println("The Element Found: " + map.get(new MyKey("Hello")));
System.out.println("-------------------------------------");
}
}
 
/*
Output of the Program:
 
Find Process
-------------------------------------
The key is: "Hello"
HashCode is: 500
Identified the Bucket!
Identified the Element!
The Element Found: Object1
-------------------------------------
 
*/

[ December 19, 2008: Message edited by: Mukesh Bhojwani ]