[Java] ArrayList<>() 배열 사이즈 동적할당 방법 뜯어보기

---

ArrayList

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를 뜯어보다보니 디버깅 해보는데도 이해가 안되는 부분이 많고내가 생각하는게 맞는지 확신이 들지 않는다..