Why is the maximum capacity of a Java HashMap 1<<30 and not 1<<31, even though the max value of an int is 231-1? The maximum capacity is initialized as static final int MAXIMUM_CAPACITY = 1 << 30;
Asked
Active
Viewed 1.5k times
15
Dennis Meng
- 5,109
- 14
- 33
- 36
tesnik03
- 1,324
- 2
- 13
- 23
-
3Signed integer has a range of **2^31-1** to **-(2^31)**. Remember one bit is reserved for the sign. – initramfs Feb 07 '14 at 21:29
-
Besides which, 2**31 is 2 billion, and each hash entry requires an object for the entry itself, an object for the key, and an object for the value. The minimum object size is generally about 24 bytes, so that would be 144 billion bytes, before you allocate space for anything else in the application. It's safe to say that the MAXIMUM_CAPACITY limit is theoretical only. – Hot Licks Feb 07 '14 at 21:36
-
1It's not even a theoretical limit. That's just the maximum number of buckets. There is no limit on the contents, each bucket can hold an unbounded (by the API, system address space bounds the number of possible pointers to distinct objects I suppose...) number of entries with colliding hashes. – Affe Feb 07 '14 at 21:57
-
There's also the point that the higher-order hash bits are "suspect" in many cases. – Hot Licks Oct 07 '14 at 20:40
-
1<<30 means the 31th bit from the low, and 2nd bit from high. And this is the largest number of power of two of signed int in Java – hao Mar 30 '21 at 01:43
4 Answers
16
Java uses signed integers which means the first bit is used to store the sign of the number (positive/negative).
A four byte integer has 32 bits in which the numerical portion may only span 31 bits due to the signing bit. This limits the range of the number to 2^31 - 1 (due to inclusion of 0) to - (2^31).
initramfs
- 8,275
- 2
- 36
- 58
7
While it would be possible for a hash map to handle quantities of items between 2^30 and 2^31-1 without having to use larger integer types, writing code which works correctly even near the upper limits of a language's integer types is difficult. Further, in a language which treats integers as an abstract algebraic ring that "wraps" on overflow, rather than as numbers which should either yield numerically-correct results or throw exceptions when they cannot do so, it may be hard to ensure that there aren't any cases where overflows would cause invalid operations to go undetected.
Specifying an upper limit of 2^30 or even 2^29, and ensuring correct behavior on things no larger than that, is often much easier than trying to ensure correct behavior all the way up to 2^31-1. Absent a particular reason to squeeze out every last bit of range, it's generally better to use the simpler approach.
supercat
- 77,689
- 9
- 166
- 211
3
By default, the int data type is a 32-bit signed two's complement integer, which has a minimum value of -2^31 and a maximum value of (2^31)-1, ranges from –2,147,483,648 to 2,147,483,647.
The first bit is reserved for the sign bit — it is 1 if the number is negative and 0 if it is positive.
1 << 30 is equal to 1,073,741,824
it's two's complement binary integer is 01000000-00000000-00000000-00000000.
1 << 31 is equal to -2,147,483,648.
it's two's complement binary integer is 10000000-00000000-00000000-00000000.
It says the maximum size to which hash-map can expand is 1,073,741,824 = 2^30.
Chandra Sekhar
- 16,256
- 10
- 67
- 90
-
This is wrong. See Integer.MAX_VALUE: it´s 2^31 - 1, ie. 2,147,483,647. – JRA_TLL Jun 11 '20 at 10:20
-
This is not right. 1<<30 means the 31th bit from the low, and 2nd bit from high. And this is the largest number of power of two of signed int in Java. – hao Mar 30 '21 at 01:42
