wood burning stoves*
The moose likes Java in General and the fly likes Buckets and Hashes Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Buckets and Hashes" Watch "Buckets and Hashes" New topic
Author

Buckets and Hashes

Vijay Kumar koganti
Ranch Hand

Joined: Jan 23, 2006
Posts: 53
Hi all,

I am really confused about these buckets and before i ask my doubts here is what i understood :

HashMap or HashSet has got better Performance for Retrieval/Insertion as the HashCode value of the object ie to be added/retrieved is checked with the existing hashcode values in the Buckets.

Please correct me if my understanding is wrong, now the questions :

1. What are these Buckets ?

2. who determines how many have to be created and whether the count is static or it can increase along with the collection?

3. Where are they stored ?

4. Who creates them and how do they look like ie any datatype associated with them ?

regards,
vijay


vijay kumar k.
Samrat Som
Ranch Hand

Joined: Feb 04, 2009
Posts: 40
Buckets are basically a data structure that is being used in the Paging algorithm of the Operating System . To be in a very Laymans language.

1.Buckets are stored in the heap.

2.The objects representing a particular hashcode is being stored in that bucket.(basically you can consider the header of the linked list data structure to be the hashcode value which is represented in the terms of bucket)

3.The references of the object is being stored in the link list , whose header represents the value of the Hashcode.

4. The JVM creates them and the size, depends upon the memory being allocated by the JVM.

I hope I have tried to clear your doubts.


SCJP 1.6
SCWCD 1.5 (Preparing...)
Vijay Kumar koganti
Ranch Hand

Joined: Jan 23, 2006
Posts: 53
Samrat Som wrote:Buckets are basically a data structure that is being used in the Paging algorithm of the Operating System . To be in a very Laymans language.

2.The objects representing a particular hashcode is being stored in that bucket.(basically you can consider the header of the linked list data structure to be the hashcode value which is represented in the terms of bucket)

3.The references of the object is being stored in the link list , whose header represents the value of the Hashcode.

4. The JVM creates them and the size, depends upon the memory being allocated by the JVM.

I hope I have tried to clear your doubts.


Hi Samrat,
thanks for your reply but i am not getting your points(2,3) and your point 4 doesn't answer any of my question. My Q is that whether the size of the collection is some thing ie going to decide how many buckets has to be created to keep these objects in collection.

can you please explain the answers in brief..
vijay
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  16

Check this article. It explains the relation between hashes, buckets, hashCode(), and equals().


[My Blog]
All roads lead to JavaRanch
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38064
    
  22
Have you read the API documentation?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38064
    
  22
Christophe Verré wrote:Check this article. It explains the relation between hashes, buckets, hashCode(), and equals().
Nice article, but it uses instanceof in a non-final class in its equals() method.
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  16

but it uses instanceof in a non-final class in its equals() method.

Sorry, I don't understand the relation between instanceof and a non-final class.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38064
    
  22
If you extend a non-final class and add a new field, you can have a situation where symmetry of the equals() method is violated. Angelika Langer (a website well worth reading) shows an example ("listing 2") where overriding a class may violate the contract of equals(); this could have been avoided with getClass() == obj.getClass().
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  16

Thank you, that's much clearer.

I'd like to add that this does not reduce the value of the article. We are not here to debate the way the equals method is implemented. As Angelika wrote :
Considering the different approaches and their respective up- and downsides it should by now be clear that none of the solutions is the silver bullet. There is not easy recipe for doing this. A designer of a new class must carefully evaluate the intended and required semantics of the class in order to come to a decision regarding the right implementation of equals() (and other pieces of basic infrastructure not discussed in this article). Here are some guidelines for class designers:


In this article, I don't see any problem with using instanceof.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38064
    
  22
The problem is that it was used without explanation. People reading that article will think instanceof is a standard part of the equals() method, not realising problems might occur later on. As I said before, the article is good about buckets.
Vijay Kumar koganti
Ranch Hand

Joined: Jan 23, 2006
Posts: 53
Campbell Ritchie wrote:Have you read the API documentation?


Yes, I did infact the doubts popped up after reading it.

I have got one doubt from the Article :
"The hashcode only tells the Hashtable into which bucket to drop the key/value. Sometimes, however, multiple objects may map to the same bucket, an event known as a collision."

The only reason i could think of for multiple objects to map into same bucket is when their hashcode values are same? Am i right ??

P.S : The article is really good,Thanks

regards,
vijay
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  16

The only reason i could think of for multiple objects to map into same bucket is when their hashcode values are same? Am i right ??

Yes, that's right. Same hashCode, same bucket.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38064
    
  22
Not the same hashcode. What HashMap does is a bitwise and with one less than the capacity. The buckets are arranged rather like a linked-list[] array, so it works something like thisThe size of the array is always a power of 2: 16, 32, 64, 128 etc. The - operator has a higher priority than the ^ operator, so it is equivalent to hashCode() ^ 15, hashCode() ^ 31, etc.

For 0 and positive numbers, ^15 gives the same result as %16. I wrote about the same question recently here. For negative numbers you get 0 or a positive number between 1 and 15. So you can use that number directly as the index of the buckets array. It only works if the size of the buckets array is 1, 2, 4, 8, 16, 32, 64, etc.

HashMap has a default capacity of 16 (= 16 buckets) and a default load factor of 75%, so when you pass 12 it takes all the contents of all the buckets and moves them into a new buckets array with 32 elements, until you reach 24. It doubles the array size every time you pass 75% of capacity.

Vijay Kumar koganti
Ranch Hand

Joined: Jan 23, 2006
Posts: 53
To summarize here are the answers for the 4 questions, Please feel free to correct me if i am wrong any where :


1. What are these Buckets ?
Ans: The Buckets are placeholders for the keyValue pairs or objects.

2. who determines how many have to be created and whether the count is static or it can increase along with the collection?
Ans : The initial size of the Collection determines the number of buckets that are created and its not static and the number of buckets gets almost doubled if the current size reaches 0.75% of the load and it could be modified.

3. Where are they stored ?
Ans : They are stored on Heap along with the other objects.

4. Who creates them and how do they look like ie any datatype associated with them ?
Ans : JVM creates them along with the creation of collection..

@ I dont know if they are associated with any data type ?, any pointers on this !!

regards,
vijay
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38064
    
  22
The data type in the buckets is java.lang.Object.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Buckets and Hashes
 
Similar Threads
Rehashing
Why does Java’s hashCode() in String use 31 as a multiplier?
Why HashSet has constant order?
WHEN to override equals() and hashcode()
Appropriate hashCode method implements with equals method