[JAVA] ArrayList는 어떻게 늘어나는가? ArrayList의 동적 할당 방식

ArrayList란

ArrayList는 배열과 유사하며, List 인터페이스를 구현한 것이다. 기본적으로 각 데이터에 순차적으로 접근 가능한 연속된 자료구조이다.

 

ArrayList의 특징

• 초기화할 때 크기를 지정할 필요가 없다. 배열은 크기가 고정되어 있지만, ArrayList는 사이즈가 동적으로 할당되는 배열이다.
• 참조 타입(reference type)만 원소로 저장할 수 있다.
• 데이터 중복이 가능하며, null 값도 허용한다.
• 자료를 대량으로 추가하거나 삭제하면 내부 처리 작업이 늘어나서 성능이 떨어질 수 있다.

ArrayList의 주요 메소드

메소드	설명
boolean add(E e)	지정된 제네릭 타입 데이터를 추가한다.
void add(int index, E element)	특정 인덱스 위치에 데이터를 추가한다.
boolean addAll(Collection<? extends E> c)	Collection을 현재 ArrayList에 모두 추가한다.
void clear()	모든 데이터를 초기화한다.
boolean contains(Object o)	파라미터로 전달된 객체를 포함하고 있는지 검사한다.
E get(int index)	특정 인덱스 위치의 제네릭 타입의 데이터를 가져온다.
int indexOF(Object o)	파라미터로 전달된 객체의 인덱스를 리턴한다.
Iterator<E> iterator()	순차 데이터 처리를 하려고 Iterator 객체를 가져온다.
boolean remove(int index)	특정 인덱스 위치의 데이터를 삭제한다.
int size()	ArrayList 객체에 포함된 데이터의 크기를 리턴한다.

 

ArrayList의 동적 할당 방식

크기가 정해져 있는 배열과 달리 ArrayList는 데이터가 추가될 때 어떻게 사이즈가 동적으로 늘어나는지 내부 메소드를 통해서 알아보기로 했다.

	/**
	 * Default initial capacity.
	 */
	private static final int DEFAULT_CAPACITY = 10;

	/**
	 * Shared empty array instance used for empty instances.
	 */
	private static final Object[] EMPTY_ELEMENTDATA = {};

	/**
	 * Shared empty array instance used for default sized empty instances. We
	 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
	 * first element is added.
	 */
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	/**
	 * The array buffer into which the elements of the ArrayList are stored.
	 * The capacity of the ArrayList is the length of this array buffer. Any
	 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
	 * will be expanded to DEFAULT_CAPACITY when the first element is added.
	 */
	transient Object[] elementData;

기본 Capacity가 10이다. ArrayList는 실제로 일반적인 Object 배열을 사용하고 있음을 알 수 있다.

빈 ArrayList는 첫 번째 요소가 추가될 때 기본 Capacity로 크기가 확장된다고 한다.

	/**
	 * Constructs an empty list with the specified initial capacity.
	 *
	 * @param  initialCapacity  the initial capacity of the list
	 * @throws IllegalArgumentException if the specified initial capacity
	 *		 is negative
	 */
	public ArrayList(int initialCapacity) {
		if (initialCapacity > 0) {
			this.elementData = new Object[initialCapacity];
		} else if (initialCapacity == 0) {
			this.elementData = EMPTY_ELEMENTDATA;
		} else {
			throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
		}
	}

	/**
	 * Constructs an empty list with an initial capacity of ten.
	 */
	public ArrayList() {
		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}

ArrayList 생성 시 초기 용량을 준 경우와 빈 ArrayList로 생성한 경우.

add() 메소드

	/**
	 * This helper method split out from add(E) to keep method
	 * bytecode size under 35 (the -XX:MaxInlineSize default value),
	 * which helps when add(E) is called in a C1-compiled loop.
	 */
	private void add(E e, Object[] elementData, int s) {
		if (s == elementData.length)
			elementData = grow();
		elementData[s] = e;
		size = s + 1;
	}

	/**
	 * Appends the specified element to the end of this list.
	 *
	 * @param e element to be appended to this list
	 * @return {@code true} (as specified by {@link Collection#add})
	 */
	public boolean add(E e) {
		modCount++;
		add(e, elementData, size);
		return true;
	}

현재 ArrayList 내부에서 동작하는 배열의 크기가 같을 때,

grow() 라는 메소드로 크기를 확장해 준 뒤 입력받은 인덱스에 새로운 값을 추가하고 있다.

그렇다면 grow()는 어떻게 동작하고 있을까. 🙄

	/**
	 * Increases the capacity to ensure that it can hold at least the
	 * number of elements specified by the minimum capacity argument.
	 *
	 * @param minCapacity the desired minimum capacity
	 * @throws OutOfMemoryError if minCapacity is less than zero
	 */
	private Object[] grow(int minCapacity) {
		int oldCapacity = elementData.length;
		if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
			int newCapacity = ArraysSupport.newLength(oldCapacity,
					minCapacity - oldCapacity, /* minimum growth */
					oldCapacity >> 1		   /* preferred growth */);
			return elementData = Arrays.copyOf(elementData, newCapacity);
		} else {
			return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
		}
	}

	private Object[] grow() {
		return grow(size + 1);
	}

 if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

먼저 현재 ArrayList가 비어 있는지 아닌지 확인한다.

비어 있을 경우, else로 기본 용량인 10과 size + 1 중 큰 값으로 새 Object 배열을 생성한다.

그렇지 않은 경우, 새로운 capacity로 크기를 확장해 준다. 

 

 int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1);

oldCapacity : 기존 용량

minCapacity - oldCapacity : (size + 1) - (elementData.length) = 일반적으로 최소 증가값은 1이 된다.

oldCapacity >> 1 : 기존 용량 / 2 (우측 쉬프트 연산)

	/**
	 * A soft maximum array length imposed by array growth computations.
	 * Some JVMs (such as HotSpot) have an implementation limit that will cause
	 *
	 * ...
	 */
	public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

	/**
	 * Computes a new array length given an array's current length, a minimum growth
	 * amount, and a preferred growth amount. The computation is done in an overflow-safe
	 * fashion.
	 *
	 * ...
	 */
	public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
		// preconditions not checked because of inlining
		// assert oldLength >= 0
		// assert minGrowth > 0

		int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
		if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
			return prefLength;
		} else {
			// put code cold in a separate method
			return hugeLength(oldLength, minGrowth);
		}
	}

어마어마한 양의 주석이라 중간에 생략했다.

 int prefLength = oldLength + Math.max(minGrowth, prefGrowth)

기존 arrayList가 10이라고 한다면 얼마나 늘릴지 용량을 저장하는 prefLength을 10과 minGrowth, prefGrowth 중 더 큰 값인 5를 더해 15으로 설정한다. 결국 기존 크기에서 1.5배로 늘려 새로운 크기를 결정하는 것이다.

 

 if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH)

새로운 크기가 SOFT_MAX_ARRAY_LENGTH를 넘어가지 않을 경우, 그대로 넘겨 주지만 0보다 작거나 최대 용량 값을 넘는 경우는 어떻게 될까.

	private static int hugeLength(int oldLength, int minGrowth) {
		int minLength = oldLength + minGrowth;
		if (minLength < 0) { // overflow
			throw new OutOfMemoryError(
				"Required array length " + oldLength + " + " + minGrowth + " is too large");
		} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
			return SOFT_MAX_ARRAY_LENGTH;
		} else {
			return minLength;
		}
	}

 int minLength = oldLength + minGrowth;

기존 크기와 최소 증가값을 더해서 설정한 최소 용량이 0보다 작은 경우 OutOfMemoryError 발생. SOFT_MAX_ARRAY_LENGTH 이하인 경우에는 설정된 int의 최대치를 용량으로 부여한다.

 

결론적으로

ArrayList는 새 요소를 추가하고자 할 때, capacity가 기존 배열의 크기와 같아지면 기존 용량의 1.5배만큼 증가시키고 그 크기가 늘어난 배열에 기존 elementData를 copy한다. 실제로는 정적 배열을 사용하지만, 요소가 추가될 때마다 최소 증가량을 계산하여 크기를 늘리는 방식이라는 것을 알 수 있었다.

 

 

참고

zorba91.tistory.com/287

sabarada.tistory.com/63

junghyungil.tistory.com/96