자바) ArrayList Capacity (23-07-06)

velog에서 이전한 글 입니다.

ArrayList

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

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

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

    private static final int DEFAULT_CAPACITY = 10;

ArrayList는 Vector, LinkedList는 list라 하자.
new ArrayList<>();로 벡터를 생성하면 elementData에 빈 obejct를 할당한다.
최초 add가 들어오면 if (s == elementData.length) 해당 분기에 걸리고 grow()가 실행된다.
grow(int minCapacity)에서 else 분기가 동작되고 elementData는 DEFAULT_CAPACITY 값인 10의 크기의 배열이 만들어진다.

 

10의 크기를 다 채운다음의 add를 보자.
grow의 if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 해당 분기에 걸리며 newCapacity 크기로 배열을 만들고 복사한다.

(ArraysSupport.newLength)
    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);
        }
    }

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

SOFT_MAX..는 정수의 상한치에 근접한다. prefLength가 상한치에 거의 도달했거나 넘으면 else 분기가 동작한다.
일단 if분기의 경우를 살펴보자. 10의 크기를 채우고 add가 들어온다면 다음과 같다. ArraysSupport.newLength(10, 1, 10 >> 1)
10>>1 = 5
15>>1 = 7
22>>1 = 11
오른쪽 한칸 시프트 연산의 경우 원래 값의 반 정도되는 값이 나오는 것을 볼 수 있다.
그래서 if 분기의 return은 대략oldLength + Math.max(1, oldLength/2); 이렇게 볼 수 있다. 즉 원래 배열 크기의 1.5배 정도의 값이 newCapacity로 할당된다.

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

oldLength + prefGrowth는 overflow이므로 oldLength + minGrowth(==1)로 시작한다. minGrowth를 더한 값마저 overflow라면 OutOfMemoryError를 던진다.

 

overflow가 아니고 Integer.MAX_VALUE - 8 보다 같거나 작다면 최대 capacity로 할당하고 그 보다는 크다면 1씩 증가한 capacity인 minLength를 할당한다.

 

추가로 시간을 비교해보고 각 자료구조의 특성을 생각해보자.

2023.07.13 - [java] - 자바) ArrayList LinkedList 시간 비교 (23-07-06)