JDK 버전 별 ArrayList 길이 가변 확장 방법 차이

Java로 개발하면서 배열을 사용해야 하는 경우 Collection 프레임워크의 ArrayList 클래스를 사용할 일이 굉장히 많습니다.

배열은 고정 길이 데이터 구조라서 최초에 할당해놓은 길이를 넘어가면 직접 더 큰 크기의 새로운 배열을 만들어줘야 하는 불편함이 있는 반면, ArrayList는 새로운 데이터를 추가할 때 내부적으로 길이를 가변적으로 관리해주기 때문에 더 편리하게 사용할 수 있기 때문이죠.

그렇다면 실제로 내부에서 어떤식으로 ArrayList의 길이를 가변적으로 관리할까요?

이런 ArrayList 클래스도 개발자들이 작성한 코드이고, JDK 버전이 업되면서 기존 구현 코드의 문제점을 보완하거나 더 효율이 좋게끔 업데이트합니다.

그래서 JDK 6,7,8 버전 간 ArrayList 구현 방식에 어떤 차이가 있는지 알아봤습니다.

(아래 JDK 버전 별 코드는 잘못된 이해를 방지하고자 실제 JDK 소스코드를 그래도 첨부했으니 참고 바랍니다.)

JDK 6 - ArrayList Implementation

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

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacity(size+1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    size++;
}

JDK 6 - ArrayList 구현 방식 설명

add 메소드의 내용에 ensureCapacity가 ArrayList의 확장 여부를 확인하고 작업하는 부분이기 때문에 한번 살펴보겠습니다.

1. oldCapacity에 기존 elementData의 길이 할당
2. 최소 필요 길이 minCapacity가 oldCapactiy보다 큰 경우
   1. newCapacity를 oldCapacity에 3을 곱한 뒤 2로 나눈 다음 1을 더한 값(약 1.5배)으로 잡는다.
   2. 만약 새로운 newCapacity도 minCapacity보다 작다면 newCapacity를 minCapacity로 치환한다.
   3. Arrays.copyOf()를 이용해서 기존 elementData를 newCapacity만큼 복사한다.
3. 2번의 경우가 아니라면 아무 작업을 안해도 되기 때문에 함수 종료.

JDK 6에서는 더 큰 ArrayList가 필요한 경우 곱셈과 나눗셈 연산을 통해 기존 길이에서 약 1.5배만큼의 크기로 확장한 새로운 길이의 ArrayList를 생성하여 사용하는 것을 확인할 수 있습니다.

JDK 7 - ArrayList Implementation

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    size++;
}

/**
 * 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) {
    if (minCapacity > 0)
        ensureCapacityInternal(minCapacity);
}

private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

JDK 7 - ArrayList 구현 방식 설명

add 메소드의 내용에 ensureCapacityInternal를 보면 modCount를 늘려준 뒤 grow 메소드를 호출하는 것을 확인할 수 있습니다.

이 grow 메소드가 ArrayList의 확장 여부를 확인하고 작업하는 부분이기 때문에 한번 살펴보겠습니다.

1. oldCapacity에 기존 elementData의 길이 할당
2. 최소 필요 길이 minCapacity가 oldCapactiy보다 큰 경우
   1. newCapacity를 oldCapacity에 oldCapacity를 비트연산을 통해 오른쪽으로 한칸 shift한 값을 더한 뒤 저장한다.
   2. 마찬가지로 만약 새로운 newCapacity도 minCapacity보다 작다면 newCapacity를 minCapacity로 치환한다.
   3. 만약, newCapacity가 MAX_ARRAY_SIZE보다 크다면 hugeCapacity(minCapacity)를 호출한다.
      1. hugeCapacity를 통해 overflow인 경우 OutOfMemoryError를 던지고, overflow가 아닌 경우에는 minCapacity의 값에 따라 MAX_ARRAY_SIZE 혹은 Integer.MAX_VALUE로 지정한다.
   4. Arrays.copyOf()를 이용해서 기존 elementData를 newCapacity만큼 복사한다.

JDK 7에서는 JDK 6와 다르게 더 큰 ArrayList가 필요한 경우 곱셈과 나눗셈 연산을 통하지 않고, 더 빠르고 효율적인 비트연산을 활용하는 것을 확인할 수 있습니다.

oldCapacity + (oldCapacity >> 1)의 비트연산 부분을 살펴보면, oldCapacity의 2진수를 오른쪽으로 1만큼 shift 하여 2^1만큼 나누는 것과 동일한 연산을 수행하여 기존 길이에서 약 1.5배만큼의 크기로 확장한 새로운 ArrayList를 생성하는 것이죠.

추가로, overflow에 대한 exception handling이 추가된 것도 JDK 6와의 차이점입니다.

JDK 8 - ArrayList Implementation

/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    size++;
}

/**
 * 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) {
    int minExpand = (elementData != EMPTY_ELEMENTDATA)
        // any size if real element table
        ? 0
        // larger than default for empty table. It's already supposed to be
        // at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

JDK 8 - ArrayList 구현 방식 설명

JDK 8은 JDK 7과 동일하게 비트연산을 통해 사이즈가 더 큰 ArrayList를 만들어줍니다.

JDK 7과의 차이는 elementData가 ArrayList 인스턴스 최초 생성 시 할당되는 EMPTY_ELEMENTDATA인 경우, 인자로 받은 minCapacity와 DEFAULT_CAPACITY의 값인 10 중 더 큰 수를 minCapacity에 할당하는 부분이 추가된 점입니다.

---

이번 기회로 정말 많이 사용하는 ArrayList의 길이를 어떻게 가변적으로 관리하는지 상세하고 살펴보았고, JDK 버전 별 새로 추가된 내용들 외에도 기존에 이미 있는 클래스들에 어떤 작업들을 하는지 알게 되었습니다.

비트연산에 대해는 알고 있었지만 이렇게 실제로 활용이 된 부분은 처음 보았는데, 이 역시 이론으로만 배웠던 내용을 실제 사례로 보고 그 효율성을 확인할 수 있는 좋은 기회였던 것 같습니다.

특히, 내부 소스코드는 이해하기 어렵다는 두려움이 있었는데 열어서 확인해보니 실제로 그렇지도 않아 앞으로 항상 이런 식으로 깊이 공부하는 버릇을 들일 생각입니다.