[Java] ArrayList 길이가 가변적으로 확장되는 방식(JDK 별)

안녕하세요. 개발자 Jindory입니다.

오늘은 ArrayList에 item을 추가할때 size가 가변적으로 증가하는 이유에 대해서 작성해보고자 합니다.

 

# 글 작성 이유

개발할 때 자주 사용하는 ArrayList의 사이즈를 정하지 않았는데도, ArrayIndexOutOfboundsexception가 발생하지 않고 사이즈가 가변적으로 증가하는 이유에 대해서 조사해보고자 합니다.

---

ArrayList 초기화 설정

ArrayList는 배열을 사용해 Object 자료형을 담을 수 있는 자료구조입니다. 초기에 설정한 길이만큼만 담을 수 있는 Array와는 달리 크기를 가변적으로 조정하여 지정한 Item를 담을 수 있는 가변배열이라고 할 수 있습니다.

 

위 코드에서와 같이 Object 자료형 배열을 멤버 변수로 가지고 있으며, 초기에 ArrayList의 Size를 설정하지 않으면 초기 사이즈 값을 10으로 설정하여 Item을 추가합니다.

---

ArrayList의 Size즈 확장 프로세스

이렇게 Size가 10으로 설정된 상태에서 10개가 넘는 Item을 추가하게 된다면 어떻게 될까요?

그림으로 보면 아래와 같은 작업이 진행됨을 알 수 있습니다.

 

추가되는 Item으로 인해 Item의 개수가 현재 ArrayList의 Size의 크기보다 커질 경우 현재 Size의 1.5큰 Array를 생성한 다음 기존의 Item들을 새로운 Array에 복사합니다.

이렇게 기존의 ArrayList의 크기를 증축하는 로직이 jdk 버전별(jdk 1.6, 1.7, 1.8)로 약간의 차이가 있다고 하여, 아래와 같이 정리를 해봤습니다.

---

JDK 1.6 ArrayList

ArrrayList 초기화

private transient Object[] elementData;

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

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

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

• Object 타입의 Element가 추가될 수 있는 Array를 멤버 변수로 선언하고, ArrayList의 size를 저장 할 size 변수를 선언합니다.
• 만일 초기 크기(initialCapacity)를 매개변수로 넘길 경우 0과의 대소 관계를 비교하여, 0보다 작을 경우 IllegalArgumentException을 발생시키고, 0보다 클 경우 해당 크기로 초기화 한 Array를 설정합니다.
• 만일 초기 크기를 설정하지 않을 경우 10을 매개변수로 하여 생성자를 만듭니다.

Add Method

/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param   minCapacity   the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
}

/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);  // Increments modCount!!
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
}

Element만 넘기는 add와 Element를 추가할 index와 Element를 넘기는 add 둘 다 ensureCapacity 메서드에서 ArrayList의 크기가 변하기 때문에 ensureCapacity 메서드에 대해서 좀 더 설명해 보겠습니다.

1. addMethod(Element e)
   1. add Method가 실행됨에 따라 ensureCapacity method에 현재의 size에 1이 증가한 값을 매개변수로 넘깁니다.
   2. ensureCapacity(int minCapacity)
      

      public void ensureCapacity(int minCapacity) {
      	modCount++;
      	int oldCapacity = elementData.length;
      	if (minCapacity > oldCapacity) {
      	    Object oldData[] = elementData;
      	    int newCapacity = (oldCapacity * 3)/2 + 1;
          	    if (newCapacity < minCapacity)
      		newCapacity = minCapacity;
                  // minCapacity is usually close to size, so this is a win:
                  elementData = Arrays.copyOf(elementData, newCapacity);
      	}
      }​

      
      
      1. modCount를 증가 시킵니다. 여기서 modCount는 ArrayList 내부에서 구조적인 변경이 일어났을 때, 이를 감지하기 위한 용도로 사용하기 위한 멤버 변수입니다. 
      2. oldCapacity 로컬 변수에 현재 ArrayList의 길이를 저장하고, oldCapacity(현재 ArrayList의 길이)와 minCapacity(증가 될 ArrayList의 길이)를 비교합니다.
      3. minCapacity(증가 될 ArrayList의 길이)가 oldCapacity(현재 ArrayList의 길이)보다 클 경우(확장)
         1. oldCapacity(현재 ArrayList의 길이) 보다 1.5배 큰 길이를 계산하여 새로운 길이(newCapacity)를 생성합니다.
         2. 만일 새로운 길이(newCapacity) 길이가 minCapacity(증가 될 ArrayList의 길이)보다 작을경우 새로운 길이(newCapacity)에 minCapacity(증가 될 ArrayList의 길이)를 대입합니다.
         3. Arrays.copyOf() 메서드를 사용하여 element를 newCapacity만큼 복사합니다.
      4. minCapacity(증가 될 ArrayList의 길이)가 oldCapacity(현재 ArrayList의 길이)보다 크지 않을 경우 ensureCapacity method를 종료합니다. 

 

JDK 1.6에서는 현재 길이보다 새로 element가 추가되었을 때의 길이가 길 경우 곱셈과 나눗셈 연산을 통해 1.5배 길이를 확장하여 ArrayList의 길이를 늘리는 것을 확인 할 수 있습니다.

---

JDK 1.7 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 = {};

/**
 * 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 == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
private transient Object[] elementData;

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

/**
 * 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) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

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

 

ArrayList를 초기화 하는 부분에서 jdk 1.6과 다른점은 ArrayList에 매개변수가 없는 생성자에서 미리 선언한 EMPTY_ELEMENTDATA를 대입하는 부분이 달라진 점입니다.

Add Method

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

// A version of rangeCheck used by add and addAll.
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 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
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

 

Element만 넘기는 add와 Element를 추가할 index와 Element를 넘기는 add 둘 다 ensureCapacityInternal 메서드에서 ArrayList의 크기가 변하기 때문에 ensureCapacityInternal 메서드에 대해서 좀 더 설명해 보겠습니다.

1. ensureCapacityInternal(int minCapacity)
   

   private void ensureCapacityInternal(int minCapacity) {
       if (elementData == EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
   
       ensureExplicitCapacity(minCapacity);
   }​

   
   
   1. add 메서드의 구현 소스에 ensureCapacityInternal에서 elementeData(ArrayList의 배열)이 EMPTY_ELEMENTDATA(초기에 비어있는 array)와 같다면 minCapacity에 DEFAULT_CAPACITY(10)과 minCapacity 중 큰 값을 minCapacity에 대입 한 후 ensureExplicitCapacity(minCapacity) 메서드를 실행합니다.
   2. ensureExplicitCapacity(int minCapacity)
      

      private void ensureExplicitCapacity(int minCapacity) {
          modCount++;
      
          // overflow-conscious code
          if (minCapacity - elementData.length > 0)
              grow(minCapacity);
      }​

      
      
      1. modCount를 증가 시킵니다. 여기서 modCount는 ArrayList 내부에서 구조적인 변경이 일어났을 때, 이를 감지하기 위한 용도로 사용하기 위한 멤버 변수입니다.
      2. minCapacity와 현재 ArrayList의 길이를 비교하여 minCapacity가 클 경우 grow 메서드를 식행합니다.(minCapacity가 크지 않을 경우 종료)
         1. grow(int minCapacity)
            

            private void grow(int minCapacity) {
                // overflow-conscious code
                int oldCapacity = elementData.length;
                int newCapacity = oldCapacity + (oldCapacity >> 1);
                if (newCapacity - minCapacity < 0)
                    newCapacity = minCapacity;
                if (newCapacity - MAX_ARRAY_SIZE > 0)
                    newCapacity = hugeCapacity(minCapacity);
                // minCapacity is usually close to size, so this is a win:
                elementData = Arrays.copyOf(elementData, newCapacity);
            }​

            
            
            1. oldCapacity에 현재 ArrayList의 길이를 대입합니다.
            2. newCapacity에 oldCapacity의 길이에 oldCapacity에 우측으로 1번 Shift한 값을 더하여 대입합니다.
            3. 만일 newCapacity가 minCapacity보다 작을 경우 newCapacity에 minCapacity를 대입합니다.
            4. 만일 newCapacity가 MAX_ARRAY_SiZE(Integer.MAX_VALUE - 8)보다 클 경우 newCapacity에 hugeCapacity 메서드를 실행합니다.
               1. hugeCapacity(int minCapacity)
                  

                  private static int hugeCapacity(int minCapacity) {
                      if (minCapacity < 0) // overflow
                           throw new OutOfMemoryError();
                      return (minCapacity > MAX_ARRAY_SIZE) ?
                          Integer.MAX_VALUE :
                          MAX_ARRAY_SIZE;
                  }

                  
                  
                  1. minCapacity값이 0보다 작을 경우 OutOfMemoryError를 발생시킵니다.
                  2. minCapacity가 MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)보다 클 경우 Integer.MAX_VALUE를 반환하고,  아닐 경우 MAX_ARRAY_SIZE를 반환 합니다.
                     여기서 MAX_ARRAY_SIZE는 ArrayList에서 생성할 수 있는 배열의 최대 크기를 제한하는 상수입니다. 이 상수로 늘어날 ArrayList의 사이즈를 제한하는 이유는 Int 범위를 초과하여 OverFlow를 방지하기 위함입니다.

JDK 1.6과 JDK 1.7의 차이는 ArrayList에서 확장 할 크기를 곱셈,나눗셈이 아닌 Shift 연산을 통해 계산했다는 것입니다. 이를 통해 더 효율적인 계산으로 효율성을 높혔다고 볼 수 있습니다. 또한 확장할 길이가 int의 값을 벗어 날 상황을 대비하여 overflow Exception handling한것도 차이라고 볼 수 있겠습니다.

---

JDK 1.8 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; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

/**
 * 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;
}

JDK 1.7과 차이점은 DEFAULTCAPACITY_EMPTY_ELEMENTDAT와 EMPTY_ELEMENTDATA array를 따로 구분하여, 만일 초기 생성자는 ArrayList 길이가 10인 DEFAULT_EMPTY_ELEMENTDATA가 할당되고, 초기 사이즈를 0으로 선언하면 EMPTY_ELEMENTDATA를 할당하게 됩니다. 이는 빈 배열과 초기 배열을 구분하기 위한 조치라고 볼 수 있을것 같습니다.

Add method

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

// A version of rangeCheck used by add and addAll.
private void rangeCheckForAdd(int index) {
   if (index > size || index < 0)
       throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
	
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 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
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

JDK 1.7과 다른 부분은 인스턴스 최초 생성시 할당되는 DEFAULTCAPACITY_EMPTY_ELEMENT와 현재 ArrayList가 같을 경우 DEFAULT_CAPACITY(초기값 10)와 minCapacity를 비교하여 더 큰 값을 반환하는 calculateCapacity 메서드가 생긴것이라고 볼 수 있습니다. 이 외의 로직은 JDK 1.7과 동일합니다.

---

글을 마무리하며...

이렇게 ArrayList의 크기가 가변적으로 변하는 일련의 과정을 JDK 버전별로 확인해봤습니다.

ArrayList Class가 이렇게 구현되었기에, 우리가 사이즈를 늘려주지 않아도 초기 크기인 10개를 넘어가는 Element가 추가될 때 가변적으로 사이즈를 증축 시켜서 Element 를 추가할 수 있었던것 같습니다.

하지만 이런 작업이 수행되면, 어플리케이션의 성능에 영향을 줍니다. 만약 저장되는 데이터 크기가 어느정도 예측 가능하다면 다음과 다음과 같이 예측한 초기 크기를 지정하는것이 성능면에서 좋습니다.

ArrayList<String> list = new ArrayList<String>(100);

---

 

혹시라도 정정할 내용이나 추가적으로 필요하신 정보가 있다면 댓글 남겨주시면 감사하겠습니다.

오늘도 Jindory 블로그에 방문해주셔서 감사합니다.

 

 

[참조]

https://www.javatpoint.com/arraylist-implementation-in-java

https://seunghyunson.tistory.com/26