One Cookie a day

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

Bubbles 2023. 10. 9. 16:01

이전에 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 호출시에 할당 크기 결정)

 

 

 

 

기타 참조 글