ArrayList는 어떻게 동적으로 크기를 늘릴 수 있을까?

이전에 CS 스터디에서 ArrayList와 LinkedList의 차이에 대해 공부한 적이 있다. 

• ArrayList
  • 배열과 유사하나 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있음
  • 초기 용량이 다 차면 더 큰 ArrayList 생성 후 거기다 복사한다. 원소가 많다면 대략적인 용량을 처음에 설정하는 것이 성능상 좋다. 
  • 조회 
    • 각 데이터의 index 가지고 있고 index를 통해 해당 데이터에 바로 접근 가능 
  • 데이터 삽입, 삭제
    • 가장 마지막 자리에 데이터를 삽입하거나 삭제한다면 빠른 속도가 가능하나, 중간에 데이터를 삽입하거나 삭제할 경우 빈 칸만큼 뒤의 원소를 앞으로 이동시켜야 한다. (위치를 맞춰줘야 함) 
    • 따라서 일반적으로 ArrayList 중간에 원소를 삽입하거나 삭제하는 경우가 많다면 비효율적
    • 만약 원소를 맨 뒤에 원소부터 쭉 삭제하거나 삽입하게 된다면 오히려 Linked List보다 빠르다. 

 

 

데이터를 삽입할 때, ArrayList는 공간이 부족할 시 자동으로 공간을 확장해준다. 너무 자주 공간을 할당하거나, 한 번에 너무 많은 공간을 할당해버려서 낭비되는 공간이 많아지지 않도록 내부적으로 구현이 되어있다. 

데이터를 추가할 때 어떤 작동방식을 가지고 있어서 이것이 가능한것일지, Java 6, 7, 8 버전을 통해 조사해보았다. 

 

 

 

---

Java 6

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private transient Object[] elementData;
	
    private int size;
    
    // ...
}

 

add 

• capacity 다 찼는지 확인한 후(ensureCapacity) data 넣기 
• checkForComodification
  • Iterator<E> 인터페이스 구현한 내부 클래스 Itr에 존재하는 final 메소드
    • if (modCount != expectedModCount) throw new ConcurrentModificationException();

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


public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
}


private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 

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

• 먼저 처음의 elementData 길이를 oldCapacity에 저장(data 저장된 길이가 아니고 현재의 배열 크기를 의미한다! 이만큼 넣을 수 있다는뜻)
• minCapacity(데이터 하나 넣었을 때의 용량 == 최소 필요 길이) > oldCapacity라면 
  • 새로운 용량은 (oldCapacity * 3) / 2 + 1로 계산
  • 만약 새로운 용량보다도 더 큰 길이가 필요하다면 newCapacity를 minCapcity(필요한 최소 길이)로 바꿔준다.
• new Capacity만큼의 크기의 배열에 기존 데이터를 복사해 넣는다. 
• 이때 복사되는 Arrays.copyOf는 shallow Copy

 

---

 

Java 7

 

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

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

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
}

 

ensureCapacity

단순히 곱하기 나누기로 계산했던 JDK6에서, 7은 grow 함수 호출을 통해 arrayList의 크기를 늘린다.

 

grow(int minCapacity)

• oldCapacity : 현재 데이터 담는 배열 크기
• newCapacity : 비트 연산을 통해 구함 
  • oldCapacity >> 1 : oldCapacity의 비트를 한칸 오른쪽으로 이동, 빈칸은 최상위 부호와 같은 값으로 채워짐
    • 왜 바뀌었는지에 대한 추가 포스팅 
  • JDK 6에서는 일반 곱셈으로 구하는데, 위의 비트 연산자는 단순 비트값을 옮겨주기만 하면 되기 때문에 CPU 부하를 줄일 수 잇음 
  • 만약 MAX_ARRAY_SIZE보다 크다면(MAX_ARRAY_SIZE : Integer.MAX_VALUE - 8이다) hugeCapacity 호출 후newCapacity로 배열 복사 
    • 이때, minCapacity가 음수 나왔다는 것은 int 범위를 넘어갔다는 의미이므로 OutofMemory 에러 던진다.

 

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

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

 

 

---

 

 

Java 8

 

기본적으로 7까지는 10이라는 default 크기의 배열이 생겼는데, 8에서는 EMPTY_ELEMENTDATA가 할당이 된다. 

private static final Object[] EMPTY_ELEMENTDATA = {}; 로 선언이 되어 있다. 

빈 배열에 처음 원소를 넣게되면, DEFAULT_CAPACITY인 10 크기를 가진 배열로 확장된다. 

public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
}

 

add

• ensureCapacityInternal이라는 메소드가 사용되었다. 
  
  • 배열에 아무것도 없는 초기 상태라면, minCapacity 따라 default를 넣을지, minCapacity 만큼 할당할 지 결정한다. 
  • 그 후 ensureExplicitCapacity 호출
• ensureExplicitCapacity
  • 앞 버전들에 있는 ensureCapacity와 동일한 흐름으로 간다. (grow 내부에서 비트연산자 사용하는 것, MAX_CAPACITY 등) 

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

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

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

 

 

 

---

결론

	Java 6	Java 7	Java 8
배열 크기 늘리는 방식	( 현재 배열의 크기 * 3 ) / 2 + 1	shift 연산, oldCapacity >> 1
사용되는 함수	- add - ensureCapacity	- add - ensureCapacity - grow - hugeCapacity	- add - ensureCapacityInternal - ensureExplicitCapacity - grow - hugeCapacity
Add 수행 순서	- add - ensureCapacity 넣을 수 있는지 검사 후, 불가능하다면 배열 크기 늘리고 원본 배열 복사 후 넣는다.	- add - ensureCapacity 넣을 수 있는지 검사 - grow 할당할 수 있는 배열의 최대 크기 넘지 않는지 검사 후 크기 늘려줌 - hugeCapacity MAX_ARRAY_SIZE 보다 크다면 Integer.MAX_VALUE까지만 늘림, 그 이상은 out of memory	- add  - ensureCapacityInternal 최초값 넣는건지 아닌지 검사 - ensureExlicitCapacity 이전 버전의 ensureCapacity와 동일하게 grow, hugeCapacity 호출
최초값	크기 10인 배열		빈 배열 (처음 add 호출시에 할당 크기 결정)

 

 

 

 

기타 참조 글 

https://velog.io/@guswlsapdlf/Java-ArrayList-Add-Method

https://seunghyunson.tistory.com/26