This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Java in General and the fly likes About Buckets used in Hashcode in java 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 "About Buckets used in Hashcode in java" Watch "About Buckets used in Hashcode in java" New topic
Author

About Buckets used in Hashcode in java

Karan Kaw
Greenhorn

Joined: Jan 05, 2013
Posts: 11
When we create hashcode based storage(map/set); Hash based Systems Use an array of Buckets.
For storing, we perform hashcode() on Key(object), That gives us index of Bucket in which we actually save 'Key-Value'(map) or Value(set)

---Source(A Programmers Guide to JAVA CERTIFICATION by Khalid Mughal)

My Question is :
Does my hashcode necessarily have to start from Zero onwards so that Array of Buckets maintained by hashtable gets correct Zero-based Index?
How we ensure that hashcode() value must start from '0' as I believe hashcode gives some arbitrary Number??
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19656
    
  18

Karan Kaw wrote:Does my hashcode necessarily have to start from Zero onwards so that Array of Buckets maintained by hashtable gets correct Zero-based Index?

You don't have to worry about that. HashMap etc all have their own internal mechanism to make sure hash codes can be used to locate buckets. If you want to know how this works you can check out the source code of HashMap inside the src.zip file in your JDK's root folder.

How we ensure that hashcode() value must start from '0' as I believe hashcode gives some arbitrary Number??

hashCode() doesn't necessarily give an arbitrary number. Most classes have a deterministic way of calculating it; String for instance even describes the calculation. And like I said before, you don't need to ensure that values start with 0, negative values are just fine.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2841
    
  11

There's not a one-to-one mapping between hash codes and buckets. Usually a modulo is used to make this mapping. So, if your hash has 100 buckets, you take the hash code of an object and mod it by 100 to determine the bucket to use. Modulos are automatically 0-based. Conflicts will arise as different hash codes will be mapped to the same bucket, so every hashing algorithm must have a way to resolve these conflicts, for example by creating a linked list in the bucket instead of a single object. A prime number of buckets tends to reduce conflicts, but doesn't eliminate them.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Karan Kaw wrote:Does my hashcode necessarily have to start from Zero onwards so that Array of Buckets maintained by hashtable gets correct Zero-based Index?
How we ensure that hashcode() value must start from '0' as I believe hashcode gives some arbitrary Number??


No. The rules for hashcode are just one rule: if two objects are equal then they must have the same hashcode. That's all.

In particular the concept of hashcodes "starting from" some point doesn't mean anything. They are indeed, as you say, just some (nearly) arbitrary number. Beyond that you don't need to know how the hashtable class manages those buckets, and really you don't even need to know that there are buckets involved at all.

At least that's true for beginners and for learners. It may happen that your hashcode function turns out to be extremely important from a performance point of view, in which case you may need to know something about the internal implementation details of the hashtable implementation you are using, but that is extremely unlikely.
Karan Kaw
Greenhorn

Joined: Jan 05, 2013
Posts: 11
Hi Folks,

Yes You are right I do not need to bother about these Intrinsic Details of Hashcode.
But, Just Out of curiosity, I wanted to know/guess how Arbitrary Values generated by Hashcode relate to index of Bucket Array.

For sake of understanding, Its good enough to know
Modulos are automatically 0-based

as Greg has Quoted here.


Thanks , All of You.
Really This is Really useful Knowledge Sharing Forum.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38075
    
  22
Greg Charles wrote:There's not a one-to-one mapping between hash codes and buckets. Usually a modulo is used to make this mapping. So, if your hash has 100 buckets, you take the hash code of an object and mod it by 100 to determine the bucket to use. Modulos are automatically 0-based. . . .
Most people would not use 100 buckets, but 128. Then you can use h & c - 1 where h is hash code and c capacity. That always gives a result which matches an array index, unlike % which can give negative results.
 
 
subject: About Buckets used in Hashcode in java
 
Similar Threads
HashMap Buckets
Using object as keys in maps
why we don't have a map view operation on Lists.
Collection(Set), Using a HashSet
HashCode Call