ArrayList 내부구현 간단하게 살펴보기 (feat. Array)

개요

ArrayList를 자주 사용하는 편인데 ArrayList는 왜 Array와 다르게 초기 사이즈를 정해주지 않아도 되고, 무한정으로 원소가 추가되는 것 입니다. 이 부분이 리스트를 사용하면서도 늘 의문이였습니다. 오늘은 ArrayList를 간단하게 해부해볼 것 입니다. 원소 추가하는 부분을 중점적으로 살펴보겠습니다.

ArrayList 내부적으로는 어떻게 되어있을까?

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  private static final long serialVersionUID = 8683452581122892189L;

  /**
   * Default initial capacity.
   */
  private static final int DEFAULT_CAPACITY = 10;

  /**
   * Shared empty array instance used for empty instances.
   */
  private static final Object[] EMPTY_ELEMENTDATA = {};

  /**
   * Shared empty array instance used for default sized empty instances. We
   * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
   * first element is added.
   */
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  /**
   * The array buffer into which the elements of the ArrayList are stored.
   * The capacity of the ArrayList is the length of this array buffer. Any
   * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
   * will be expanded to DEFAULT_CAPACITY when the first element is added.
   */
  transient Object[] elementData; // non-private to simplify nested class access

  /**
   * The size of the ArrayList (the number of elements it contains).
   *
   * @serial
   */
  private int size;

    ...
}

가장 눈에 띄는 부분들은 내부 원소를 Object[]로 구현한 점과 elementData의 사이즈를 나타내는 size 변수, 그리고 초기 용량인 DEFAULT_CAPACITY가 보입니다.

배열로 구현되어 있는데 어떻게 무한정으로 원소 추가 될까?

ArrayList를 생성해서 add 메서드를 호출해보신 기억이 있으실겁니다. 배열은 초기용량을 정해줘야하고 초기용량을 초과하면 에러가 발생합니다.

그런데 어떻게 ArrayList는 초기 용량이 10으로 정해 졌는데도 불구하고 무한정 원소가 추가될 수 있을까요?

그 이유를 알기 위해서는 ArrayList의 add(E e) 메서드를 살펴봐야 합니다.

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

size는 현재 배열의 사이즈입니다. 현재 사이즈의 1을 더해서 ensureCapacityInternal 메서드를 호출하고 있습니다.

그럼 ensureCapacityInternal 메서드를 살펴볼까요?

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

현재 elementData와 파라미터로 받은 사이즈를 가지고 calculateCapacity를 호출합니다. 메서드 명으로 미뤄봤을 때 인스턴스가 가지고 있는 배열과 사이즈를 가지고 적절한 배열의 용량을 계산해줄 것으로 보입니다.

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

calculateCapacity 메서드입니다. 다음 로직을 거치면서 수행됩니다.

• 파라미터로 받은 elementData가 비어있는 배열인지 확인합니다
• 만약 비어있다면(true) → DEFAULT_CAPACITY(=10)와 파라미터로 받은 minCapacity 둘 중 큰 수를 반환합니다.
• 비어있지 않다면(false) → 파라미터로 받은 minCapacity를 그대로 반환합니다.

자! 다시 ensureCapacityInternal 메서드로 돌아옵니다.

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

calculateCapacity 메서드에서 정해준 용량을 가지고 ensureExplicityCapacity 메서드를 호출합니다.

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

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

먼저 modCount라는 변수(이 elementData가 몇번 수정됐는지에 대한 횟수를 저장하는 변수)를 증가시키고, 파라미터로 받은 minCapacity가 현재 elementData의 사이즈 보다 크다면 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);
}

grow 함수에서는 다음 로직을 수행합니다.

• 현재 배열의 사이즈를 oldCapacity 변수에 할당
• oldCapacity 변수에 oldCapacity 비트 쉬프트한 수(oldCapacity의 1/2 후 나머지 버림한 수)를 더한 값을 newCapacity에 할당합니다.
• 만약 newCapacity가 minCapacity보다 작으면 newCapacity는 minCapacity가 된다.
• 만약 newCapacity가 최대사이즈(Integer.MAX_VALUE - 8) 보다 크다면, hugeCapacity 메서드를 호출합니다.
• 최종적으로 정해진 newCapacity를 가지는 새로운 배열에 기존 데이터를 복사하여 elementData에 저장합니다.

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

hugeCapacity 메서드입니다. 0보다 작으면 예외를 던지고, 파라미터가 배열의 최대 사이즈보다 크면 Integer의 최대 값을 반환하고, 그렇지 않으면 배열의 최대 사이즈를 반환합니다.

OutOfMemoryError를 던지는 부분을 보면, 맨 처음 add 함수에서 size + 1을 하는 부분이 있습니다. 만약 그때의 size가 Integer.MAX_VALUE 였다면 어떻게 될까요?

네, 바로 오버플로우가 돼서 음수값을 가지게 될 것 입니다. 이러한 상황을 방지하기 위해서 방어코드를 삽입한 것 같습니다. 그럼 우리는 ArrayList의 최대 사이즈는 Integer.MAX_VALUE 라는 것을 짐작할 수 있습니다.

마치며..

간단하게 ArrayList 내부에 어떤 멤버 변수가 선언되어 있는지, 어떻게 초기 사이즈를 지정해주지 않았는데 가변적으로 사이즈가 늘어나는지 add 메서드를 하나하나 살펴보면서 그 이유를 알아보았습니다. 그동안 아무 생각없이 편리하기 때문에 ArrayList를 사용했는데요, 내부적으로 어떻게 동작하는지를 살펴본 뒤에는 리스트에 값을 추가할 때 리소스 낭비가 발생하기 때문에 성능이 중요한 부분에서는 사용을 지양 해야겠다고 깨달았습니다.

긴 글 읽어주셔서 감사합니다. 저의 글이 많은 분들께 도움이 되었으면 좋겠습니다. 틀린 내용이 있다면 언제든 편하게 말씀해주시면 감사 드리겠습니다! 감사합니다!