ArrayList have a default capacity of 10 objects. As the size exceeds 10 objects, an ArrayList will internally increase its capacity. Does the capacity decrease when we remove the object from ArrayList.
If the ArrayList capacity doesn't decrease, could this lead to performance issues?
It doesn't decrease this automatically. From the doc.
public void trimToSize()
Trims the capacity of this ArrayList instance to be the list's current size. An application can use this operation to minimize the storage of an ArrayList instance.
There are several remove methods within arraylist, I will use the remove by index version as this example
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
The most important thing to note is that a new array is never created within elementData so its size does not change, only elements are copied.
If you need to reduce the capacity of the array list (which you usually won't) use trimToSize()
The ArrayList offers a method, trimToSize(), that "Trims the capacity of this ArrayList instance to be the list's current size. An application can use this operation to minimize the storage of an ArrayList instance." See http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#trimToSize().
If any other methods do such an action silently, that would depend on the implementation provided with your JRE.
do the the capacity decrease when we remove the object from ArrayList.
The answer is simply no.If you observe source code of the ArrayList class, you will get the answer.
There is no operation to decrease capacity of ArrayList's remove() method.
From what I understand the capicity of an ArrayList is only increased, to decrease it must copy one array to another.
I have tried my own experiment to answer you question. You can't lookup the current capacity of an array list so I am running the garbage collector and checking free memory.
My results are:
Before: 125637904
After Aloc: 126959888 -1321984
After Insert: 126718560 241328
After Clear: 126958496 -239936
After trim: 126998432 -39936
After nullify: 126998400 32
Which is weird and I can't explain. Allocating the list reduced free memory. Inserting into the list increased free memory (I didn't expect that) Clearing the list reduced free memory (???) trimming the list decreases free memory again (doesn't seem to clear it) and setting the list pointer to null should get us back to where we started but it doesn't!
My code is below:
package metcarob.com.dev.rubbish;
import java.util.ArrayList;
import java.util.List;
public class ArrayListTest {
private static long outputMem(String pre, long last) {
Runtime.getRuntime().gc();
String pre2 = " " + pre;
System.out.print(pre2.substring(pre2.length()-20) + " ");
long tv = Runtime.getRuntime().freeMemory();
System.out.print(tv);
if (last!=0) {
System.out.print(" " + (last - tv));
}
System.out.println("");
return tv;
}
public static void main(String[] args) {
long lm = outputMem("Before:",0);
ArrayList<String> lis = new ArrayList<String>();
lis.ensureCapacity(10000);
lm = outputMem("After Aloc:", lm);
for (int c=0;c<10000;c++) {
lis.add(new String("ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC"));
};
lm = outputMem("After Insert:", lm);
lis.clear();
lm = outputMem("After Clear:", lm);
lis.trimToSize();
lm = outputMem("After trim:", lm);
lis = null;
lm = outputMem("After nullify:", lm);
}
}
You asked about performance implications. You have to clarify what you mean by "decreasing" performance. If you had to resize the array every time that you decreased the array, you would end up re-copying the array each time. On the other hand, if the capacity remains the same, then you are taking up unneeded memory.
It is your use-case which determines how this impacts the performance perceived by the user. Are they running on a machine with low memory? Are we talking about large, mostly static arrays? Is the array changing all the time?
The Java implementation only changes the underlying array if it needs to. This favors avoiding unnecessary copies at the expense of memory size. But, they give you ability to trim it if necessary.
Does the capacity of an
ArrayListdecrease when we remove elements?
No. This is an implementation detail, but AFAIK no (standard) implementation of the ArrayList class has ever reduced the capacity automatically of a list automatically when elements are deleted.
If the
ArrayListcapacity doesn't decrease, could this lead to performance issues?
Well, in general no.
Firstly, lists typically don't shrink. (Most lists have a relatively short lifetime. They are treated, built by appending and then processed. List element removal is relatively unusual ... though it depends on the application.) So the question is moot, most of the time.
Secondly, unless a ArrayList is grossly oversized, then the unused space at beyond the end of the list doesn't impact performance significantly. Indeed the only time when anything is directly impacted at all is when the list is marked and copied by the garbage collector. And the impact is relatively small, because the region beyond the logical end of an ArrayList is always cleared to null to prevent memory leaks.
It is worth noting that an ArrayList that is creating by appending to an initially empty list is liable to have a backing array that is on average 50% too big. This is because ArrayLists builtin strategy for expanding the backing array is to double its size. This what makes append an amortized O(1) operation.
Thirdly, a delete or similar operation doesn't "know" what is going to happen next with the list, so it cannot judge whether resizing is an appropriate thing to do.
If your application really needs to, it could call trimToSize() after deleting elements. However, beware:
Calling trimToSize() is expensive. The ArrayList implementation is going to create a brand new backing array (of exactly the right size) and copy all of the array elements.
The next time you insert or append an element to the ArrayList after a trimToSize(), the operation will be forced to reallocate the backing array ... again. And the new capacity will be double the current list size.
In fact, if you think about it automatically shrinking an ArrayList after each deletion is pretty much guaranteed to be BAD for performance due to the reallocations and copying it would trigger.
Insertion and deletion would become significantly more expensive than it currently is, and for some usage patterns append would become O(N) on average.
