• Post Reply Bookmark Topic Watch Topic
  • New Topic

Bucket and Hashmap  RSS feed

 
Avinash Tiwari
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,

We keep on hearing the hashmap stores object(key-value pair) in same bucket for same hashcode.

What exactly is a bucket and internal implementation behind it.

Also how exactly is bucket arranged.Is it some array of bucket(data structure) through which iteration is done.

Also what is the implementation of bucket for storing objects with same hashcode but different and how does get() function retrieves or iterates through them

Also during rehashing how is this principle or bucket concept kept in place.

Please let me know

Thanks
Avinash .
 
Chan Ag
Rancher
Posts: 1090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Avinash Tiwari wrote:Hi All,

What exactly is a bucket and internal implementation behind it.

Also how exactly is bucket arranged.Is it some array of bucket(data structure) through which iteration is done.

Also what is the implementation of bucket for storing objects with same hashcode but different and how does get() function retrieves or iterates through them

Also during rehashing how is this principle or bucket concept kept in place.



How about you read Jesper's response again in a previous post of yours ( http://www.coderanch.com/t/620891/java/java/Hashing-java )?
And then let us know what you've understood of that response. Also how about you go through the source code of java.util.HashMap in the src folder and then tell us how you think these buckets are implemented.

If your analysis turns out to be incomplete/wrong, somebody will definitely correct you.

Chan.

 
Joe Areeda
Ranch Hand
Posts: 334
2
Java Netbeans IDE Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Chan has a point but I'll respond anyway.

I have not looked at the source code to HashMap or HashSet because they work fine, but to describe a general hashing scheme I would say:

We have an array whose size is the number of buckets (N). Each bucket is a Set of objects. Bucket number = hash(obj) % N. Other ways to reduce the hash code to the number of buckets are used. Then each object is stored in the proper bucket. The efficiency comes from searching much smaller buckets for the object.

A bucket is often implemented as a linked list or a b-tree. The efficiency of the algorithm depends on how well the hash code randomizes the objects and how many buckets we have. If you know your data and the number of objects is large searches can be much more efficient than an optimized b-tree.

What rehashing means to me is that when we discover we have too many objects in a bucket we increase N and move the current objects to new buckets.

Joe
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!