Array List 의 바 텀 원리 - 확장

ArrayList 의 바 텀 데이터 구 조 는 하나의 배열 입 니 다. 배열 요소 의 유형 은 Object 형식 이 고 ArrayList 의 모든 작업 바 텀 은 배열 을 기반 으로 합 니 다.
ArrayList 의 확장 메커니즘
ArrayList 의 확장 은 주로 ArrayList 집합 에 요 소 를 추가 할 때 발생 합 니 다.add () 방법의 분석 을 통 해 알 수 있 듯 이 추가 하기 전에 집합 용량 이 추 가 된 요 소 를 내 려 놓 을 수 있 도록 확보 해 야 합 니 다.주로 다음 과 같은 몇 단 계 를 거 쳤 다.
첫째, add () 방법 에서 ensureCapacity Internal (size + 1) 방법 으로 집합 을 통 해 요 소 를 성공 적 으로 추가 하 는 최소 집합 용량 인 minCapacity 의 값 을 확인 합 니 다.매개 변 수 는 size + 1 로 집합 에 요 소 를 추가 하면 집합 중의 실제 요소 갯 수 를 나타 낸다.집합 이 원 소 를 추가 하 는 데 성공 하도록 하기 위해 서 는 집합 최소 용량 인 minCapacity 가 size + 1 이 어야 한 다 는 것 이다.ensureCapacity Internal 방법 에서 먼저 element Data 가 기본 빈 배열 인지 판단 합 니 다. 만약 그렇다면 minCapacity 는 minCapacity 와 집합 기본 용량 크기 의 큰 값 입 니 다.
둘째, ensureExplicitCapacity (minCapacity) 방법 을 사용 하여 집합 이 요 소 를 추가 하 는 데 성공 할 수 있 도록 기 존의 요소 배열 을 확장 해 야 하 는 지 확인 합 니 다.먼저 구조 적 수정 카운터 에 1 을 추가 합 니 다.그 다음 에 minCapacity 와 현재 요소 배열 의 길이 크기 를 판단 합 니 다. 만약 에 minCapacity 가 현재 요소 배열 의 길이 보다 클 때 확장 이 필요 하고 세 번 째 단계 에 들 어 갑 니 다.
셋째, 기 존의 요소 배열 을 확장 하려 면 grow (minCapacity) 방법 을 호출 하고 매개 변수 minCapacity 는 집합 을 통 해 요 소 를 추가 하 는 데 성공 하 는 최소 용량 을 확보 하기 위해 서 입 니 다.용량 을 확대 할 때 먼저 원소 배열 의 길 이 를 1.5 배 (oldCapacity + (oldCapacity > > 1) 늘 린 다음 에 용량 을 확대 한 후의 용량 과 minCapacity 를 비교 합 니 다. ① 새로운 용량 이 minCapacity 보다 적 으 면 새로운 용량 을 minCapacity 로 설정 합 니 다.② 새로운 용량 이 minCapacity 보다 크 면 새로운 용량 을 지정 합 니 다.마지막 으로 오래된 배열 을 확장 한 새 배열 로 복사 합 니 다.

//      ，       ，    

   ensureCapacityInternal(size + 1)

 /**
     * Increases the capacity of this ArrayList 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) {
        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);
        }
    }
       //          ，   DEFAULT_CAPACITY = 10
     //               ，         ，         DEFAULT_CAPACITY
    private void ensureCapacityInternal(int minCapacity) {
       //                  
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          //         ，  minCapacity    DEFAULT_CAPACITY
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
      //                  
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; //  List        

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


    /**
     * 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;
            //        MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)
            //     hugeCapacity      
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
       //     newCapacity   ，             ，  ArrayList     
        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;
    }

배열 복사 원본 코드

public static  T[] copyOf(U[] original, int newLength, Class extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
  //  c   
 @FastNative
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

Array List 의 장단 점
ArrayList 의 장점
Array List 바 텀 은 배열 로 이 루어 지 며 무 작위 접근 모드 인 데다 가 RandomAccess 인 터 페 이 스 를 실현 하기 때문에 get 을 찾 을 때 매우 빠르다.Array List 는 순서대로 요 소 를 추가 할 때 매우 편리 합 니 다. 배열 에 하나의 요 소 를 추가 할 뿐 입 니 다.아래 표 시 된 요소 에 따라 효율 이 높 습 니 다.자동 으로 용량 을 늘 릴 수 있 으 며, 기본적으로 매번 1.5 배로 용량 을 늘 릴 수 있다.
Array List 의 단점
요 소 를 삽입 하고 삭제 하 는 효율 이 높 지 않 습 니 다.요소 아래 에 표 시 된 요 소 를 찾 으 려 면 전체 요소 배열 을 옮 겨 다 녀 야 합 니 다. 효율 이 높 지 않 습 니 다.
[문제 1] 왜 Array List 의 증가 나 삭제 작업 이 상대 적 으로 효율 이 낮 습 니까?왜 그런 지 간단히 설명해 주 시 겠 어 요?
Array List 는 확장 용량 보다 작은 상황 에서 작업 효율 을 높이 는 것 이 매우 높다. 확장 과 관련 된 상황 에서 작업 효율 이 확실히 낮 고 삭제 작업 은 위치 이동 복사 가 필요 하 며 효율 이 낮다.ArrayList 에서 증가 (확장) 하거나 요 소 를 삭제 할 때 System. array Copy 를 호출 하 는 효율 이 낮은 방법 으로 처리 하기 때문에 데이터 양 이 약간 많 고 자주 삽입 하거나 삭제 해 야 하 는 작업 효율 이 낮 습 니 다. 구체 적 으로 ArrayList 의 add 와 reove 방법 을 볼 수 있 지만 ArrayList 가 자주 요소 에 접근 하 는 효율 이 매우 높 습 니 다.따라서 비슷 한 장면 을 만나면 우 리 는 가능 한 한 링크 드 리스트 를 사용 하여 대체 효율 이 높 을 것 이다.
[문제 2] 간단하게 Array List 와 Vector 의 차 이 를 말 해 볼 까요?
Array List 는 기본 배열 의 용량 이 부족 할 때 기본 확장 은 1.5 배 이 고, Vector 는 capacity Increment 가 0 이상 일 때 capacity Increment 크기 를 확대 합 니 다. 그렇지 않 으 면 원본 용량 의 2 배로 확대 합 니 다.Vector 는 스 레 드 보안 등급 에 속 하 며, Array List 는 스 레 드 가 아 닌 안전 합 니 다.
[문제 3] Vector 와 Stack 은 무엇 입 니까? 각각 어떤 특징 이 있 습 니까?
Vector 는 라인 이 안전 한 동적 그룹 으로 ArrayList 와 같이 AbstractList 를 계승 하고 List, RandomAccess, Cloneable, Serializable 인 터 페 이 스 를 실현 했다. 내부 실현 은 여전히 그룹 을 바탕 으로 한다. Vector 와 ArrayList 는 기본적으로 일치한다. 유일한 차이 점 은 Vector 는 라인 이 안전 하고 라인 이 안전 할 수 있 는 방법 앞 에 synchronized 키 워드 를 붙인다.Array List 와 유사 합 니 다. 무 작위 접근 속도 가 빠 르 고 삽입 과 제거 성능 이 떨 어 집 니 다 (배열 원인). null 요 소 를 지원 합 니 다. 순서 가 있 고 요 소 는 중복 되 며 스 레 드 가 안전 합 니 다.Stack 은 Vector 가 동적 배열 을 바탕 으로 하 는 스 레 드 안전 스 택 을 계승 하 는 것 입 니 다. 그러나 지금 은 추천 하지 않 습 니 다. Stack 은 안전 한 후진 선 출 로 스 택 의 기본 적 인 조작 방법 을 실 현 했 습 니 다 (사실은 후진 만 먼저 나 갈 수 있 는 것 이 아 닙 니 다. Vector 를 계승 하기 때문에 많은 조작 을 할 수 있 습 니 다. 엄 밀 히 말 하면 하나의 스 택 이 아 닙 니 다).그 공통점 은 모두 방법 잠 금 (즉 synchronized) 을 사용 하여 병발 안전 을 확보 한 것 이다.