개요

• ArrayList는 List Interface의 구현체 중 하나입니다.

• ArrayList는 요소의 갯수가 늘어날 수록 리사이징이 되는데, 내부적으로 배열을 가지고 있습니다.

• 배열은 고정된 길이를 가지기 때문에, 배열이 가득차면 리사이징을 해야합니다.

• 이때 배열을 어느정도 길이로 리사이징해야 하는지 중요합니다.

• 예를 들어 10개의 요소를 담을 수 있는 ArrayList가 있다고 해봅시다.

• 이 ArrayList가 꽉 차있고 1개의 요소를 더 추가하려고하면 공간이 부족하기에, 내부의 배열을 리사이징 해야합니다.

• 이때 리사이징의 길이를 20으로 잡는다 해봅시다.

• 그러면 1개의 요소만 추가되는데도 당장 사용하지 않는 19개의 공간은 낭비되고 있습니다.

• 이렇게 고정된 길이의 리사이징은 비효율적일 수 있습니다.

• Java의 ArrayList는 효율적인 리사이징에 대해서 나름 최적화를 해놨습니다.

• 이 아티클에서는 Java의 코드르 살펴보며 어떻게 ArrayList가 사이즈를 조절하는지 알아보려고 합니다.

목표

🚀 ArrayList는 어떻게 용량을 증가시키는 건지 알아봅니다.

Code 속으로

• ArrayList가 어떤 방식으로 리사이징 하는지 직접 구현된 코드를 살펴봅시다.

Java 6의 ArrayList 구현

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

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    //1) 배열이 가득 찬 상태에서 새로운 요소가 들어온 경우
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
		// 2)증가식을 통해 나온 용량보다 더 큰 용량을 갖게 만드는 길이의 요소가 추가됐을 경우
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

• 위에서 자세히 살펴볼 부분은 ensureCapacity 메소드입니다. 해당 메소드는 ArrayList가 가지고 있는 배열의 리사이징 여부를 판단하고, 리사이징 시 그 길이도 정하게 됩니다.

• 우선 현재 배열이 가득 찼는지 확인하고, 가득 찼다면 (현재 배열의 길이 * 3)/2 + 1 만큼의 새로운 길이의 배열을 만듭니다.

1) 기본 Capacity에 따른 회차 별 Capacity Increment

회차	0회	1회	2회	3회	4회	5회	...
Capacity	10	16	25	38	58	88	...

• 별다른 초기화 설정을 안한다면 배열의 기본길이는 10이므로 아래와 같이 증가하게 됩니다.

• 즉 초기 값이 어떻게 잡히냐에 따라서 배열 길이의 증가량에 영향을 줍니다.

• 초기 값이 작으면 상승폭이 작아서 자주 리사이징이 일어날 것입니다.

• 초기값이 충분히 크다면 리사이징이 일어나는 주기가 길어지지만 한번 증가할 때 사용하지 않지만 잡혀있는 메모리도 많아질 것입니다.

• 초기 값과 리사이징 회차에 따라서 다음에 리사이징 될 길이가 정해지므로 동일한 길이만큼 증가 시키는 것보다 효율적일 것입니다.

2) addAll 메소드 호출 시 Capacity Increment

• addAll메소드로 여러 요소를 한번에 저장할 때는 add메소드 때랑 약간 다르게 동작할 수 있습니다.

• 만약 현재 capacity가 10이고, ArrayList가 가득차 있는 상태라 가정해봅시다.

• 이때 7개의 요소를 addAll메소드를 통해서 저장하게 된다면, 배열의 사이즈를 늘려야합니다.

• 배열 사이즈를 늘릴려고하니 증가식에 의한 사이즈(16)보다 새로운 요소가 들어간 후의 사이즈(17)이 더 큰 상황입니다.

• 그럼 배열 사이즈를 두번 연속 늘려야하나?.. 라는 애매한 상황이 발생합니다.

• 이때 ArrayList는 새로운 요소가 들어간 후의 사이즈(17)로 새로운 배열 크기를 맞춰버립니다.

• 안타깝게도 다음에 add메소드로 1개의 요소만 추가해도 다시 리사이징이 일어납니다.

• 새로운 베이스로 증가식이 적용되기에 그 다음에도 또 addAll메소드로 여러 요소를 받더라도 위와 같은 상황이 발생활 확률은 조금 줄어듭니다.

Java 7의 ArrayList 구현

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

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

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//2147483639

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

capacity 증가식의 변경

• Java 7에서는 capacity 증가식이 약간 변경되었습니다.

• 변경이유는 capacity 증가식 계산 중 발생할 수 있는 overflow 때문입니다.

//java 6
int newCapacity = (oldCapacity * 3)/2 + 1;
/*
	(oldCapacity * 3)/2는 오버플로우가 아닐지라도  
	oldCapacity * 3에서 오버플로우가 발생할 가능성이 있다.
*/

//java 7
int newCapacity = oldCapacity + (oldCapacity >> 1);
/*
	위 코드는 오버플로우에 안전하다.
*/

• shift연산을 통해서 기존의 약 150% 정도의 값을 만들어낼 수 있습니다.

• 오른쪽으로 비트가 이동하면 2로 나눈 것과 같습니다.

• 기존의 capacity 증가폭보다 조금 좁아졌지만 에러에 더욱 안전한 코드가 되었습니다.

• default capacity로부터 증가표는 다음과 같습니다

회차	0회	1회	2회	3회	4회	5회	...
Capacity	10	15	22	33	49	73	...

hugeCapacity 메소드의 추가

• 또한 Java 7에서는 너무 큰 배열을 만드는 것을 제한 하고 있습니다.

• 연속된 공간을 잡는 배열을 너무 크게 할당하면 메모리 운영에 영향을 줄 수 있기 때문이라 합니다.

• capacity가 될 값이 Overflow가 있으면 OutOfMemory(OOM)Error를 발생시킵니다.

• 혹은 MAX_ARRAY_SIZE보다 클 땐, Integer.MAX_VALUE로 capacity를 설정하고,
  MAX_ARRAY_SIZE보다 작을 땐, MAX_ARRAY_SIZE로 capacity를 설정합니다.

• 위와 같이 capacity가 설정된 후 다시 배열이 가득차서 리사이징이 필요할 땐, overflow가 발생해서
  OOM Error가 발생할 것입니다.

Java 8의 ArrayList 구현

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

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

• Java 8은 Java7과 비교하여 큰 변화는 없습니다. 조금 더 최적화 하려는 흔적들이 보이는데요.

• ensureCapacityInternal 메소드를 보면 비어있는 배열, 그러니까 사이즈가 0으로 시작한
  ArrayList인지 체크합니다.

• 이때 사이즈가 0으로 시작한 ArrayList라면 기본 설정값인 10으로 capacity를 잡아줍니다.

• 그러면 다음 리사이징 부턴 기본 capacity에 의한 증가량을 따르게 됩니다.

정리

• ArrayList는 효과적인 저장 공간 관리와 배열의 용량 증가 연산을 위해서 균등하게 Capacity를 증가시키지 않습니다.

• Java 6은 (oldCapacity * 3)/2 + 1,
  Java 7이후 부터는 oldCapacity + (oldCapacity >> 1)로 계산합니다

• 증가식이 바뀐 이유는 Overflow 때문입니다.

• Java 8부터는 너무 큰 배열을 만드는 것을 제한합니다.

• ArrayList의 Capacity를 어떻게 증가시키는지 그 과정을 이해한다면, 초기 capacity를 설정하는 게 중요하다는 것을 알 수 있습니다.

• Capacity의 초기값과 증가된 횟수에 따라서 다음 Capacity가 얼마나 커지는지 영향을 주게 되는 것입니다.