[JAVA] ArrayList는 내부적으로 어떻게 사이즈를 확장할까? (feat. add method)

• ArrayList의 사이즈 확장을 코드로 먼저 확인하기
• add Method의 flow 따라가며 이해하기

 

---

 

ArrayList의 사이즈가 언제 얼만큼 확장되는지 코드를 통해 먼저 확인해보자.

 

ArrayList 객체를 생성하고 20개의 데이터를 순차적으로 담으면서,

언제, 얼만큼 capacity를 늘리는지 단순히 확인하기 위한 코드입니다.

 

가독성을 위해 static 메서드를 사용했고 main 메서드만 확인하시면 됩니다 !

이 글을 참고해서 ArrayList의 capacity를 구하는 메서드를 작성했습니다.

How to get the capacity of the ArrayList in Java?

 

package example;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;

public class ArrayListTest {

	// capacity 구하는 메서드
	static int getCapacity(List<String> list) throws Exception {
		Field field = ArrayList.class.getDeclaredField("elementData");
		field.setAccessible(true);
		return ((Object[]) field.get(list)).length;
	}
    
	// capacity와 size를 출력하는 메서드
	static void print(List<String> list) throws Exception {
		System.out.printf("size:%d, capacity:%d\n", list.size(), getCapacity(list));
	}

	static void print(List<String> list, int line) throws Exception {
		System.out.printf("Line%02d - size:%d, capacity:%d\n", line, list.size(), getCapacity(list));
	}

	public static void main(String[] args) throws Exception {
		List<String> list = new ArrayList<>();  // 객체 생성 (default capacity : 10)
		print(list);

		// 20개 element add
		for (int i = 1; i <= 20; i++) {
			list.add("A");
			print(list, i);
		}
	}
}

 

출력결과

빨간줄 친 4개의 라인만 확인해보자 !

1. 첫번째 Line : 기본생성자로 ArrayList 객체를 생성한 직후에 출력한 결과로, 아직까지 capacity는 0이다.

 

2. Line01 : for문 안에서 첫 데이터가 add됐을 때의 출력 결과로, current capacity는 default capacity인 10으로 늘어나고 첫번째 데이터를 삽입한다. 

 

3. Line11 : capacity가 10인 객체에 10개의 데이터가 이미 꽉찬 상태이고 11번째 데이터를 add하려고 할 때, capacity를 1.5배 늘리고 11번째 데이터를 추가한다.  

 

4. Line16 : Line11과 마찬가지로, capacity를 1.5배 늘리고 16번째 데이터를 추가한다.

 

 

알 수 있는 점 

1. initialCapacity를 주지않은 ArrayList 객체는 첫번째 add 메서드가 실행돼야만 default capacity 10이 적용 (lazy loading)
2. ArrayList load factor는 1이다.
3. ArrayList capacity 1.5배씩 증가 (10->15->22->33->49...)

* Load Factor와 Threshold(임계점)에 대해 알고싶다면, 아래 글을 참고해 주세요 !

[개발용어] Load Factor, Threshold란?

 

---

ArrayList 클래스 선언부와 필드

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    
    // elementData 배열의 초기 크기
    private static final int DEFAULT_CAPACITY = 10;

    // 비어있는 Object 배열
    private static final Object[] EMPTY_ELEMENTDATA = {};  // new ArrayList(0);
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // new ArrayList();

    // ArrayList의 Element(요소)가 저장되는 배열 
    transient Object[] elementData;  // transient: 직렬화 대상에서 제외

    // elementData 배열이 가진 Element(데이터)의 개수 
    private int size;

ArrayList는 확장 가능한 배열, 동적으로 사이즈가 증가하는 배열 등으로 정의되지만,
실제로 ArrayList는 내부적으로 일반적인 Object 배열(elementData)를 가질 뿐이다.

 

그렇다면,
ArrayList도 다양한 타입을 담을 수 있는 일반적인 배열일 뿐인데..

어떻게 동적으로 사이즈가 증가한다는 것일까?

: 답은 add 메서드에 있다. add 메서드의 흐름을 따라가보자 !

 

add Method

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);  // 오버로딩된 메서드 호출
        return true;
    }
    
    // element(데이터)를 추가하는 메서드
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length){  // 배열에 데이터가 꽉 찼는지 체크
            elementData = grow();  // 찼다면, 배열의 사이즈를 확장 !
        }
        elementData[s] = e;  // 데이터 추가
        size = s + 1;
    }

add Method의 작업흐름

1. ArrayList의 Object 배열에 element가 꽉 찼는지 체크한다. (= capacity와 element의 갯수가 동일한지 체크)
   • 배열에 데이터가 가득 찼으면, 배열의 사이즈를 확장하는 grow Method 호출
2. 데이터를 추가한다.

 

add()는 궁극적으로 데이터를 추가하는 역할을 수행하는 메서드이지만,

추가하려는 element를 저장할 공간이 남아있는지 체크해서,
저장할 공간이 남아있으면 데이터 추가하는 역할만 수행하고
저장할 공간이 없으면 저장공간을 늘리기 위한 또 다른 메서드를 호출하는 역할도 수행한다.

grow Method

    private Object[] grow() {
        return grow(size + 1);  // 오버로딩된 메서드 호출
    }
  
    // 크기가 newCapacity(minCapacity)개인 배열을 새로 생성하고, elementData 배열을 복사
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

grow Method의 작업흐름

1. newCapacity 메서드를 호출해서, 확장할 크기를 리턴받는다.
2. Arrays.copyOf 메서드를 사용해서, 리턴받은 newCapacity(minCapacity)만큼의 길이를 가진 새로운 배열을 생성하고
   기존 배열을 복사한다.

 

newCapacity Method

    // capacity와 size가 같을 때, 새로운 capacity를 부여하는 메서드 
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        
        int newCapacity = oldCapacity + (oldCapacity >> 1);  // 현재 capacity의 1.5배 증가한 값을 넣어준다.
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

grow Method의 작업흐름

• 비트 연산을 통해 oldCapacity에서 1.5배 증가된 newCapacity를 리턴한다.

 

---

정리

ArrayList는 내부적으로 Object 배열을 가지고, add 메서드 실행시마다 capacity==size를 체크한다.

같으면 capacity 사이즈를 1.5배 증가시킨 뒤 데이터를 add하고,

같지 않으면 데이터 add만 수행한다.

 

그러므로, ArrayList 객체를 생성할 때 담을 데이터의 크기를 고려해서 initialCapacity를 지정해 주는 것이 성능상 훨씬 좋다. 

 

 

 

* ArrayList의 특징과 사용법, 생성자, 메서드(+ ArrayList 주요 메서드별 시간복잡도)를 확인하려면 아래 글을 참고해 주세요 !

[JAVA] ArrayList의 사용법과 주요 메서드의 시간복잡도