• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

can you please this doubt about hashcode()

 
Ranch Hand
Posts: 155
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:


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 ]
 
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.


[ December 19, 2008: Message edited by: Mukesh Bhojwani ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic