ArrayList가 크기를 늘리는 방법

ArrayList는 데이터를 추가할때마다 공간을 확장하는 걸까?
아니면 미리 확장하는 걸까?

 

이번글은 ArrayList가 공간을 확장하는 방법에 대해서 알아보겠습니다.

예시로 Java 6,7,8 버전별 ArrayList의 공간을 확장하는 방법을 비교해보겠습니다.

 

ArrayList가 공간을 확장할때, 정말 동적으로 할당해줄까요?

 

⚠️ 글의 앞부분에서는 간단한 디버깅을 통해 동적 할당이 이루어지는지를 확인합니다. 각 메서드에 대한 설명은 아래에서 자세히 다룹니다.

 

디버깅은 Java v17을 기준으로 합니다.

 

디버깅을 통해서 직접 알아보겠습니다.

 

ArrayList에 값을 추가하면서, ArrayList가 어떠한 메서드를 호출해서 공간을 확장하는지 알아보기 위해 디버깅을 해본 결과 다음과 같습니다.

 

 

grow()라는 메서드가 호출이 됩니다.

 

grow() 메서드가 뭘까요?

 

ArrayList 내부에서 배열의 크기를 동적으로 확장하는 역할을 하는 코드입니다.

 

grow()메서드는 아래와 같은 코드 흐름을 가집니다.

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

 

if문에서 elementData(현재 배열)의 길이가 0보다 크거나 DEFAULTCAPACITY_EMPTY_ELEMENTDATA가 아니라면 새로운 Capacity를 할당한 후, Arrays.copyOf메서드를 사용해 깊은 복사를 해줍니다. 즉, 배열의 확장이 필요한 경우를 의미합니다.

 

ArrayList가 처음 선언될때 사용되는 else문에서는 DEFAULT_CAPACITY와 주어진 minCapacity의 max값을 기준으로 새로운 배열을 할당하게 됩니다.

 

코드에서 ArraySupport.newLength()인 static 메서드가 ArrayList 확장을 담당하는 것으로 보입니다.

또한, 파라미터 3개를 넘기게 되는데 각 파라미터가 의미하는 바는 다음과 같습니다.

• oldCapacity: 기존 배열 크기
• minCapacity - oldCapacity: 최소한 증가해야 하는 크기
• oldCapacity >> 1: 기존 크기의 1/2 배

 

newLength() 메서드에 대해 알아보겠습니다. 코드는 다음과 같습니다.

 

전달받은 3개의 파라미터를 통해 새로운 길이를 할당해 줍니다.

처음 ArrayList를 인스턴스화 할때, 생성자에 아무런 값도 넘겨주지 않았기 때문에, 기본크기인 10으로 설정이됩니다.

 

동적 할당이 일어나는지 디버깅을 통해 알아보겠습니다.

 

list에 0 ~ 9까지 추가해 10의 크기를 가지는 list가 가득찬 상황입니다.

다음 디버깅 포인트로 넘어가니, 아래와 같이 grow() 메서드가 호출됩니다.

 

 

참고로, add 메서드 내부에 크기가 부족할 경우 grow() 메서드를 호출해주는 부분이 존재합니다.

 

Java 6,7,8 버전은 어떻게 동적 할당을 하는지 알아보겠습니다.

 

JAVA 6

 

add(E e)

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

 

add 메소드에서는 ArrayList의 끝에 매개변수로 받은 배열의 원소를 추가합니다. 배열 원소 추가가 되면, true라는 불리언 값을 return해줍니다. add 메서드 내부에서 가장 먼저 호출되는 메서드는 ensureCapacity 메서드 입니다. 인수 값으로 배열의 크기인 size에 1을 더한 값을 넘겨줍니다.

 

ensureCapactiy가 무엇을 하는 메서드일까요?

 

ensureCapacity()

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

 

코드 각 문장을 해석하면 다음과 같습니다.

 

1.  원소를 추가하기 전 이전 배열 크기인 oldCapacity(이전 공간 크기)보다 원소를 추가하고 1을 더한 크기인 minCapacity(최소 필요한 공간 크기) 더 큰 경우, 현재 원소들을 oldData[]라는 Object 배열에 담아줍니다.

 

2. (oldCapacity * 3)/2 + 1 공식을 사용해서 oldCapacity(이전 공간 크기)값의 1.5배를 하고 1을 더한 값을 newCapacity(새로 할당되는 공간 크기)라는 값에 담아줍니다.

 

3. 조건문에서 newCapacity(새로 할당되는 공간 크기)가 minCapacity(최소 필요한 공간 크기)보다 작은경우 즉, 1.5배를하고 1을 더함에도 불구하고 최소 가져야할 배열의 길이보다 작은 경우엔 newCapacity(새로 할당되는 공간 크기)를 minCapacity(최소 필요한 공간 크기)로 초기화 합니다.

 

4. 최종적으로 Arrays의 깊은 복사를 통해 newCapacity(새로 할당되는 공간 크기)를 가진 배열을 초기화합니다.

 

 

Java 7버전은 어떻게 해줄까요?

 

JAVA 7

add(E e)

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

 

add 메서드는 JAVA 6버전과 같습니다.

 

ensureCapacity()

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

 

JAVA6 버전과 달리 grow메서드를 호출합니다.

 

grow()

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

 

Java 7에서는 grow라는 함수를 통해 newCapacity를 oldCapacity + (oldCapacity >> 1)로 설정하고 있습니다.

oldCapacity + (oldCapacity >> 1)가 무엇일까요?

 

이 코드가 의미하는 것은 아래 코드와 같습니다.

newCapacity = oldCapacity + (oldCapacity >> 1)
	    = oldCapacity + oldCapacity * 0.5
 	    = oldCapacity * 1.5

 

쉽게말해, newCapacity를 1.5배 해줍니다.

Java 6에서는 newCapacity에 1.5배를 해준 뒤, 1을 더해준 점과 차이가 있습니다.

if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);

 

Java6과 달리 Java7에서는 MAX_ARRAY_SIZE라는 한계크기가 존재합니다.

만약 한계 크기보다 큰 경우엔 hugeCapacity 메서드를 호출해 newCapacity 크기를 조정해줍니다.

 

hugeCapacity()

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

 

 

MAX_ARRAY_SIZE와 minCapacity를 비교하여 minCapacity가 더 클 경우 Integer의 최대값인 ]2,147,483,647을 리턴하고 MAX_ARRAY_SIZE가 더 클 경우 MAX_ARRAY_SIZE를 리턴하고 있습니다.

 

왜 이렇게 해줄까요?

 

너무 큰 배열을 만들려는 시도를 방지하고, Java의 힙 메모리 한도를 초과하는 문제를 예방하기 위함입니다.

 

 

Java 8버전은 어떻게 해줄까요?

 

 

JAVA 8

 

add()

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

 

JAVA 8은 JAVA 6,7과는 다르게 ensureCapacityInternal을 호출합니다. 

 

 

ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

 

calculateCapacity를 호출한 결과로 ensureExplicitCapacty를 호출합니다.

 

 

 

calculateCapacity()

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

 

 

calculateCapacity 메서드는 ArrayList 내부에서 새로운 배열의 크기를 결정합니다.
ArrayList가 새로운 요소를 추가할 때, 현재 배열이 비어있는 경우 초기 용량을 설정하고, 그렇지 않으면 최소한 필요한 크기를 반환하는 방식입니다.

 

DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY = 10;

 

EMPTY_ELEMENTDATE

private static final Object[] EMPTY_ELEMENTDATA = {};

 

 

ensureExplicitCapacity()

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

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

 

 

현재 elementData 배열의 크기(elementData.length)가 minCapacity보다 작은지 확인해서 배열 크기가 부족하면 grow(minCapacity)를 호출하여 크기를 확장합니다.

 

grow()

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

 

MAX_ARRAY_SIZE

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 

JAVA 8 버전은 newCapacity를 1.5배 증가시킵니다.

newCapacity가 minCapacity보다 작으면, 최소 크기만큼 확장하도록 조정합니다.

만약 newCapacity가 MAX_ARRAY_SIZE보다 크면, hugeCapacity()를 호출하여 newCapacity를 재조정합니다.

 

 

 

 

hugeCapacity()

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

 

JAVA 7버전의 hugeCapacity와 동일하게 동작합니다.

 

 

 

정리

 

• Java 6에서는 (oldCapacity * 3) / 2 + 1 공식을 사용하여 1.5배 증가 후 1을 추가하는 방식으로 크기를 확장합니다.
• Java 7부터는 grow() 메서드를 도입하고, 크기 증가 공식을 oldCapacity + (oldCapacity >> 1)(1.5배 증가)로 변경합니다.
• Java 7 이후 MAX_ARRAY_SIZE 도입으로 너무 큰 배열을 생성하지 못하도록 제한합니다.
• Java 8에서는 calculateCapacity()를 추가하여, 초기 할당 시 지연 초기화(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)를 적용됩니다.

ArrayList는 내부적으로 메모리 관리 및 성능 최적화를 고려하여 점진적으로 발전해 왔으며, Java 7부터 grow() 메서드가 도입되면서 보다 체계적인 크기 조정 방식이 적용되었습니다.