Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

HashMap Buckets

 
victor kamat
Ranch Hand
Posts: 247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24211
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Rob Spoor
Sheriff
Pie
Posts: 20552
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49447
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24211
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 49447
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So the largest number of buckets possible would actually be 2^30 (1073741824), since HashMap always increases its size by doubling.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic