ArrayList : 크기는 어떻게 증가합니까?

ArrayList : 크기는 어떻게 증가합니까?

---

Java에 대한 기본적인 질문이 있습니다 ArrayList.

때 ArrayList기본 생성자를 사용하여 선언 및 초기화, 10 개 요소를위한 메모리 공간이 만들어집니다. 이제 11 번째 요소를 추가하면 어떻게 되나요? 요소 용량이 20 개 (또는 그 이상) 인 새 메모리 공간이 생성됩니까 (첫 번째 메모리 위치에서 새 위치로 요소를 복사해야 함) 또는 다른 것이 있습니까?

여기에서 확인 했습니다 . 그러나 나는 답을 찾지 못했습니다.

지식을 공유하십시오. 감사.

---

새 배열이 생성되고 이전 배열의 내용이 복사됩니다. 이것이 API 수준에서 아는 전부입니다. 문서 에서 인용 (내 강조) :

각 ArrayList인스턴스에는 용량이 있습니다. 용량은 목록의 요소를 저장하는 데 사용되는 배열의 크기입니다. 항상 최소한 목록 크기만큼 큽니다. ArrayList에 요소가 추가되면 용량이 자동으로 증가합니다. 요소를 추가하면 상각 된 시간 비용이 일정하다는 사실 외에는 성장 정책의 세부 사항이 명시되어 있지 않습니다.

특정 구현 ArrayList(예 : Sun)에서 실제로 발생하는 방식과 관련하여 해당 경우 소스에서 피투성이 세부 정보를 볼 수 있습니다. 그러나 물론 특정 구현의 세부 사항에 의존하는 것은 일반적으로 좋은 생각이 아닙니다.

---

Sun의 JDK6 :

나는 그것이 15 요소로 성장한다고 믿습니다. 코딩하지 않고 jdk에서 grow () 코드를 살펴 봅니다.

int newCapacity는 = 10 + (10 >> 1) = 15입니다.

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

Javadoc에서 이것이 Java 2 이상에서 나온 것이라고 말하고 있으므로 Sun JDK에서 안전한 방법입니다.

편집 : 곱셈 요소 1.5와 의 관계를 얻지 못한 사람들을 위해int newCapacity = oldCapacity + (oldCapacity >> 1);

>>숫자를 절반으로 줄이는 오른쪽 시프트 연산자입니다. 따라서
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=>int newCapacity = 1.5*oldCapacity ;

---

구현에 따라 다르지만 Sun Java 6 소스 코드에서 가져온 것입니다.

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

그것은 ensureCapacity방법에 있습니다. 다른 JDK 구현은 다를 수 있습니다.

---

arraylist에 객체를 추가하려고하면

Java는 기존 어레이에 새 객체를 보유하기에 충분한 용량이 있는지 확인합니다. 그렇지 않은 경우 더 큰 크기 의 새 배열이 생성 되고 Arrays.copyOf를 사용하여 이전 배열이 새 배열에 복사되고 새 배열 이 기존 배열에 할당됩니다.

아래 코드를보십시오 (GrepCode.com의 Java ArrayList 코드에서 가져옴).

편집하다:

public ArrayList () 초기 용량이 10 인 빈 목록을 구성합니다.

public ArrayList (int initialCapacity) 초기 용량을 지정할 수 있습니다.

public ArrayList (Collection c) 컬렉션의 반복자가 반환하는 순서대로 지정된 컬렉션의 요소를 포함하는 목록을 구성합니다.

이제 ArrayList () 생성자를 사용할 때 Size = 10 인 ArrayList를 얻 습니다. 목록에 11 번째 요소를 추가하면 새 Arraylist가 ensureCapacity () 메서드 내에 생성됩니다.

다음 공식 사용 :

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

---

기본 생성자를 사용하여 ArrayList를 선언하고 초기화하면 10 개의 요소에 대한 메모리 공간이 생성됩니다. 이제 11 번째 요소를 추가하면

ArrayList는 다음 크기로 새 개체를 만듭니다.

즉 OldCapacity * 3 / 2 + 1 = 10 * 3 / 2 + 1 = 16

---

JDK 6까지는 공식에 따라 용량이 증가 newCapacity = (oldCapacity * 3/2) + 1합니다.

JDK 7 이상에서는 공식이 newCapacity = oldCapacity + (oldCapacity >> 1).

초기 용량이 그렇다면 10다음 새로운 용량이 될 것입니다 16 in JDK6및15 in above JDK6

---

일반적으로 ArrayList 유형 컨테이너의 메모리는 두 배로 늘립니다. 따라서 처음에 10 개 항목을위한 공간이 있고 10 개를 추가 한 경우 11 번째 항목이 20 개 항목의 새 (내부) 배열에 추가됩니다. 그 이유는 내부 배열이 꽉 찰 때마다 크기를 두 배로 늘릴 때 배열이 고정 크기 증분으로 증가한 경우 항목 추가의 증분 비용이 O (n ^ 2)에서 좋은 O (n)으로 감소하기 때문입니다.

---

컨텍스트 Java 8

모든 답변을 읽은 후 gmgmiller가 java 6 컨텍스트에서 답변을 제공하고 Java 7 컨텍스트에서 또 다른 답변을 제공 했으므로 Oracle Java 8 구현의 맥락에서 여기에 답변을 제공합니다. 그러나 Java 8이 크기 증가를 구현하는 방법은 제공되지 않았습니다.

Java 8에서 크기 증가 동작은 Java 6과 동일합니다 grow. ArrayList 의 메소드를 참조하십시오 .

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

키 코드는 다음 줄입니다.

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

따라서 성장 계수도 Java 6과 같은 1.5입니다.

---

이 코드 (jdk1.8)를 살펴 보겠습니다.

@Test
    public void testArraySize() throws Exception {
        List<String> list = new ArrayList<>();
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("last");
    }

1) "last"가 삽입 될 때 줄에 중단 점을 둡니다.

2) 추가 방법로 이동 ArrayList당신은 볼 것이다

ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;

3)이 메서드가 호출하는 ensureCapacityInternal 메서드로 이동 ensureExplicitCapacity

4)

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

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

이 예에서 minCapacity는 11과 같으 11-10 > 0므로 grow방법 이 필요 합니다.

5)

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= 10 ArrayListinit 일 때이 매개 변수를 넣지 않았기 때문에 기본 용량 (10)을 사용합니다.

2) int newCapacity = oldCapacity + (oldCapacity >> 1); Here newCapacity is equal to oldCapacity plus oldCapacity with right shift by one (oldCapacity is 10 this is the binary representation 00001010 moving one bit to right we will get 00000101 which is 5 in decimal therefore newCapacity is 10 + 5 = 15)

3)

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

For example your init capacity is 1, when you add the second element into arrayList newCapacity will be equal to 1(oldCapacity) + 0 (moved to right by one bit) = 1 In this case newCapacity is less than minCapacity and elementData(array object inside arrayList) can't hold new element therefore newCapacity is equal to minCapacity

4)

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

Check if array size reach MAX_ARRAY_SIZE (which is Integer.MAX - 8) Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?

5) Finally it copy old values to the newArray with length 15

---

When ArrayList is declared and initialized using the default constructor, memory space for 10 elements is created.

NO. When ArrayList is initialized, memory allocation is made for an empty array. Memory allocation for default capacity (10) is made only upon addition of first element to ArrayList.

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

P.S. Don't have enough reputation to comment on question, so I am putting this as an answer as nobody pointed out this incorrect assumption earlier.

---

From JDK source code, I found below code

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

---

What happens is a new Array is created with n*2 spaces, then all items in the old array are copied over and the new item is inserted in the first free space. All in all, this results in O(N) add time for the ArrayList.

If you're using Eclipse, install Jad and Jadclipse to decompile the JARs held in the library. I did this to read the original source code.

---

Size of ArrayList increases with n+n/2+1 always.

---

Default capacity of ArrayList is 10. Once the Capacity reaches its maximum capacity, Size of the ArrayList will be 16, once the capacity reaches its maximum capacity of 16, size of the ArrayList will be 25 and keep on increasing based on Data size.....

How? Here is the Answer and Formula

New capacity = (Current Capacity * 3/2) + 1

So, if the default capacity is 10, then

Current Capacity = 10
New capacity = (10 * 3/2) + 1
Output is 16

---

static int getCapacity(ArrayList<?> list) throws Exception {
            Field dataField = ArrayList.class.getDeclaredField("elementData");
            dataField.setAccessible(true);
            return ((Object[]) dataField.get(list)).length;
    }

use the above method to check the size when the arraylist is being modified.

---

In Jdk 1.6: New capacity = (Current Capacity * 3/2) + 1;

In Jdk 1.7:

int j = i + (i >> 1); this is same as New capacity = (Current Capacity * 1/2) + Current Capacity;

ex:size will increase like :10-->15-->22-->33

---

ArrayList does increases the size on load factor on following cases:

• Initial Capacity: 10
• Load Factor: 1 (i.e. when the list is full)
• Growth Rate: current_size + current_size/2

Context : JDK 7

While adding an element into the ArrayList, the following public ensureCapacityInternal calls and the other private method calls happen internally to increase the size. This is what dynamically increase the size of ArrayList. while viewing the code you can understand the logic by naming conventions, because of this reason I am not adding explicit description

public boolean add(E paramE) {
        ensureCapacityInternal(this.size + 1);
        this.elementData[(this.size++)] = paramE;
        return true;
    }

private void ensureCapacityInternal(int paramInt) {
        if (this.elementData == EMPTY_ELEMENTDATA)
            paramInt = Math.max(10, paramInt);
        ensureExplicitCapacity(paramInt);
    }
private void ensureExplicitCapacity(int paramInt) {
        this.modCount += 1;
        if (paramInt - this.elementData.length <= 0)
            return;
        grow(paramInt);
    }

private void grow(int paramInt) {
    int i = this.elementData.length;
    int j = i + (i >> 1);
    if (j - paramInt < 0)
        j = paramInt;
    if (j - 2147483639 > 0)
        j = hugeCapacity(paramInt);
    this.elementData = Arrays.copyOf(this.elementData, j);
}

---

The default size of the arraylist is 10. When we add the 11th ....arraylist increases the size (n*2). The values stored in old arraylist are copied into the new arraylist whose size is 20.

참고 URL : https://stackoverflow.com/questions/4450628/arraylist-how-does-the-size-increase