java Arralist size?

Question

Hi,

As we know ArrayList increases its size by 50% when elements are added(100% incase of Vector).Where can we find the implementation for this behavior?

Thx

Answer 1

Where can we find the implementation for this behavior?

In the source code. You can find the source code for the Sun Java class libraries in the "src.zip" file in your Sun JDK installation. The sources for OpenJDK 6 and OpenJDK 7 are also available for download via the OpenJDK Project page. For other Java implementations, look on the web or consult the documentation.

Beware - not all Java class libraries implement these classes the same way. So for example, looking at the Apache Harmony project sources or the GNU Classpath project sources won't tell you how the Sun JDK class libraries work.

Answer 2

.. in the implementation of ArrayList#add !?

Here's an implementation:

public boolean add(E object) {
  if (lastIndex == array.length) {
     growAtEnd(1);
  }
  array[lastIndex++] = object;
  modCount++;
  return true;
}

It calls growAtEnd and inside this method we find the snippet:

} else {
  int increment = size / 2;
  if (required > increment) {
    increment = required;
  }
  if (increment < 12) {
    increment = 12;
  }
  E[] newArray = newElementArray(size + increment);
  if (size > 0) {
    System.arraycopy(array, firstIndex, newArray, 0, size);
    firstIndex = 0;
    lastIndex = size;
  }
  array = newArray;

.. where the increment is set to 50% of the actual size of the current list.

---

docjar contains the sourcecode of the Apache harmony project, Apaches open source Java SE 6 platform. There a lot of different Java implementations around and it is not guaranteed that each and every implementation shows the exact same behaviour (like increasing size in steps of 50%) as long as it is not documented/required in the interface to this method.

Answer 3

In ArrayList:

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);
  }
}

and Vector:

private void ensureCapacityHelper(int minCapacity) {
  int oldCapacity = elementData.length;
  if (minCapacity > oldCapacity) {
    Object[] oldData = elementData;
    int newCapacity = (capacityIncrement > 0) ?
        (oldCapacity + capacityIncrement) : (oldCapacity * 2);
    if (newCapacity < minCapacity) {
      newCapacity = minCapacity;
    }
    elementData = Arrays.copyOf(elementData, newCapacity);
  }
}

Note: capacityIncrement defaults to 0 unless set otherwise so the default behaviour of a Vector is to double every time the backing array needs to be expanded but if you set capacityIncrement then it will be incremented by that instead.

Also in all cases (for ArrayList and Vector) the increase--regardless of what it is--is superseded if the new capacity still isn't large enough, in which case the required capacity is used.