Array List 의 동적 확장 소스 읽 기

Array List 는 '자동 으로 용량 을 늘 리 는 Array' 로 이해 할 수 있다.그럼 문제 가 생 겼 습 니 다. Array List 는 어떻게 확장 되 었 습 니까?
우선 Array List 소스 코드 를 엽 니 다. 로 컬 은 자바 1.8 버 전 입 니 다.첫 번 째 질문 에 대해 add (E) 방법 으로 넘 길 수 있 습 니 다.

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
   // 注意这里的size表示ArrayList的长度，而非Array(数组)的长度。

원본 코드 의 내용 은 정말 간단 합 니 다. 확 장 된 처리 가 ensureCapacity Internal 방법 에서 처리 되 는 것 을 볼 수 있 습 니 다.

 private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
    //这里的elementData是存储数据的对象，ArrayList实际上是对数组的一层封装。
    //注意minCapacity这里确定了最小值DEFAULT_CAPACITY，也就是10

ensureCapacity Internal 방법 은 또 하나의 신비 한 베일 로 계속 젖 혀 집 니 다.

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

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

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

어, 드디어 여산 의 정 체 를 보 았 다. grow (int minCapacity) 방법.우선 minCapacity 의 값 이 얼마 인지 확인 해 보 겠 습 니 다.add (E) 방법 중 에 다음 줄 이 있 습 니 다.

 ensureCapacityInternal(size + 1)

이 를 통 해 입력 값 minCapacity 의 값 은 size + 1 임 을 알 수 있 습 니 다.ensureCapacity Internal 에서 minCapacity 의 최소 값 10 을 확 정 했 습 니 다.다음은 grow (int minCapacity) 방법 중 두 줄 을 보 겠 습 니 다.

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

배열 의 초기 화 방법 이 인삼 이 없 는 new Array List () 를 호출 했다 고 가정 하면 이 두 줄 의 코드 처리 논 리 는 다음 과 같다.

oldCapacity = 0， newCapacity = 0 + 0000>>1 = 0 + 0000 = 0;
oldCapacity = 1， newCapacity = 1 + 0001>>1 = 1 + 0000 = 1;
oldCapacity = 2， newCapacity = 2 + 0010>>1 = 2 + 0001 = 3;
oldCapacity = 4， newCapacity = 4 + 0100>>1 = 4 + 0010 = 6;
oldCapacity = 7， newCapacity = 7 + 0111>>1 = 7 + 0011 = 10;
oldCapacity = 11， newCapacity = 11 + 1011>>1 = 11 + 0101 = 16;
oldCapacity = 17， newCapacity = 17 + 1 0001>>1 = 17 + 1000 = 25;
...

비트 연산 을 이해 하지 못 하 더 라 도 귀납 할 수 있 으 며, new Capacity 는 old Capacity 의 1.5 배 이다.즉, add (E) 방법 을 실행 할 때마다 배열 의 용량 크기 는 원래 의 1.5 배 로 확대 된다.
기타 방법의 읽 기: addAll(Collection extendsE> c)

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

add (E) 와 의 절 차 는 배열 을 확대 한 다음 에 배열 을 합 칩 니 다.확장 기본 논리: new Capacity 는 먼저 원래 의 1.5 배로 확대 한 다음 에 [배열 현재 용량 + 추가 크기 용량] 과 비교 하여 비교적 큰 값 을 취하 여 확장 합 니 다.add(int index,E element)

    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

이 방법 은 주로 배열 의 복사 본 을 완성 합 니 다. 먼저 [index 위 에서 끝까지] 배열 을 한 자리 뒤로 이동 한 다음 에 element 를 index 위치 에 할당 합 니 다.
이 문 제 는 작년 에 만난 면접 문제 로 당시 에 대답 하지 못 한 것 이 부 끄 러 웠 다.마음 에 걸 리 는 마음의 병 으로서 오늘 에 야 비로소 확장 절 차 를 알 게 되 었 다.미래 에 더 많은 재 미 있 는 지식 을 얻 을 수 있 기 를 바 랍 니 다.