자바 기반 Array List 의 확장 메커니즘

자바 의 Array List 대상 의 밑바닥 은 배열 을 바탕 으로 이 루어 진 것 이 고 배열 은 길이 제한 이 있다 는 것 을 알 고 있 습 니 다.그러면 배열 을 바탕 으로 이 루어 진 Array List 는 길이 제한 이 있 습 니까?우 리 는 Array List 의 구조 방법 을 통 해 분석 합 니 다.
Array List 는 우리 가 얻 을 수 있 도록 세 가지 구조 방법 을 제공 합 니 다.

ArrayList(int initialCapacity)첫 번 째 할당 길이 new

ArrayList()두 번 째 무 참 구조 로 할당 배열 의 초기 길이

가 필요 없습니다.

ArrayList(Collectionc)세 번 째 입 참 하 나 는 Collection 대상 을 계승 하여 Array List

로 전환 하 였 다.

//    ArrayList  int     
    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;
    }
	//     Collection     ArrayList
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

다음은 Array List 의 초기 길이 의 구조 방법 과 무 참 구조 방법 을 추적 하여 우리 의 답 을 얻 을 수 있 습 니 다.
1.ArrayList(int initialCapacity)

/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
    
public ArrayList(int initialCapacity) {
		//initialCapacity  0    ，  new  Object  、   initialCapacity   
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        //initialCapacity  0    ，         Object[]；
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        //initialCapacity  0    ，     
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

위 와 같은 소스 코드 분석 을 통 해 초기 길이 의 구조 방법 에서 initialCapacity 가 0 이상 인 경우 new Array List 에 서 는 initialCapacity 의 대상 배열 을 만 들 고 0 이하 인 경우 만들어 진 Object[]EMPTY 를 되 돌려 줍 니 다.ELEMENTDATA；
2.ArrayList(）

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    public ArrayList() {
    	//           ，               ，     
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

ArrayList 가 생 성 된 후에 우 리 는 이어서 그의 add()추가 방법 을 보고 ArrayList 가 실현 하 는 add 방법 을 찾 습 니 다.

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    public boolean add(E e) {
    	//1、add        ensureCapacityInternal    size+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    //3、       new    add      
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
    	//  elementData     ，   DEFAULT_CAPACITY minCapacity  ，     ，DEFAULT_CAPACITY   10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //    minCapacity
        return minCapacity;
    }

	//2、 ensureCapacityInternal        calculateCapacity(elementData, minCapacity)  ，  add    list size  
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
	//4、  minCapacity   ， modCount++，      list       list              ；
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //     list     list     ，   list        ，   grow(minCapacity)      
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }    

위의 분석 을 통 해 우 리 는 add 에 있 을 때 Array List 가 먼저 당신 이 빈 배열 인지 아 닌 지 를 판단 하 는 것 을 알 게 되 었 습 니 다.만약 그렇다면 할당 배열 의'길이 값'을 줄 것 입 니 다.기본 값 은 10 입 니 다.이 단계 에서 우 리 는 어떤 구조 방법 이 든 add 에 있 을 때 빈 배열 에 할당 하 는 길 이 를 판단 할 것 입 니 다.즉,Array List 에 있어 서 는...그 는 배열 의 길이 가 필요 하 며,배열 의 원래 길이 와 add 후의 길 이 를 비교 하여 확장 이 필요 한 지 여 부 를 판단 할 것 이다.
다음은 grow(minCapacity)확장 방법 을 살 펴 보 겠 습 니 다.

private void grow(int minCapacity) {
        //          
        int oldCapacity = elementData.length;
        //  1.5   
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //  1.5     add     ，  add              
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //  1.5     array        hugeCapacity(minCapacity)  
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //   Arrays.copyOf                ，    
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
            //  add      array         Integer     ，    array     ，  1.5   ，  array          
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

여기 서 우 리 는 소스 코드 에 대한 분석 이 끝났다.
결론:
1.new 일 때 ArrayList 에 배열 의 길이 값 을 설정 할 수도 있 고 설정 하지 않 을 수도 있 습 니 다.설정 하지 않 은 상태 에서 첫 번 째 add 일 때 기본 값 의 길 이 는 10 입 니 다.
2.add 할 때마다 add 후의 길이 값 과 배열 의 원래 길이 값 을 비교 하여 grow(int minCapacity)확장 방법 이 필요 한 지 판단 합 니 다.
3.기본 Array List 는 1.5 의 길이 로 확장 합 니 다.먼저 새로운 길이 의 배열 을 만 든 다음 에 원래 의 배열 을 할당 하여 확장 작업 을 완성 합 니 다.
4.1.5 의 길이 와 array 의 최대 길 이 를 비교 하여 array 의 최대 길 이 를 선택 할 것 인지 아니면 Integer 의 최대 길 이 를 선택 할 것 인 지 를 선택한다.
5.작업 할 때 Array List 가 데 이 터 를 얼마나 저장 해 야 하 는 지 알 수 있다 면 new 일 때 초기 값 을 부여 하 는 것 이 좋 습 니 다.배열 을 확장 하 는 것 은 시간 과 cpu 자원 을 낭비 하 는 것 이기 때 문 입 니 다.
자바 기반 의 Array List 의 확장 메커니즘 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.자바 Array List 의 확장 메커니즘 에 관 한 더 많은 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!