ArrayList는 어떻게 용량을 관리할까?

이번 방학기간에 Java의 자료구조에 대해서 심도있는 공부를 해볼 예정입니다.

그 첫번째는 ArrayList입니다.

 

먼저, ArrayList는 List 인터페이스의 구현체입니다.

 

List : 인터페이스

 

• 동일한 데이터의 중복을 허용
• 데이터의 저장 순서가 유지된다
• 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있다.
  • 저장 방식은 해당하는 인덱스에 객체의 주소값을 참조하여 저장한다.

 

List 인터페이스의 특징은 위와 같은 데 이를 통해 알 수 있는 것은 List는 데이터의 중복을 허용하고, 저장 순서가 유지되어야할 때 사용되어야한다는 것입니다.

 

ArrayList

ArrayList는 List 인터페이스의 구현체 중 하나입니다. 아래는 ArrayList의 특징입니다.

 

 

• List 인터페이스를 구현한만큼 크기 조절이 가능하다.
• 내부적으로 배열의 크기를 조작하는 메서드를 가지고 있다.
• 여러 스레드가 동시에 ArrayList 인스턴스에 액세스하고 스레드 중 하나 이상이 목록을 구조적으로 수정하는 경우 외부적으로 동기화해야 합니다. → 멀티 스레드 환경에서 사용하는 것은 비추천!

 

지금부터 내부 메서드들을 하나하나 알아보며, ArrayList는 어떻게 내부적으로 용량을 관리하고 있을 까에 대해서 알아보겠습니다!

 

 

내부 메서드 - 용량 관리

 

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

private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

 

 

위 메서드는 추가할 요소의 인덱스가 배열의 용량의 길이와 같다면, 배열의 용량을 늘리고 해당 값을 List에 넣어줍니다.

grow 메서드는 배열의 용량을 늘리는 역할을 합니다.

 

 

private Object[] grow() {
        return grow(size + 1);
    }

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

 

• grow 메서드의 조건문을 살펴보면, 현재 List가 비어있는 지를 확인합니다.
  • 만약 비어있다면, Math.max(DEFAULT_CAPACITY, minCapacity) 에 따라서 더 큰 값을 가진 것이 새로운 용량이 됩니다.
  • 비어있지 않다면, 아래의 수식에 따라 새로운 용량으로 확장되게 됩니다.
    • size : 10 이라면, minCapacity : 11, oldCapacity : 10, oldCapacity >> 1 : 5

 

int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);

public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0

        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
 }

 

 

• minGrowth : minCapacity - oldCapacity ⇒ 1
• prefGrowth : oldCapacity >> 1 즉 나누기 2! > 5

 

즉, prefLength = 10 + 5    15가된다!!

if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) 이 경우에는 15가 반환된다.

=> 즉 배열의 기존 용량의 1.5배가 커진다는 것을 알 수 있다.

 

preLength가 0보다 작을 경우 그리고, preLength가 Integer.MAX_VALUE - 8보다 클 경우에는 hugeLength 메서드를 실행한다.

 

 

private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError(
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            return minLength;
        }
    }

 

 

• minLength < 0이라면, 용량의 최댓값을 넘겨 음수가 됬다는 뜻이라 OutOfMemoryError를 발생!

위와 같은 메서드들을 통해 배열의 용량을 관리합니다.

 

 

 

마지막으로, trimToSize 메서드에 대해서 알아보고 포스팅을 마무리하겠습니다.

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

 

 

이 메서드는 현재 용량이 사이즈보다 크다면, elementData 즉 용량을 사이즈에 맞게 축소시킵니다.

 

 

지금까지 ArrayList를 공부하며, ArrayList의 크기를 동적으로 생성해줘 편리한 부분이 있고, 또 나름대로의 용량을 최적화하는 기능들이 있지만, 크기를 특정할 수 있는 상황에서는 굳이 ArrayList를 사용하는 것보다는 크기를 정할 수 있는 배열을 사용하는 게 더 좋다는 생각이 들었습니다.