Why the new capacity of arraylist is (oldCapacity * 3)/2 + 1?

Question

Why does ensureCapacity() in Java ArrayList extend the capacity with a const 1.5 or (oldCapacity * 3)/2 + 1?

Answer 1

Resizing the array is a relatively expensive operation. It wants to try and make sure that if the method gets called with ensureCapacity(11), ensureCapacity(12), ensureCapacity(13), ... it should not have to resize the array every time. So it resizes by a reasonable chunk (increase by 50%) instead of the minimum specified.

Answer 2

The main reason lies the (asymptotic) complexity of adding a sequence of elements to the list.

Note that the add method internally calls ensureCapacity(size+1). When the size of the internal array is increased, all elements have to be copied into the new, larger array.

If the size was only increased by a constant amount (which would be 1 for each call to add), then adding n elements would have a complexity of O(n²).

Instead, the size is always increased by a constant factor. Then, adding n elements only has a complexity of O(n).