ArrayList 및 확장 메커니즘 에 대한 간단 한 설명

ArrayList 및 확장 메커니즘 에 대한 간단 한 설명
ArrayList
Array List 는 동적 배열 입 니 다.사실은 Array 의 복잡 한 버 전 입 니 다.동적 으로 요 소 를 추가 하고 요 소 를 삭제 하 는 방법 을 제공 하 는 동시에 Collection 과 List 인 터 페 이 스 를 실현 하여 배열 의 크기 를 유연 하 게 설정 할 수 있 습 니 다.
소스 코드 분석 을 통 해 Array List 는 세 가지 구조 방법 이 있 음 을 알 수 있다.

빈 구조 함수

들 어 오 는 수치 크기 에 따라 지정 한 길이 의 배열 을 만 듭 니 다

Collection 요소 목록 에 들 어가 서 생 성 합 니 다

//        
private static final int DEFAULT_CAPACITY = 10;
//        
private static final Object[] EMPTY_ELEMENTDATA = {
     };
//           ，           
transient Object[] elementData;
//   list     
private int size;

 /**
  *       
  */
    public ArrayList() {
     
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
 /**
   *                list  ，        0，            
   */
    public ArrayList(int initialCapacity) {
     
        //         0
        if (initialCapacity > 0) {
     
            //        initialCapacity   
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
     
            //        
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
     
           //      ，      
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    
 /**
   *       collection     ，                  
   *         null，throws NullPointerException。
   */
    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;
        }
    }
    

질문
ArrayList 장단 점
장점.
Array List 바 텀 은 배열 로 이 루어 지 며 무 작위 접근 모드 인 데다 가 RandomAccess 인 터 페 이 스 를 실현 하기 때문에 get 방법 을 실행 할 때 빠르다.
Array List 는 순서대로 요 소 를 추가 할 때 매우 장면 적 입 니 다.배열 에 하나의 요 소 를 추가 할 뿐 아래 표 시 된 요소 에 따라 요 소 를 옮 겨 다 니 며 효율 이 높 습 니 다.
자동 으로 용량 을 늘 릴 수 있 으 며,기본적으로 매번 1.5 배로 용량 을 늘 릴 수 있다
결점.
배열 에(끝 을 제외 하고)요 소 를 삽입 하고 삭제 하 는 효율 이 높 지 않 습 니 다.많은 요 소 를 이동 해 야 하기 때 문 입 니 다.
Array List 는 용량 을 확대 하 는 것 보다 작은 상황 에서 작업 효율 을 높이 는 것 이 매우 높 고 확장 과 관련 된 상황 에서 작업 효율 이 확실히 낮 으 며 삭제 작업 은 위치 이동 복사 가 필요 하 다.
또한 Array List 에서 증가(확장)하거나 요 소 를 삭제 할 때 System.array Copy()를 호출 하 는 효율 이 낮은 방법 으로 처리 하기 때문에 데이터 양 이 약간 많 거나 자주 삽입 하고 삭제 해 야 할 때 효율 이 낮 습 니 다.상기 장면 을 만나면 LinkedList 를 사용 하여 대체 해 야 합 니 다.
Array List 의 장점 은 배열 을 구성 한 후 잦 은 접근 요소 의 효율 이 매우 높다 는 데 있 기 때문이다.
ArrayList 와 Vector 의 차이
우선 List 인 터 페 이 스 는 모두 세 가지 실현 유형 이 있 습 니 다.Array List,Vector,LinkedList
Vector 는 ArrayList 와 마찬가지 로 배열 을 통 해 이 루어 집 니 다.다른 것 은 Vector 가 스 레 드 의 동기 화 를 지원 합 니 다.즉,어느 순간 에 하나의 스 레 드 만 Vector 를 쓸 수 있 고 다 중 스 레 드 를 동시에 써 서 발생 하 는 일치 하지 않 는 문 제 를 피 할 수 있 습 니 다.그러나 동기 화 를 실현 하려 면 높 은 세대 Synchronized 가 필요 합 니 다.따라서 Vector 의 효율 은 ArrayList 보다 느 립 니 다.
또한 Vector 와 Array List 의 확장 체 제 는 차이 가 있 으 며,Vector 는 매번 배열 길이 의 배로 확장 되 고,Array List 는 원래 배열 길이 의 1.5 배 이다.
용량 확장 메커니즘
add 방법
우선 Array List 의 add 방법 이 요 소 를 어떻게 추가 하 는 지 살 펴 보 겠 습 니 다.

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

ensureCapacity 내부 방법
add 가 하나의 요소 에 들 어 갔 을 때 minCapacity 는 1 이 고 이때 이들 의 최대 값 을 가 져 옵 니 다.

//         
private void ensureCapacityInternal(int minCapacity) {
     
        //            
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
     
            //                 
            // DEFAULT_CAPACITY: 10 , minCapacity: 1
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
}

ensureExplicitCapacity 방법
우 리 는 상기 조작 이 실 행 된 후에 ensureExplicitCapacity 방법 을 호출 하 는 것 을 보 았 다.이 방법 은 주로 확장 여 부 를 판단 하기 위 한 것 이다.

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

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

성장 방법
요 소 를 추가 할 때 현재 배열 의 길이 보다 크 면 grow 작업 이 실 행 됩 니 다.이 작업 은 배열 을 확대 합 니 다.

int newCapacity = oldCapacity + (oldCapacity >> 1)

핵심 코드 는 위 에 있 는 이 문장 으로 원래 의 배열 길 이 를 1.5 배로 늘 린 다음 에 복사 명령 을 실행 하고 낡은 배열 의 내용 을 새로운 배열 에 복사 하여 요소 의 확장 작업 을 실현 한다.

elementData = Arrays.copyOf(elementData, newCapacity);

System.array Copy()와 Arrays.copy Of()방법
두 소스 코드 를 보면 copy Of()내부 에서 System.array copy()방법 이 실제 호출 되 었 음 을 알 수 있 습 니 다.
array copy()는 대상 배열 이 필요 합 니 다.원 배열 을 자신 이 정의 한 배열 이나 원 배열 로 복사 할 수 있 습 니 다.또한 복사 의 시작 점 과 길 이 를 선택 하고 새 배열 에 넣 을 위 치 를 선택 할 수 있 습 니 다.copy Of()는 시스템 이 내부 에 자동 으로 새 배열 을 만 들 고 이 수 를 되 돌려 줍 니 다.
전체 코드 는 다음 과 같다.

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

private void grow(int minCapacity) {
     
        //      
        int oldCapacity = elementData.length;
        //        （         ，          ，    ，      1.5 ）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //                ，       
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            
        /**         MAX_ARRAY_SIZE,  (  ) `hugeCapacity()`       minCapacity             * MAX_ARRAY_SIZE，  minCapacity      ，      `Integer.MAX_VALUE`，  ，           *         MAX_ARRAY_SIZE    `Integer.MAX_VALUE - 8`。
          */
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //     copy      
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    /**         MAX_ARRAY_SIZE,  (  ) `hugeCapacity()`       minCapacity             * MAX_ARRAY_SIZE，  minCapacity      ，      `Integer.MAX_VALUE`，  ，           *         MAX_ARRAY_SIZE    `Integer.MAX_VALUE - 8`。
      */
    private static int hugeCapacity(int minCapacity) {
     
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

총결산
위의 방법 을 정리 함으로써 우 리 는 다음 과 같은 몇 가 지 를 정리 할 수 있다.

우리 가 첫 번 째 요 소 를 Array List 에 추가 할 때 element Data.length 는 0(빈 list 이기 때문에 게 으 름 을 피 우 는 느낌?)입 니 다.그러나 이때 ensureCapacity Internal()방법 을 실 행 했 습 니 다.기본 적 인 비 교 를 통 해 이 때 minCapacity 를 10 으로 얻 을 수 있 습 니 다.이때 minCapacity-elementData.length>0 이 만족 하기 때문에 grow(minCapacity)방법 에 들 어 갑 니 다

add 두 번 째 요 소 를 추가 할 때 minCapacity 는 2 입 니 다.이때 element Data.length()는 첫 번 째 요 소 를 추가 한 후에 용량 을 10 으로 확대 합 니 다.이때 minCapacity-element Data.length>0 이 성립 되 지 않 기 때문에 grow(minCapacity)방법 에 들 어가 지 않 습 니 다

4.567917.동시에 우 리 는 요 소 를 계속 추가 합 니 다.3,4...11.11 번 째 요 소 를 추가 할 때 minCapacity(11)가 10 보다 더 크 면 grow 작업 을 촉발 합 니 다레 퍼 런 스

https://blog.csdn.net/jmlqqs/article/details/107128147

https://www.cnblogs.com/clover-forever/p/13155160.html