📌 서론.

자바의 동적 배열인 ArrayList와 연결리스트를 공부하면서

• 메모리 블록이 연속적이지 않을 수 있으므로, Cache hit rate가 낮을 수 있다.

라는 정리를 보았다. 그래서 논리적인 주소값으로 배열을 할당시키고 실제 물리적 주소값은 연속적이지 않게 구현되었나보다~ 하고 오해했었다.

하지만 그건 틀린 정리글이었다. 자바의 ArrayList는 연속적으로 메모리에 요소를 할당한다.

그렇다면 어떻게?

잘못된 정리를 고치기 위해 자바 ArrayList의 동적 할당을 담당하는 내부 메서드인 grow()함수의 동작을 정리했다.

grow(int minCapacity) 메서드

add() 메소드를 통해 배열을 할당하다가 기존 메모리 공간보다 더 큰 공간이 필요해지면 내부 배열의 크기를 늘려 ArrayList의 요소를 재할당한다.
그 일을 하는게 바로 grow() 메서드이다.

1. 현재 용량 계산:

   int oldCapacity = elementData.length;
   

   현재 배열의 크기를 oldCapacity에 저장한다.

2. 새 용량 계산:

   int newCapacity = oldCapacity + (oldCapacity >> 1);
   

   새로운 용량은 현재 용량의 1.5배로 설정한다. 비트 시프트 연산 >> 1은 현재 용량을 2로 나누는 것과 동일하다.(비트연산)
   즉, oldCapacity의 절반을 더해서 새로운 용량을 계산한다.

3. 최소 요구 용량 확인:

   if (newCapacity - minCapacity < 0)
       newCapacity = minCapacity;
   

   계산된 새로운 용량이 최소 요구 용량(minCapacity)보다 작은 경우, 새로운 용량을 최소 요구 용량으로 설정한다.

4. 최대 배열 크기 확인:

   if (newCapacity - MAX_ARRAY_SIZE > 0)
       newCapacity = hugeCapacity(minCapacity);
   

   새로운 용량이 최대 배열 크기(MAX_ARRAY_SIZE)를 초과하면, hugeCapacity 메서드를 호출하여 더 큰 용량을 계산한다. MAX_ARRAY_SIZE는 일반적으로 JVM에서 허용하는 최대 배열 크기와 관련이 있다고 한다.

5. 배열 복사:

   elementData = Arrays.copyOf(elementData, newCapacity);
   

   Arrays.copyOf 메서드를 사용하여 기존 배열을 새로운 용량의 배열로 복사한다. 이 과정에서 기존 요소들이 새로운 배열로 복사된다.

🎯 결론.

grow(int minCapacity) 메서드는 리스트의 내부 배열 용량을 늘려 추가적인 요소들을 저장할 수 있도록 한다.
기본적으로 현재 용량의 1.5배로 증가시키지만, 최소 요구 용량과 최대 배열 크기를 고려하여 최종 용량을 결정한다.

이 과정을 통해 효율적으로 가변적인 동적 배열의 크기를 관리할 수 있다!