• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Liutauras Vilda
  • Henry Wong
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Mikalai Zaikin
  • Himai Minh

Bucket and Hashmap

 
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 .
 
Rancher
Posts: 1090
14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ( https://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.

 
Ranch Hand
Posts: 334
2
Netbeans IDE Tomcat Server Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic