용량이 늘어나는 동적 배열 만들기

앞 글의 TitleArray는 만들 때 정한 용량이 다 차면 IllegalStateException을 던졌습니다. 게시글이 몇 개나 들어올지 미리 알 수 없는 프로그램이라면 이런 목록은 쓰기 어렵습니다. 용량을 넉넉히 잡으면 메모리를 낭비하고, 작게 잡으면 언젠가 넘칩니다. 그렇다고 이미 만든 배열의 길이를 늘릴 수도 없습니다. 자바 배열의 길이는 생성할 때 정해지면 바뀌지 않기 때문입니다.

방법은 하나입니다. 배열이 가득 차면 더 큰 배열을 새로 만들고, 기존 원소를 모두 옮긴 다음, 목록이 새 배열을 쓰게 바꾸는 것입니다. 이렇게 필요할 때 스스로 용량을 늘리는 배열을 동적 배열(dynamic array)이라고 하며, 자바의 ArrayList가 바로 이 구조입니다. 이 글에서는 MyArrayList라는 동적 배열을 직접 만들고, 배열을 얼마나 키울지에 따라 복사 비용이 얼마나 달라지는지 계산해 봅니다.

고정 배열에 하나 더 넣으면

먼저 용량을 확인하지 않고 저장하면 어떻게 되는지 보겠습니다. 다음 코드는 두 칸짜리 배열에 값을 세 번 저장합니다.

public final class FixedCapacityOverflowFailure {
    public static void main(String[] args) {
        String[] values = new String[2];
        int size = 0;
        values[size++] = "array";
        values[size++] = "list";
        values[size++] = "growth";
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
	at FixedCapacityOverflowFailure.main(FixedCapacityOverflowFailure.java:7)

세 번째 저장문은 길이 2인 배열의 2번 칸에 쓰려다 실패합니다. 이 예외는 목록이 아니라 배열이 던진 것입니다. 목록을 쓰는 사람은 '목록에 하나 더 추가한다'고 생각했을 뿐인데, 내부 배열의 길이라는 구현 사정이 예외 메시지로 그대로 드러납니다. 목록이 할 일은 저장하기 전에 칸이 남았는지 확인하고, 모자라면 미리 늘려 두는 것입니다.

더 깊이: 예외가 나도 size는 이미 늘어나 있다

values[size++] = "growth"에서 배열 접근식 values[size++]는 오른쪽 값을 대입하기 전에 먼저 평가됩니다. 이때 size++가 실행되어 size가 3이 되고, 그다음에 2번 칸이 범위 밖이라는 사실이 확인되어 예외가 납니다. 예외를 잡아서 프로그램을 계속 실행했다면 size는 3인데 실제로 저장된 값은 두 개뿐인 상태가 남습니다. 객체 배열로 회원 저장소 만들기에서 본 것처럼, 저장소의 상태를 바꾸는 코드는 실패할 수 있는 일을 모두 끝낸 뒤에 실행해야 합니다. 이 글의 add가 용량 확인을 저장문보다 먼저 하는 것도 같은 이유입니다.

가득 차면 두 배 크기의 배열로 옮긴다

새 배열을 얼마나 크게 만들지가 이 글의 핵심 질문입니다. 가장 단순한 생각은 딱 한 칸만 늘리는 것이지만, 그러면 뒤에서 보듯 거의 매번 추가할 때마다 전체를 복사하게 됩니다. 그래서 동적 배열은 보통 현재 용량의 일정 배수로 늘립니다. 이 글에서는 두 배로 늘리겠습니다.

import java.util.Arrays;

public final class DynamicTitleList {
    public static void main(String[] args) {
        MyArrayList<String> list = new MyArrayList<>(1);
        list.add("array");
        list.add("growth");
        list.add("copy");
        System.out.println(list);
        System.out.println("size=" + list.size() + ", capacity=" + list.capacity());
    }

    private static final class MyArrayList<E> {
        private Object[] values;
        private int size;

        MyArrayList(int initialCapacity) {
            if (initialCapacity < 0) throw new IllegalArgumentException("capacity");
            values = new Object[initialCapacity];
        }

        void add(E value) {
            ensureCapacity(size + 1);   // 저장하기 전에 칸부터 확보한다
            values[size++] = value;
        }

        @SuppressWarnings("unchecked")
        E get(int index) {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
            return (E) values[index];
        }

        private void ensureCapacity(int required) {
            if (required <= values.length) return;
            int doubled = values.length == 0 ? 1 : values.length * 2;
            values = Arrays.copyOf(values, Math.max(doubled, required));
        }

        int size() {
            return size;
        }

        int capacity() {
            return values.length;
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOf(values, size));
        }
    }
}

[array, growth, copy]
size=3, capacity=4

add는 값을 저장하기 전에 ensureCapacity(size + 1)을 호출합니다. 지금 원소가 size개이니 하나를 더 넣으려면 칸이 size + 1개 필요하다는 뜻입니다. ensureCapacity는 필요한 칸 수가 현재 길이 이하이면 아무것도 하지 않고 바로 돌아옵니다. 모자라면 두 배 길이와 필요한 칸 수 중 큰 값으로 새 배열을 만듭니다. 이 일을 하는 Arrays.copyOf(원본, 새 길이)는 지정한 길이의 새 배열을 만들고, 원본의 원소를 앞에서부터 복사해 돌려줍니다. 원본보다 길어서 남는 칸은 null로 채워지고, 마지막으로 values가 이 새 배열을 가리키도록 바꿉니다. 옛 배열은 더 이상 아무도 참조하지 않으므로 가비지 컬렉터가 회수할 수 있는 대상이 됩니다.

용량 1에서 시작한 목록에 세 값을 넣는 과정을 따라가 보겠습니다. 첫 add("array")는 필요한 칸이 1이고 용량도 1이므로 확장 없이 0번에 저장됩니다. 두 번째 add("growth")는 2칸이 필요한데 용량이 1이므로, 길이 2인 새 배열을 만들고 기존 원소 1개를 복사한 뒤 저장합니다. 세 번째 add("copy")는 3칸이 필요한데 용량이 2이므로, 길이 4인 배열로 2개를 복사한 뒤 저장합니다. 그래서 마지막 출력은 size=3, capacity=4이고, 남은 한 칸은 null인 채로 다음 추가를 기다립니다. 첫 줄의 목록 출력에 null이 보이지 않는 것은 toString이 size까지만 잘라서 출력하기 때문입니다.

여기서 확장이 모든 add에서 일어나지 않는다는 점이 중요합니다. 같은 방식으로 계속 넣으면 네 번째 add는 남은 칸에 바로 저장되고, 다섯 번째에서 용량 8로, 아홉 번째에서 16으로 늘어납니다. 확장은 배열이 가득 찬 순간에만 일어나고, 용량이 커질수록 다음 확장까지의 간격도 길어집니다.

확장 규칙에서 빠뜨리기 쉬운 두 가지

ensureCapacity의 두 줄은 각각 실제로 생길 수 있는 문제를 막습니다. 첫째는 용량 0입니다. 빈 배열에서 시작하는 목록은 흔한데, 그 상태에서 values.length * 2로 늘리면 0의 두 배도 0입니다. 다음 코드는 이 점을 놓친 구현입니다.

import java.util.Arrays;

public final class ZeroCapacityBug {
    public static void main(String[] args) {
        MyArrayList<String> list = new MyArrayList<>(0);
        list.add("array");
        System.out.println(list.size());
    }

    private static final class MyArrayList<E> {
        private Object[] values;
        private int size;

        MyArrayList(int initialCapacity) {
            values = new Object[initialCapacity];
        }

        void add(E value) {
            if (size == values.length) {
                values = Arrays.copyOf(values, values.length * 2);
            }
            values[size++] = value;
        }

        int size() {
            return size;
        }
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
	at ZeroCapacityBug$MyArrayList.add(ZeroCapacityBug.java:22)
	at ZeroCapacityBug.main(ZeroCapacityBug.java:6)

배열이 가득 찼다는 판단은 맞았지만, 새로 만든 배열도 길이가 0이라서 첫 저장이 실패합니다. DynamicTitleList의 values.length == 0 ? 1 : values.length * 2는 길이가 0일 때 최소 1칸을 확보해 이 문제를 피합니다.

둘째는 한 번에 여러 개가 필요한 경우입니다. 지금의 add는 한 번에 하나씩만 넣으므로 두 배면 언제나 충분합니다. 하지만 다른 목록의 원소를 한꺼번에 붙이는 addAll 같은 메서드를 생각해 보세요. 원소 4개로 가득 찬 목록에 원소 10개를 한 번에 넣으려면 14칸이 필요한데, 두 배로 늘린 8칸으로는 모자랍니다. Math.max(doubled, required)는 이럴 때 필요한 만큼을 한 번에 확보합니다. 어떤 경우든 새 용량이 필요한 칸 수보다 작아지지 않으므로, 확장이 끝난 뒤의 저장은 언제나 성공합니다.

한 칸씩 늘리면 왜 느린가

이제 '얼마나 늘릴까'를 비용으로 따져 보겠습니다. 한 칸씩 늘리는 방식은 메모리를 한 칸도 낭비하지 않지만, 용량이 크기와 같은 상태가 계속되므로 처음 확보한 칸을 다 쓴 뒤로는 모든 add가 확장을 일으킵니다. k번째 add는 기존 원소 k−1개를 복사해야 하므로, 원소 n개를 넣는 동안 복사하는 원소는 모두 0 + 1 + 2 + … + (n−1) = n(n−1)/2개입니다. n이 열 배가 되면 복사량은 백 배가 되는, n²에 비례하는 비용입니다.

두 배로 늘리면 사정이 완전히 달라집니다. 용량 1에서 시작해 원소 10개를 넣으면 확장은 2번째, 3번째, 5번째, 9번째 add에서만 일어나고, 그때 복사하는 기존 원소는 각각 1, 2, 4, 8개입니다. 두 방식의 복사량을 원소 수에 따라 계산해 보면 차이가 분명합니다.

두 배씩 늘리는 쪽은 복사량이 언제나 n의 두 배를 넘지 않습니다. 이유는 마지막 확장에서 거꾸로 생각해 보면 알 수 있습니다. 마지막 확장에서 복사한 원소 수를 C라고 하면, 용량 1에서 시작한 경우 그 앞의 확장들은 차례로 C/2, C/4, …, 1개를 복사했습니다. 이 수들을 모두 더해도 1 + 2 + 4 + … + C = 2C − 1이므로 2C보다 작습니다. 또 마지막 확장은 원소가 C개였을 때 일어났으니 C는 n보다 작습니다. 따라서 전체 복사량은 2n보다 작고, n에 비례합니다.

분할 상환 O(1)의 뜻

원소 n개를 끝에 추가하는 전체 작업은 이렇게 정리됩니다. 새 값을 저장하는 일이 n번이고, 확장 때 기존 원소를 복사하는 일이 모두 합쳐 2n번 미만입니다. 전체가 3n번 미만이므로, 이를 add 호출 n번으로 나누면 한 번에 3번 미만의 작업이 돌아갑니다. 원소가 천 개든 백만 개든 이 평균은 상수입니다. 이처럼 연산 하나하나가 아니라 연산을 여러 번 한 전체 비용을 횟수로 나누어 따지는 방법을 분할 상환 분석(amortized analysis)이라 하고, 그 결과를 'add의 분할 상환 비용은 O(1)'이라고 말합니다.

비싼 확장의 비용을 그 앞의 값싼 add들이 나누어 낸다고 생각하면 이해하기 쉽습니다. 용량을 C에서 2C로 늘리는 add부터 다음 확장 직전까지, 원소는 C개 추가됩니다. 이 C번의 add가 각자 2만큼씩 비용을 미리 적립해 두면, 모인 2C로 다음 확장 때 원소 2C개를 복사하는 비용을 치를 수 있습니다. 그래서 add마다 저장 1에 적립 2를 더한 3만큼씩만 부담하면 전체 비용이 맞아떨어지고, 앞에서 구한 '3n 미만'과도 같은 결론이 나옵니다. 저축이라는 비유는 여기까지만 맞습니다. 실제 프로그램이 무언가를 미리 적립하는 것은 아니고, 이것은 전체 작업량을 세는 방법일 뿐입니다.

분할 상환은 평균 실행 시간과 다른 개념이라는 점도 구별해야 합니다. 평균 실행 시간은 입력이 어떤 확률로 들어오는지를 가정하고 기댓값을 구하므로, 운이 나쁜 입력이 오면 더 오래 걸릴 수 있습니다. 반면 분할 상환은 확률을 쓰지 않습니다. 어떤 순서로 add를 n번 호출하든 전체 작업은 3n 미만이라고 확실하게 말할 수 있습니다.

그렇다고 각각의 add가 빠르다는 뜻은 아닙니다. 확장을 일으키는 바로 그 호출은 원소 수만큼 복사하므로 O(n)입니다. 대부분의 시간 동안 빠르게 처리되다가 가끔 한 번씩 오래 걸리는 셈이므로, 응답 하나하나의 지연 시간이 중요한 시스템에서는 이 순간이 문제가 될 수 있습니다. 그런 경우에는 예상 최대 개수에 가까운 초기 용량을 처음부터 주거나, 데이터를 미리 적재해 요청을 처리하는 도중에는 확장이 일어나지 않게 하는 방법을 씁니다.

같은 실행을 조금 더 이어서 생각해 보세요. 용량 1에서 시작해 원소 10개를 넣고 나면 size=10, capacity=16이고, 지금까지 확장은 4번, 확장 때 복사한 원소는 1 + 2 + 4 + 8 = 15개입니다. 여기에 원소를 하나 더 넣으면 확장 횟수와 용량, 누적 복사 수는 각각 어떻게 될까요? 다음 확장은 몇 번째 원소를 넣을 때 일어날까요?

더 깊이: 배수를 얼마로 잡을까

두 배는 정답이 아니라 선택입니다. 1보다 큰 배수 r로 늘리기만 하면 복사량은 등비수열의 합이 되어 n에 비례하므로, 분할 상환 O(1)은 어떤 r에서든 성립합니다. 달라지는 것은 상수입니다. r이 크면 확장 횟수와 복사량은 줄지만, 방금 확장한 직후에는 용량의 상당 부분이 비어 있습니다. 두 배라면 최악의 경우 용량의 절반 가까이를 쓰지 않고 남깁니다. r이 작으면 남는 칸은 줄어드는 대신 확장이 더 자주 일어납니다.

자바의 ArrayList는 약 1.5배로 늘립니다. OpenJDK 구현은 기존 용량에 그 절반(oldCapacity >> 1)을 더하며, JDK 21에서 기본 생성자로 만든 목록에 원소를 계속 넣어 보면 용량이 10, 15, 22, 33, 49, 73처럼 늘어납니다. 기본 생성자로 만든 목록은 길이 0인 빈 배열로 시작했다가 첫 add에서야 길이 10인 배열을 만들고, new ArrayList<>(0)처럼 용량 0을 명시하면 1, 2, 3, 4, 6, 9처럼 처음에는 한 칸씩 늘다가 점점 간격이 벌어집니다. 다만 이것은 구현의 세부 사항일 뿐 약속된 동작이 아닙니다. 공식 문서는 성장 정책을 '원소 추가가 분할 상환 상수 시간이 든다는 것 외에는 명시하지 않는다'고 적고 있으므로, 특정 수열에 기대는 코드를 짜서는 안 됩니다.

원소를 많이 넣을 것을 미리 안다면 new ArrayList<>(예상 개수)로 초기 용량을 주거나, 넣기 직전에 ensureCapacity(최소 용량)을 호출해 중간 확장을 줄일 수 있습니다. 반대로 원소를 다 넣은 뒤 남는 칸이 아깝다면 trimToSize()로 용량을 크기에 맞게 줄일 수 있습니다.

게시글 저장소가 스스로 늘어나도록

앞 글의 게시글 저장소는 처음부터 ensureCapacity를 갖고 있었습니다. 이제 이 메서드가 무슨 일을 하는지 읽을 수 있습니다.

public final class PostRepositoryCliCH142 {
    public static void main(String[] args) {
        PostRepository repository = new PostRepository();
        repository.add("capacity", 30);
        repository.add("array-copy", 50);
        repository.print();
        System.out.println("total=" + repository.totalViewCount());
    }

    private static final class PostRepository {
        private Entry[] entries = new Entry[2];
        private int size;

        void add(String title, int viewCount) {
            if (title == null || title.isBlank()) throw new IllegalArgumentException("title");
            if (viewCount <= 0) throw new IllegalArgumentException("viewCount");
            ensureCapacity(size + 1);
            entries[size++] = new Entry(title, viewCount);
        }

        private void ensureCapacity(int required) {
            if (required <= entries.length) return;
            Entry[] grown = new Entry[Math.max(required, entries.length * 2)];
            System.arraycopy(entries, 0, grown, 0, size);
            entries = grown;
        }

        int totalViewCount() {
            int total = 0;
            for (int i = 0; i < size; i++) {
                total += entries[i].viewCount();
            }
            return total;
        }

        void print() {
            for (int i = 0; i < size; i++) {
                Entry entry = entries[i];
                System.out.println(i + ":" + entry.title() + "=" + entry.viewCount());
            }
        }
    }

    private record Entry(String title, int viewCount) {}
}

0:capacity=30
1:array-copy=50
total=80

MyArrayList와 다른 점은 복사 방법입니다. 여기서는 새 배열을 직접 만든 뒤 System.arraycopy(entries, 0, grown, 0, size)로 0번부터 size개의 원소를 옮깁니다. 이 저장소는 배열이 가득 찼을 때만 확장하므로 이 시점의 size는 배열 길이와 같고, 결과적으로 Arrays.copyOf와 같은 일을 합니다. 또 새 길이를 Math.max(required, entries.length * 2)로 정하므로, 용량이 0이었더라도 필요한 칸 수만큼은 확보됩니다.

이번 실행은 두 칸짜리 배열에 게시글 두 개만 넣으므로 확장 분기를 지나지 않습니다. main에 repository.add("growth", 20);을 한 줄 더 넣고 실행하면 세 번째 add에서 길이 4인 배열로 옮겨 간 뒤 2:growth=20과 total=100이 출력됩니다. 확장 뒤에도 기존 두 게시글이 같은 순서와 조회 수로 남아 있다는 것이 바로 앞 글에서 정한 확인 기준입니다. 용량이 언제 얼마나 늘어나는지는 출력에 드러나지 않는 내부의 성능 문제일 뿐이고, 사용자에게 보이는 동작은 달라지지 않아야 합니다.

초기 용량과 성장 배수를 정하는 기준

초기 용량은 정답이 있는 값이 아니라, 남는 메모리와 복사 횟수 사이에서 고르는 값입니다. 너무 크게 잡으면 쓰지 않는 칸이 메모리를 차지하고, 너무 작게 잡으면 초반에 확장이 여러 번 일어납니다. 그러니 감으로 정하기보다 실제 데이터가 보통 몇 개쯤 되는지 확인한 뒤 정하는 것이 좋습니다. 다만 어떤 초기 용량을 고르든 배수로 늘리는 한 끝 추가의 분할 상환 비용은 O(1)이므로, 초기 용량은 성능을 조금 다듬는 값이지 정확성을 좌우하는 값이 아닙니다.

정리

• 자바 배열의 길이는 바꿀 수 없으므로, 동적 배열은 가득 찼을 때 더 큰 배열을 만들고 원소를 복사한 뒤 새 배열로 바꿔 씁니다.
• 저장하기 전에 size + 1칸이 있는지 확인합니다. 새 용량은 두 배와 필요한 칸 수 중 큰 값으로 하고, 용량 0에서도 늘어날 수 있도록 최소 1칸을 확보합니다.
• 한 칸씩 늘리면 n개를 넣는 데 n²에 비례하는 복사가 필요하고, 두 배씩 늘리면 전체 복사량이 2n 미만입니다.
• 그래서 끝 추가의 분할 상환 비용은 O(1)입니다. 확률을 가정하지 않고 어떤 순서로 n번 호출하든 성립하지만, 확장을 일으키는 그 한 번의 호출은 O(n)입니다.
• 자바의 ArrayList는 약 1.5배로 늘리지만, 공식적으로 약속된 것은 분할 상환 상수 시간이라는 점뿐입니다.

연습 문제

문제 1: 확장 횟수 세기

초기 용량 1에서 두 배씩 늘리는 동적 배열에 원소 10개를 끝에 추가한다고 가정합니다. 실제 배열은 만들지 말고 size와 용량만 바꿔 가며, 확장이 일어난 횟수와 마지막 용량을 출력하는 프로그램을 작성하세요.

public final class CapacityGrowthTraceSolution {
    public static void main(String[] args) {
        int size = 0;
        int capacity = 1;
        int growths = 0;
        while (size < 10) {
            int required = size + 1;
            if (required > capacity) {
                capacity = Math.max(required, capacity * 2);
                growths++;
            }
            size++;
        }
        System.out.println("growths=" + growths + ", capacity=" + capacity);
    }
}

growths=4, capacity=16

문제 2: 늘리는 방식에 따른 복사량 비교하기

문제 1의 프로그램을 고쳐, 원소 n개를 넣는 동안 확장 때 복사하는 원소 수의 합을 구하세요. 한 칸씩 늘리는 방식과 두 배씩 늘리는 방식을 n = 10, 1,000, 1,000,000에 대해 비교합니다. 확장할 때 복사하는 원소 수는 그 순간의 size와 같습니다.

public final class GrowthCopyCount {
    public static void main(String[] args) {
        for (int n : new int[] {10, 1_000, 1_000_000}) {
            System.out.println("n=" + n
                    + "  plusOne=" + copiesFor(n, false)
                    + "  doubling=" + copiesFor(n, true));
        }
    }

    private static long copiesFor(int n, boolean doubling) {
        long copied = 0;
        int capacity = 1;
        for (int size = 0; size < n; size++) {
            if (size == capacity) {
                copied += size;
                capacity = doubling ? capacity * 2 : capacity + 1;
            }
        }
        return copied;
    }
}

n=10  plusOne=45  doubling=15
n=1000  plusOne=499500  doubling=1023
n=1000000  plusOne=499999500000  doubling=1048575

문제 3: 확장하는 그 한 번의 비용

두 배씩 늘리는 MyArrayList의 끝 추가는 분할 상환 O(1)입니다. 그런데 원소가 1,000,000개 들어 있고 용량도 1,000,000인 목록에 add를 한 번 호출하면, 그 호출은 몇 개의 원소를 복사할까요? 이 사실이 분할 상환 O(1)이라는 말과 모순되지 않는 이유를 설명하세요.

다음 글

MyArrayList는 get에서 @SuppressWarnings("unchecked")를 붙이고 Object 값을 E로 캐스팅했습니다. 제네릭 목록과 타입 안전성에서는 목록을 제네릭으로 만들어야 하는 이유와, 내부에 Object[]를 쓰면서도 이 캐스팅이 안전한 이유를 살펴봅니다.