Array List: 사이즈는 어떻게 증가합니까?

Array List: 사이즈는 어떻게 증가합니까?

에 대한 .ArrayList.

ArrayList기본 컨스트럭터를 사용하여 선언 및 초기화되며 10개 요소의 메모리 공간이 생성됩니다.11시에요?20개 이상의 소자 용량으로 새로운 메모리 공간이 생성됩니까(첫 번째 메모리 위치에서 새 위치로 요소를 복사해야 함) 아니면 다른 어떤 것이 생성됩니까?

했습니다.ArrayListJava 1.4.2 API '''을 사용하다

지식을 공유해 주세요.감사해요.

편집: 새 링크:

• ArrayList 11 11 API를 참조하십시오.
• Java(TM) 2 SDK, Standard Edition 문서 1.4.2

새 배열이 생성되고 이전 배열의 내용이 복사됩니다.API 레벨에서 아는 것은 이것뿐입니다.문서에서 인용한 내용(주요 사항):

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

「」의 특정의 에서는, 실제로 .ArrayList(Sun's 등) 그들의 경우, 당신은 그 출처에서 피비린내 나는 세부사항을 볼 수 있다.하지만 물론 특정 구현의 세부 사항에 의존하는 것은 보통 좋은 생각이 아닙니다.

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

자바독에서는 Java 2 이상이라고 되어 있기 때문에 Sun JDK에서는 안심입니다.

EDIT : 곱셈계수 간의 연관성을 파악하지 못한 사용자용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;

내용이 것그 the the the that that that that that that that that that 。ensureCapacity방 。 은 다를 수 있습니다JDK를 사용하다

어레이 목록에 개체를 추가하려고 하면

Java는 기존 어레이에 새 개체를 저장하기에 충분한 용량이 있는지 확인합니다.그렇지 않으면 더 큰 크기의 새 어레이가 생성되고 Arrays.copyOf를 사용하여 오래된 어레이가 새 어레이에 복사되고 새 어레이가 기존 어레이에 할당됩니다.

다음 코드를 보세요(GrepCode.com의 Java Array List Code에서 발췌).

편집:

public Array List() 초기 용량이 10인 빈 목록을 만듭니다.

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

public ArrayList(Collection c) 지정된 컬렉션의 요소가 컬렉션의 반복자에 의해 반환되는 순서대로 목록을 작성합니다.

ArrayList() 컨스트럭터를 사용하면 Size=10의 ArrayList가 생성됩니다.목록의 11번째 요소를 추가하면 새 ArrayList가 sureCapacity() 메서드에 생성됩니다.

다음 수식을 사용합니다.

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

공식 JDK 6으로 됩니다(JDK 6 （ 식식 ） 。newCapacity = (oldCapacity * 3/2) + 1

7 은 JDK 7로 .newCapacity = oldCapacity + (oldCapacity >> 1).

초기 이 기기용용 so인 경우10는 "Capacity"가 .16 in JDK6 ★★★★★★★★★★★★★★★★★」15 in above JDK7

이 테스트 케이스(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) "마지막"을 삽입할 때 줄에 중단점을 표시합니다.

of 2) Add method로 합니다.ArrayList 알게 될 것이다

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

3. capacity capacitycapacitycapacity 、 [ Internal Method ]으로합니다.이는 [Internal Method], [Internal Method]를 호출합니다.ensureExplicitCapacity

4. private void secureExplicitCapacity(int minCapacity) { modCount++;

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

예에서는 입니다.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 8 constructor = "java 8 arraylist", "java 8 arraylist", "java 8 arraylist", "java 8 arraylist", "java 8 arraylist", "10", "java 8 arraylist"에서 수

2. int newCapacity = oldCapacity + (oldCapacity >> 1);입니다(「」, 「oldCapacity」, 「oldCapacity」, 「oldCapacity」, 「oldCapacity」는 1oldCapacity is 10 표현입니다.00001010오른쪽으로 조금만 움직이면 된다00000101 이하니까 5는 5는 5다.newCapacity10 + 5 = 15)

3. (Capacity - Capacity < Capacity = Capacity., 초기 용량이 1new Capacity - min Capacity < 0) new = min Capacity인 1 ( )new ArrayList<>(1) 요소를 " " " " " " "newCapacity 되다1(oldCapacity) + 0 (moved to right by one bit) = 1 "newCapacity" minCapacity"는 minCapacity보다 작습니다.elementData array （ 「 」 ）Object[]inside 는 데이터를 를 유지할 수 Capacity는 와 같습니다.inside arrayList)는 minCapacity와 .

4. (new Capacity - MAX_ARRAY_SIZE > 0) new Capacity = 거대 용량(min Capacity)인 경우,

어레이 크기가 MAX_ARRAY_SIZE(정수)에 도달했는지 확인합니다.MAX - 8) Array List의 최대 어레이 사이즈가 Integer인 이유MAX_VALUE - 8?

5. 마지막으로 길이 15의 newArray에 오래된 값을 복사합니다.

기본 컨스트럭터를 사용하여 ArrayList가 선언되고 초기화되면 10개 요소의 메모리 공간이 생성됩니다.11번째 요소를 추가하면

Array List는 다음 크기의 새 개체를 만듭니다.

즉, Old Capacity*3/2+1 = 10*3/2+1 = 16

일반적으로 ArrayList 타입 컨테이너의 메모리는 2배로 증가합니다.따라서 처음에 10개의 아이템을 저장할 공간이 있고 10개를 추가한 경우, 11번째 아이템은 20개의 아이템으로 구성된 새로운 (내부) 배열에 추가됩니다.그 이유는 내부 어레이가 가득 찰 때마다 크기가 2배로 증가하면 어레이가 고정 크기로 증가하면 항목 추가 비용이 O(n^2)에서 O(n^2)로 감소하기 때문입니다.

컨텍스트 Java 8

Oracle java 8 구현의 맥락에서 답변합니다. 모든 답변을 읽어본 결과 gmgmiller에 의해 Java 6의 컨텍스트에서 답변이 제공되었고, java 7의 컨텍스트에서 다른 답변이 제공되었음을 알 수 있었습니다.그러나 Java 8이 어떻게 크기를 늘렸는지는 밝혀지지 않았다.

8에서는 은 Java 6과 . Java 8은 Java 6을 하십시오.를 참조해 주십시오.grow어레이 리스트 서 :

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

따라서 성장률도 1.5로 Java 6과 동일합니다.

기본 컨스트럭터를 사용하여 ArrayList가 선언 및 초기화되면 10개 요소의 메모리 공간이 생성됩니다.

아니요. ArrayList가 초기화되면 빈 어레이에 메모리가 할당됩니다.기본 용량(10)에 대한 메모리 할당은 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;

추신: 질문에 대해 코멘트를 할 수 있는 충분한 평판이 없기 때문에, 지금까지 아무도 이 잘못된 가정을 지적하지 않았기 때문에, 저는 이것을 대답으로 삼습니다.

ArrayList는 다음과 같은 경우에 부하 팩터의 크기를 늘립니다.

• 초기 용량: 10
• 부하 계수: 1(리스트가 꽉 찬 경우)
• 성장률: current_size + current_size/2

컨텍스트 : JDK 7

를 에 할 때ArrayList과 같다.public ensureCapacityInternal콜 및 기타 프라이빗 메서드콜은 내부적으로 발생하여 크기를 늘립니다. 크기가 .ArrayList통해 할 수 있습니다.이에, 는 명시적인 . 코드를 보면서 명명 규칙을 통해 로직을 이해할 수 있습니다.이 때문에, 저는 명시적인 설명을 추가하지 않습니다.

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

JDK 소스 코드에서 아래 코드를 찾았습니다.

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

Java의 Array List는 가득 차면 원래 용량의 50%까지 확장됩니다.

새로운 어레이가 n*2 스페이스로 작성되면 이전 어레이의 모든 항목이 복사되고 새 항목이 첫 번째 빈 공간에 삽입됩니다.결과적으로 Array List에 O(N) 추가 시간이 발생합니다.

이클립스를 사용하는 경우 Jad 및 Jadclipse를 설치하여 라이브러리에 저장된 JAR을 디컴파일합니다.원래 소스코드를 읽기 위해서 한 거예요.

의 ArrayList 따라 n+n/2+1★★★★★★ 。

ArrayList의 기본 용량은 10입니다.용량이 최대 용량에 도달하면 Array List의 사이즈는 16, 용량이 최대 용량인 16에 도달하면 Array List의 사이즈는 25, 데이터 크기에 따라 계속 증가합니다.

어떻게요? 여기 정답과 공식입니다.

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

따라서 기본 용량이 10이면

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

위의 방법을 사용하여 배열 목록을 변경할 때 크기를 확인합니다.

Jdk 1.6의 경우: 새 용량 = (현재 용량 * 3/2) + 1;

Jdk 1.7의 경우:

int j = i + (i > > 1) 이는 새 용량 = (현재 용량 * 1/2) + 현재 용량과 동일합니다.

ex: 사이즈는:10-->15-->22-->33과 같이 증가합니다.

(구 사이즈 * 3)/2 + 1

는, 사이즈의 「」를 해 주세요.ArrayList 되다10할 수 .ArrayList.

예:기본 생성자가 있는 경우

List<String> list = new ArrayList<>();
list.size()

예:매개 변수화된 생성자가 있는 경우

List<String> list = new ArrayList<>(5);
list.size()

1. 어레이 목록의 기본 용량은 10입니다.

2. [1,2,3,4,5.....10]

3. Java에서 Arraylist의 크기를 늘리고 싶다면, 이것을 적용할 수 있습니다.

4. 공식

5. 새로운 용량, 현재 용량

6. new capacity =((현재 capacity*3/2)+1)

7. Arralist는 [1,2,3,4,5.....10,11], 어레이 리스트 용량은 16입니다.

이것은 최신 JDK 버전인 JDK 18로, https://jdk.java.net/18/에서 다운로드하거나 Github https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java에서 소스를 확인할 수 있습니다.

항목을 ArrayList에 추가하면 Java는 적어도 해당 항목에 포함된 항목과 새 항목을 유지할 수 있습니다.Java는 이 표현에 따라 용량을 1.5*의 현재 용량으로 늘리는 것을 선호합니다.

int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);.

oldCapacity >> 1는 0.5 * 1.5 * 가 아닌 0.5 * oldCapacity가 .newLength 1 1.5 * oldCapacity 1 。

코드 스니펫은 다음과 같습니다.

src/java.base/share/classes/java/util/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();
    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)];
    }
}

src/java.base/share/classes/jdk/internal/util/ArraysSupport.java

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        return hugeLength(oldLength, minGrowth);
    }
}

ArrayList는 수집 인터페이스의 클래스입니다.자바는 오픈 소스 언어입니다. 구현 방식을 변경할 수 있습니다.Java의 사전 정의된 구현은 다음과 같습니다. 새 용량 = (currentCapacity*3)/2 + 1 또는 JAVASE8 새 용량 = oldCapacity+(oldCapacity>1);

어레이 목록의 기본 크기는 10입니다.11번째 ..arraylist를 추가하면 크기가 커집니다(n*2).이전 배열 목록에 저장된 값은 크기가 20인 새 배열 목록에 복사됩니다.

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