ArrayList 내부에서 동적 할당이 어떻게 일어나는지 궁금해서 한번 뜯어봤다.
내용은 추측이 대부분이라 정확 X
ArrayList는 자료구조의 한 종류로서 동적으로 배열의 크기를 변경할 수 있습니다.
1. ArrayList의 초기 크기는 10
2. add()로 인해 사이즈가 꽉 찼을 시 현재의 1.5배를 증가시켜 새로운 배열을 생성
3. 1.5배 증가시킨 새로운 배열에 현재의 배열을 복사
ArrayList는 내부 필드로 정적 배열을 가지고 있고, 동적으로 사이즈를 조절해 주는 배열입니다. 처음 생성할 때 기본 사이즈는 10으로 할당됩니다.이후 요소를 하나 추가(add)할 때 마다 사이즈가 1 씩 늘어나게 되고, ensureCapacity() 메소드로 원하는 사이즈를 할당 시켜줄 수 있는 것 같다..
/*ArrayList.java*/
public boolean add(E e) {
modCount++; // 배열 수정 횟수
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow(); // 사이즈 1 증가
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
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)];
}
}
이 때 할당받을 새로운 사이즈는 ArraysSupport.newLength() 메소드로부터 반환 받게 된다.
ArraysSupport.newLength()
- prefLength 를 반환
- prefLength = oldLength + Math.max(minGrowth, prefGrowth);
/*ArraysSupport.java*/
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);
}
}
oldLength는 할당되어있는 사이즈 (default 10)
minGrowth는
.add()의 경우 (실제 담겨있는 데이터의 수 + 1) - (실제 담겨있는 데이터의 수) 즉, minGrowth = 1
.ensureCapacity()의 경우 실제 담겨있는 데이터 수 + 원하는 minCapacity를 지정 가능
prefGrowth는 실제 담겨있는 데이터 수 / 2
데이터의 length가 10일 때 add() 메소드를 통해 하나를 추가하게 된다면
minGrowth = 11 - 10 = 1
prefGrowth = 10 / 2 = 5
prefLength = 10 + 5 = 15
-> 사이즈가 15인 새로운 배열에 현재 배열을 복사
이러한 과정으로 동적 할당이 이루어 지는 것 같다.
실제 ArrayList.java를 뜯어보다보니 디버깅 해보는데도 이해가 안되는 부분이 많고내가 생각하는게 맞는지 확신이 들지 않는다..