jdk 버전별 ArrayList 구현 방식

카테고리 없음

jdk 버전별 ArrayList 구현 방식

casylm 2024. 7. 28. 20:33

자바 ArrayList는 ensureCapacity 메소드를 통해 리스트 객체의 길이를 가변적으로 관리한다.

JDK 6,7,8 버전별로 자바가 어떻게 동적 리스트의 길이를 관리하는지 알아보자

JDK6

jdk6은 add,addAll 메소드에서 ensureCapacity 메소드를 호출하여 길이를 조절한다.

ArrayList의 원소 추가

Add

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

* size: 현재 리스트의 길이

add 메소드는 ensureCapacity를 호출 할 때 (size+1)의 값을 넘겨준다.

addAll

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

* size + numNew : 현재 리스트의 길이 + 매개변수 객체의 길이

addAll 메소드는 매개변수로 넘어온 컬랙션 객체의 원소를 모두 추가하기 때문에, 기존 리스트의 size에 매개변수의 길이를 더해 ensureCapacity 함수를 호출한다.

ensureCapacity

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

다음은 자바 길이를 가변적으로 늘려주는 메소드이다.

* oldCapacity : 기존 리스트의 크기

* minCapacity : 리스트가 가져야 하는 최소 크기

* newCapacity : 새롭게 가져야하는 최적 크기

1) 기존 리스트 크기(oldCapacity)가 최소 크기(minCapacity)보다 작다면 새로운 크기(newCapacity) 를 정한다.

- 리스트가 가져야하는 최소 길이인 minCapacity가 oldCapacity보다 크면 기존 리스트를 oldData에 저장한다.

2) 새로운 리스트 길이 생성을 위해 (oldCapacity * 3) /2 + 1 을 사용하여 길이를 늘린다.

3) 새로운 길이가 최소 크기보다 작다면 최소 크기를 넣는다.

기본 Capacity에 따른 회차 별 Capacity Increment은 다음과 같다. 리스트의 default 값은 10이다.

jdk7

다음은 jdk7의 add 코드이다. jdk7은 1) overflow를 방지하기 위한 시프트 연산 2) outofMemory 예외를 방지하기 위한 최대값 제한의 특징을 가지고 있다.

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

/**
     * 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) {
        if (minCapacity > 0)
            ensureCapacityInternal(minCapacity);
    }

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

jdk7은 ensureCapacityInternal 메소드를 호출한다.

jdk6과 비교하여 overflow를 방지하는 코드가 추가되었다. 현재 리스트의 길이보다 최소 길이가 크다면 grow 함수를 호출한다.

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

* oldCapacity : 현재 리스트의 길이

* newCapacity : 비트 연산을 통해 구함

capacity 증가식의 변경

int newCapacity = (oldCapacity * 3)/2 + 1;	// jdk6

/*
	(oldCapacity * 3)/2는 오버플로우가 아닐지라도  
	oldCapacity * 3에서 오버플로우가 발생할 가능성이 있다.
*/

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

- jdk6에서 Integer.MAX_VALUE의 1/3 이 넘어가는 시점에서 *3을 하면 오버플로우가 발생한다

- jdk7에서 증가식의 방식이 비트연산자로 바뀐 이유는 오버플러우 때문이다. 비트 연산자는 단순히 비트만 이동시키면 되기 때문에 CPU 부하를 줄일 수 있다.

- 오른쪽으로 Shift를 하면 나누기 2를 한 효과가 있으므로, 최종적으로 newCapacity는 기존 길이보다 1.5배가 된다.

MAX_ARRAY_SIZE 의 선언

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

- Integer.MAX_VALUE 는 정수 int 형의 최대값 2^32를 의미한다

- 자바의 객체는 8byte 단위이므로 (최대값-8)의 값을 배열의 최대 크기로 정한다

hugeCapacity 메소드의 추가

새로운 길이가 최소 길이보다 작다면 최소 길이로 설정해준다

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

- jdk7에서는 배열의 최대 크기를 제한하고 있다

- 연속된 메모리 공간에 배열을 크게 할당하면 메모리 운영에 영향을 줄 수 있기 때문이라고 한다

- minCapacity가 음수라는 것은 int 범위를 벗어났다는 것이다.

- 이때, OutOfMemoryError() 를 발생시키는 것은 jdk6과의 차이점이다.

jdk8

최초 값 할당방식의 변경

[jdk7]
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);
}

// jdk7은 default 배열의 크기를 10으로 할당하였다

[jdk8]
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData; // non-private to simplify nested class access

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);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

- jdk7 이전까지는 생성 시 리스트의 크기를 10으로 할당하였다

ensureCapacityInternal 함수의 호출

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

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);
}

- add 메소드는 ensureCapacityInternal 메소드를 호출한다

- calculateCapacity 메소드는 리스트가 비어있을 때, default 값과 minCapacity 중 큰 값을 반환한다

[jdk 버전]

jdk6

https://github.com/openjdk/jdk6/blob/master/jdk/src/share/classes/java/util/ArrayList.java

jdk6/jdk/src/share/classes/java/util/ArrayList.java at master · openjdk/jdk6

https://openjdk.org/projects/jdk6. Contribute to openjdk/jdk6 development by creating an account on GitHub.

github.com

jdk7

https://github.com/openjdk/jdk7/blob/master/jdk/src/share/classes/java/util/ArrayList.java

jdk7/jdk/src/share/classes/java/util/ArrayList.java at master · openjdk/jdk7

https://openjdk.org/projects/jdk7 released 2011-07-28 - openjdk/jdk7