aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Collection Details Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Collection Details" Watch "Collection Details" New topic
Author

Collection Details

Pal Sudarshan
Ranch Hand

Joined: Jun 10, 2004
Posts: 52
Howdy,

I was reading the article "Collections in Java Part 2" by Thomas Paul. He writes, "The HashSet achieves good performance by using a hash to store the Object in the Set. The hash allows fast lookup."

QUESTION:
1. How does HashSet store objects? Explain in detail please.
1a. How does HashSet use hash to store an object?
2. How does the hash allow for fast lookup?
Dan Chisholm
Ranch Hand

Joined: Jul 02, 2002
Posts: 1865
A HashSet stores the Objects in a HashMap. The Object is used as the key in the HashMap. The value stored in the HashMap is just a dummy value that the user never sees. The HashMap provides for fast lookups because the hashCode of the Object is used to calculate which bucket in the HashMap contains the Object.


Dan Chisholm<br />SCJP 1.4<br /> <br /><a href="http://www.danchisholm.net/" target="_blank" rel="nofollow">Try my mock exam.</a>
Fletcher Estes
Ranch Hand

Joined: Jul 01, 2004
Posts: 108
If you're interested in how a HashMap stores values, there are plenty of tutorials available on the web. I don't know how it's implemented in java, but it could be something like:

1. Create an Object[], of arbitrary size, say 100
2. When the map.put(obj1, obj2) method is called, we need to find where in the array to put the obj2.
3. Because the array is sized 100, we could use the formula: obj1.hashCode() % 100. This will always give a value from 0-99, and that's the index at which we place the object in the array
4. Conversely, to retrieve the object via map.get(obj1), we apply the modulus formula again to get the array index, and simply return the value stored there.

There are two problems with this method - what if two different objects hash to the same location, and what if the map needs to store more than 100 objects, and there are many and varied solutions to these problems, the details of which I won't delve into here.
Dan Chisholm
Ranch Hand

Joined: Jul 02, 2002
Posts: 1865
Originally posted by Fletcher Estes:


...

There are two problems with this method - what if two different objects hash to the same location, and what if the map needs to store more than 100 objects, and there are many and varied solutions to these problems, the details of which I won't delve into here.


Fletcher,

Your generalized description of a hashtable is very good, but you left out one detail. Each element in your object array is actually an Entry object that contains a key and a value and a reference to the next Entry in a linked list of Entry objects. Each linked list of Entry objects is commonly called a bucket. In your example, you suggested having 100 elements in the array, so the number of buckets would be 100. The number of Entry objects that can appear in each bucket depends on the load factor value, and the load factor can be set by the programmer.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Collection Details