Query regarding ArrayList on creation of new array in ensureCopacity(...) method

[saurabh kuma]

Hi Friends,

I was looking in to implementation of ArrayList class, particularly the add(..) method which is

public boolean add(E o) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = o;
return true;
}

The above method calls another method ensure capacity, which is responsible for creating new array:

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;
elementData = (E[])new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}

I was wondering why Java designers have defined new capacity as (oldCapacity * 3)/2 + 1 and not anything else? How this optimization was found?

[Steve Luke]

I don't think anyone here was involved in writing that method so 'why was it written that way' is probably not answerable. But:

1) This is an implementation detail. You don't need to know that calculation or they would put it in the API. So why are you worrying about it?

2) If I were to straight up guess with no knowledge of the situation: I would hardly call it an optimization, I would call it a compromise. "The size has to grow, but doubling in size is probably not very efficient at larger list sizes, so let's make sure we grow by at least 1.5 so we don't have to come up with some complex growth scheme."

[Winston Gutkowski]

saurabh kuma wrote:I was wondering why Java designers have defined new capacity as (oldCapacity * 3)/2 + 1 and not anything else? How this optimization was found?

Like Steve, I'm just guessing, but one thing about calculating the new size based on the old makes the size increase exponential, which in turn allows them to say that additions work in amortized constant time.

Winston