The logic used in the securityCapacity method in an ArrayList

Question

I was looking at the source code of an ArrayList. I came across the secureCapacity () method, which increases the capacity of the data array used internally. At the same time, the new capacity of the data array was increased based on the logic int newCapacity = (oldCapacity * 3)/2 + 1; where the old capacity is the current size of the data array. Is there any special reason for choosing (oldCapacity * 3)/2 + 1 as the new size of the array, if so, what is it?

 /** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } } 

Thanks in advance...

Answer 1

The only guarantee made in JavaDoc is that adding a new item has constant amortized time. This means that the average time a new item is added to the array is constant. Sometimes this can take a little longer (for example, when changing the size of the array), but in general, these cases are rare enough not to affect the average level too much.

Therefore, in order to be able to respect this guarantee, they need to make sure that resizing is rare enough not to affect the average add time. For this reason, they use the percentage of current capacity for new capacity. If the size is something like oldCapacity + 50 , the array will be too large for small lists of arrays, but if you want to add several thousand elements, resizing each of the 50 elements will result in poor performance. Thus, throughput increases exponentially (if you have already added many elements, most likely you will add more to increase capacity) so that it does not degrade performance.

As for why they chose 50%, maybe they felt that doubling (or more) of capacity could be excessive (require too much extra memory for very large ArrayLists) and too low (e.g. 10-25%) would be too severely degrade performance (by doing too many redistributions), therefore, probably + 50% offered good enough performance without taking up too much additional memory. I assume they performed some performance tests before deciding on the value.

Answer 2

It increases the list by 50% each time it is called to prevent the distribution of the world too early. + 1 designed to detect situations when the list was initialized with a size of 1 :)