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


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "HashMap Buckets" Watch "HashMap Buckets" New topic
Author

HashMap Buckets

victor kamat
Ranch Hand

Joined: Jan 10, 2007
Posts: 247
We know that for a HashMap the key's hashCode() is used to put the key into a bucket.

The hashCode() is an int.

So is the number of buckets is limited to Integer.MAXIMUM ?
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

The number of buckets is much smaller than that! The hashCode() isn't used directly as an index into a bucket; the HashMap uses the hashCode() modulo the number of buckets. The number of buckets is chosen so as to achieve a given load factor -- i.e., if the buckets start to get too full, the HashMap makes more of them.

But in any case, the number of prety much EVERYTHING is limited to that value. The size of a Java array is a 32-bit int; the length of a java.util.List is a 32-bit int. If you had a 64-bit JVM with enough RAM to hold more than 2^32 (4 billion) objects, then it'd be hard to find a container they'd fit into.


[Jess in Action][AskingGoodQuestions]
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19684
    
  20

Not quite correct Ernest. Although most collections have that limitation, LinkedList can have potentially more than Integer.MAX_VALUE elements, since it does not use an array for its storage. This is also reflected by the Javadoc of Collection.size():
Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

However, its toArray() method is flawed because of this, since it can never contain all elements if there are more than Integer.MAX_VALUE.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38517
    
  23
Is it really 32 bits' worth of capacity Ernest, rather than 31 bits? I have tried to create an array with more than 2147483647 (2^31 - 1) members, and I get compiler errors saying the number is out of range for an int.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

Campbell: yep, you're right. Sorry.

Rob: Thanks, I never read those docs that closely. Weird. Imagine using a list when size() had overflowed in this way!
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38517
    
  23
So the largest number of buckets possible would actually be 2^30 (1073741824), since HashMap always increases its size by doubling.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: HashMap Buckets