0

I just wish to validate my below understanding so please suggest.

In Java, regular array can have indices up to the maximum value of int type which is 2 raised to power 31 minus -1 and since HashMap MAXIMUM_CAPACITY is an int too, it can go up to that value too.

But since HashMap internally needs table length(bucket size) to be a power of two so limit gets curtailed to - static final int MAXIMUM_CAPACITY = 1 << 30; since that value is nearest power of two to 1<<31 -1 .

Am I correct in my understanding?

All answers here mention only about sign bit limit but not power of two requirement, 

/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Also, I understand that size limit for array or Hashmap (bucket size) has nothing to do with system / object / heap memory limitations but max_range for int data type only (index data type)and other logical requirements (like power of two etc).

Community
  • 1
  • 1
Sabir Khan
  • 9,826
  • 7
  • 45
  • 98

2 Answers2

1

You are (more or less) correct in your reasoning about array size.

But the size limit on the internal array HashMap.table does not limit the size of HashMap (i.e. number entries which can be stored in the HashMap).

Each element in that array is effectively a linked list of Entry objects of unlimited size, therefore there is no hard limit on number of entries which can be stored in a HashMap.

Community
  • 1
  • 1
wero
  • 32,544
  • 3
  • 59
  • 84
1

The limit for the array is 2^^30 as this is the largest power of two you can have a for an array. However, there is no reason to suggest that the hash map is limited to this size, but rather it is around this point that the hash map degrades in to a hash of linked lists (or tree in Java 8) i.e there is no limit to the number of entries in each bucket.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130