Intro
ArrayList란 무엇인가요?
..인덱스로 원소를 관리하고 그래서 원소를 빠르게 탐색할 수 있어요. 하지만 중간에 원소를 추가하거나 삭제하게 되면 원소의 인덱스가 밀리거나 줄어들게 되어서 성능에 안좋습니다. 정도로 대답했었습니다.
물론 사람들의 기준에 따라 이정도 알면 됐지 라는 사람도 있겠지만 ArrayList라는 자바의 자료 구조 중에서도 상당히 자주 많이 사용되는 자료구조이므로 제대로 알 필요가 있다고 느껴서 이글을 쓰게되었습니다. (java 17을 기준으로 작성했습니다.)
ArrayList에 대해서 파헤쳐보자
ArrayList의 상속관계
java.lang.Object
- java.util.AbstractCollection<E>
- java.util.AbstractList<E>
- java.util.ArrayList<E>ArrayList의 가장 상위 부모는 당연히 Object 클래스 입니다.
그 다음에는 AbstractCollection, AbstractList 클래스 순으로 확장했습니다.
Object 클래스를 제외한 나머지 부모 클래스들의 이름 앞에는 Abstract가 붙어있습니다. 즉 abstract클래스 입니다. abstract클래스는 일반 클래스와 비슷하지만, 몇몇 메소드는 자식에서 구현하라고 abstract로 선언한 메소드들이 있는 클래스 입니다.
생성자에 대하여
ArrayList arrayList = new ArrayList<>();주로 저는 ArrayList를 선언할 때 내부동작 원리에 대해서는 이해하지 않은 채로 위처럼 사용했었습니다. 하지만 내부코드를 살펴보면 ArrayList의 생성자는 3개 입니다.
public ArrayList() 객체를 저장할 공간이 10개인 ArrayList를 만듭니다.
public ArrayList(Collection<? extends E> c)매개변수로 넘어온 컬렉션 객체가 저장되어 있는 ArrayList를 만듭니다.
public ArrayList(int initialCapacity)매개변수로 넘어온 initialCapacity개수 만큼의 저장공간을 갖는 ArrayList를 만듭니다.
ArrayList의 크기를 지정하지않으면 기본 사이즈는 10이다.
위 사진은 실제 내부코드를 캡쳐한 사진입니다. DEFAULT_CAPACITY는 10인 것을 확인할 수 있습니다.
ArrayList 생성 후 크기가 10을 넘어가게 되면 무슨일이 일어날까?
보통 ArrayList에 대한 설명을 들을때면 우리는 동적인 배열이라고 배웠던 기억이 있습니다. 어떻게 동적으로 크기 조절이 가능할까요?
public class Main {
public static void main(String[] args) {
ArrayList arrayList = new ArrayList<>();
for (int i = 0; i < 30; i++) {
Object o = new Object();
arrayList.add(o);
}
}
}간단하게 테스트 코드를 짜본 후 디버그 모드로 실행해보았습니다.
arrayList.add(o)가 실행되게 되면 내부적으로는
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}add 함수가 실행되게 됩니다.
두번째 파라미터로는 오브젝트형 배열을, 세번째 파라미터는 int형 정수(size)를 받고 있습니다.
로직의 흐름은 아래와 같습니다.
- s와 elementData의 길이를 비교하여 배열의 사이즈를 조정해야하는 지 체크합니다.
- 만약 조정해야한다면 3번째 줄의 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)
- 현재 배열이 비어있는지 아닌지 확인합니다.
- 비어있을 경우 esle로 기본용량인 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 (우측 쉬프트 연산)
newLength() 함수를 살펴보겠습니다.
public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
...
...
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이라고 한다면 얼마나 늘릴지 용량을 저장하는 prefGrowth를 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;
}
}기존 크기와 최소 증가값을 더해서 설정한 최소 용량이 0보다 작은 경우 OutOfMemoryError를 발생 시킵니다. SOFT_MAX_ARRAY_LENGTH 이하인 경우에는 설정된 int의 최대치를 용량으로 부여합니다.
추가 내용
TrimToSize() 라는 메소드에 대하여
/**
* Trims the capacity of this {@code ArrayList} instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an {@code ArrayList} instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}ArrayList 객체 공간의 크기를 데이터의 개수만큼으로 변경합니다. 즉 String 클래스의 trim() 메소드가 데이터 앞 뒤 공백을 없애는 것 처럼 이 메소드를 사용하면 저장할 수 있는 공간을 만들어 두었지만, 데이터가 저장되어 있지 않을 때 해당 공간을 없애버립니다. 일반적인 경우에는 이 메소드를 사용할 일이 없지만, 만약 ArrayList객체를 원격으로 전송하거나, 파일로 저장하는 일이 있을 때에 이 메소드를 호출함으로써 데이터의 크기를 줄일 수 있다는 장점이 있습니다.
결론
이렇게 ArrayList의 동작원리에 대해서 살펴보았습니다. "ArrayList는 크기를 동적으로 할당해줘서 편하니까 ArrayList를 써야지" 라고 단순하게 생각했었지만 ArrayList의 내부구조를 알고나니 ArrayList가 항상 좋은 것만은 아니라고 생각이 들었습니다. 예를 들어
배열의 크기를 특정할 수 있을 때 라는 상황이 있다면 배열의 크기를 정해주고 배열을 생성하는 것이 좋다는 생각이 들었습니다.
