wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes I am finding hashing a bit confusing please it in a bit detail Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "I am finding hashing a bit confusing please it in a bit detail" Watch "I am finding hashing a bit confusing please it in a bit detail" New topic
Author

I am finding hashing a bit confusing please it in a bit detail

varinder mahajan
Ranch Hand

Joined: Jun 11, 2008
Posts: 47
import java.util.*;
public class CollWrapperEX{
private String s;
public CollWrapperEX(String s){ this.s=s; }
public static void main(String[] args){
HashSet hs=new HashSet();
CollWrapperEX ws1=new CollWrapperEX("xyz");
CollWrapperEX ws2=new CollWrapperEX("xyz");
String s1=new String("xyz");
String s2=new String("xyz");
hs.add(ws1);
System.out.println(hs.size());
hs.add(ws2);
System.out.println(hs.size());
hs.add(s1);
System.out.println(hs.size());
hs.add(s2);
System.out.println(hs.size());
}
}

=====
1
2
3
3

wh


Beat the world,if you can.......
Sagar Rohankar
Ranch Hand

Joined: Feb 19, 2008
Posts: 2902
    
    1

Only subject line cant explain the things, you need to elaborate a Little bit more, What you want to ask ?


=====
1
2
3
3


The output is fine because CollWrapperEX class doesn't override Object#equals() method , where String class override equals() method !

You need to look out more deeply How objects are added into Set collection class !!


[LEARNING bLOG] | [Freelance Web Designer] | [and "Rohan" is part of my surname]
varinder mahajan
Ranch Hand

Joined: Jun 11, 2008
Posts: 47
The output is fine because CollWrapperEX class doesn't override Object#equals() method , where String class override equals() method !


How hashing works
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9293
    
  17

First of all you must remember that a hash set has unique elements. It also uses the equals method of the objects stored in it to check for uniqueness of objects.

In the code you have given

String s1=new String("xyz");
String s2=new String("xyz");

both s1 and s2 will have the same string in them. This means that the equals method called on s1 or s2 with the other passed as parameter will return true.

So when you do this

hs.add(s1); //(1)
System.out.println(hs.size());
hs.add(s2); //(2)
System.out.println(hs.size());

the statement (1) will add s1 object into the hash set. when (2) is executed, it will check if there is already an object in hs that is equals to s2. Since s1 and s2 are equal so the call at (2) will have no effect on hs. This means that no new object will be added. This is why the last two calls to hs.size() returns the same value i.e. 3.
[ August 11, 2008: Message edited by: Ankit Garg ]

SCJP 6 | SCWCD 5 | Javaranch SCJP FAQ | SCWCD Links
Dariusz Kordonski
Ranch Hand

Joined: Jul 11, 2008
Posts: 49
Hash*** collections use hashCode() AND equals() methods of objects to determine if a given object is held within the collection. It is important to know that hashCode is only a 'pre-eliminary' check. Elements of a hash collection are stored in a kind of 'sub-collections', each of them labeled with a specific hash-value. The check, if a given object is held within a collection is performed in two steps:
1) hashCode of objects is retrieved and the collection checks if there is already a sub-collection marked with this hashCode; if not - the object is not in the collection, end of check process
2) if 1) holds true, the matching sub-collection is iterated and equals() invoked on each member until it returns true (object found) or the end of sub-collection is reached.

This procedure may significantly speed up the process of finding given object within a collection. And that's core reason of existence of the hashCode() method. But it requires each object held in the collection to reasonably override hashCode() and equals(). Moreover, there is a special contract between hashCode() and equals(): if o1.equals(o2) == true, then o1.hashCode() == o2.hashCode() (but it must work only in this direction, o1.hashCode() == o2.hashCode() does not have to imply o1.equals(o2). Think about it and find out whyyourself. You may find it useful to take a look at:
http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode()
http://java.sun.com/javase/6/docs/api/java/lang/Object.html#equals(java.lang.Object)
http://www.ibm.com/developerworks/java/library/j-jtp05273.html (a bit old, but does a good job in explaining equals and hashCode)
Bob Ruth
Ranch Hand

Joined: Jun 04, 2007
Posts: 320
I'm going to try my usual thing and break it down to "real simple" idea of what hashing does for you.

Let's say you have 100 different toys to put away but you want to be able to find them with reasonable speed. If you put all 100 into one bucket then you must search through the entire bucket every time you want a toy. There HAS to be a better way.

So let's say that one day you sit down and decide that, the toys are ALL one of 5 colors: red, blue, green, yellow, and orange. So you go and get four more buckets for a total of 5 and you sort out all of your toys into the five buckets according to colors. NOW when you want a toy you first think, what color is it? Once you have the color you know to go to that bucket and you only have to search through the one color bucket which can reduce the time you spend seraching to find JUST the RIGHT toy.

But note a few things:

a) while many toys MAY have the same color and go in the same color bucket, that does NOT make them the SAME TOY. The toys in that bucket are NOT necessarily the same so SOME searching will be required.

b) as you collect toys and add to your collection it is good to have the toy colors spread out evenly by choosing your colors well. If you do not and wind up with one blue toy, no yellow, 3 orange toys, 2 green toys, and ALL of the rest are red, then you will STILL hit a slowdown when you hit the red bucket because you STILL have to search for that special toy that you want and there will be ( initially ) 94 red toys which isn't all that much fewer than the whole 100.

If we start dragging this towards Java hashcodes, all that the hashcode winds up being is a unique integer value that determines which BUCKET this particular object goes in to.

Since it is an integer, it is actually legal to return the same integer for all hashCode calls. But not the best idea because that means that all of your objects are in one bucket.

At the same time it is not the best idea to have hashCodes TOTALLY unique. Each object would be in it's own bucket and that is not necessarily the most space and time efficient choice to make.

The hashCode should depend on the attributes of the particular object that you are storing meaning, the variables that you choose to create your hashCode method. You can make it a simple calculation such as adding the variables or adding the hashCodes of the variables involved. If you know that you would like to see 10 buckets then do a calculation and do a "remainder" or "modulo" of 10 ( calculatedValue % 10 ).

I understand that, if you are intending to override equals() that the hashCode should be calculated on the SAME variables that will be used to determine the equality of the objects. That way the same data controls which hash bucket each object falls into as well as the results of the search itself.

I hope that this approaches what you wanted to know.


------------------------
Bob
SCJP - 86% - June 11, 2009
Rajah Nagur
Ranch Hand

Joined: Nov 06, 2002
Posts: 239
Great example Bob. Thanks for a clear explanation.

On the similar lines, another simple example to explain hashing would be a book store.

When any person enters a library/book store, he first scans which section he wants to visit (Computer/fiction/self-help/spiritual etc) and then go that section and start looking for a particular book.

Two parts:
1. Look for a section/aisle (~ to bucket)
2. Search the book (Object in the bucket)


You can't wake a person who is <b><i>pretending</i></b> to be asleep.<br />Like what <b>"it"</b> does not like - <i> Gurdjieff </i>
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: I am finding hashing a bit confusing please it in a bit detail