• Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
saurabh kuma
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!