Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is the maximum capacity of a Java HashMap 1<<30 and not 1<<31?

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;

like image 781
tesnik03 Avatar asked Feb 07 '14 21:02

tesnik03


People also ask

Why HashMap capacity is power of 2?

Why is the capacity in power of 2? In general, the number of buckets should be prime is so that the hash values are well distributed and will have less collisions. In case of HashMap, the capacity is always a power-of-two. In contrast, Hashtable by default allocates a size of 11, a prime number.

What is HashMap default capacity?

Finally, the default initial capacity of the HashMap is 16. As the number of elements in the HashMap increases, the capacity is expanded. The load factor is the measure that decides when to increase the capacity of the Map. The default load factor is 75% of the capacity.

What is the difference between the capacity and size of HashMap in Java?

The difference between capacity() and size() in java. util. Vector is that the size() is the number of elements which is currently hold and capacity() is the number of element which can maximum hold. A Vector is a dynamically growable data structure, and it would reallocate its backing array as necessary.


2 Answers

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).

like image 110
initramfs Avatar answered Oct 06 '22 22:10

initramfs


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.

like image 45
supercat Avatar answered Oct 06 '22 23:10

supercat