Array List, Array List 에 대해 알 고 싶 은 모든 것 에 정통 합 니 다.

목차

Array List, Array List 에 대해 알 고 싶 은 모든 것 에 정통 합 니 다.

서문

ArrayList 내부 구조 와 상용 방법 실현

실례 화 방법

요소 추가 add () 방법

get () 방법

원소 제거

어떻게 확 대 했 어 요

서열 화 된 문제

스 레 드 안전 문제

Array List, Array List 에 대해 알 고 싶 은 모든 것 에 정통 합 니 다.ArrayList
머리말
자바 개발 에서 Array List 는 가장 자주 사용 하 는 데이터 구조 중 하나 로 데이터 목록 을 저장 합 니 다.ArrayList 대상 을 초기 화 한 후에 우 리 는 그것 이 제공 하 는 여러 가지 방법 을 사용 할 수 있 습 니 다. 삽입, 지정 한 위치 삽입, 대량 삽입, 획득, 삭제, 비 공 판단, 저장량 획득 등 입 니 다.
비록 우 리 는 모두 능숙 하 게 사용 하지만, 이러한 의문 이 있 었 습 니까? Array List 는 내 가 add () 에 들 어간 데 이 터 를 어떻게 저장 합 니까?내 가 new Array List 대상 이 었 을 때, 그 는 얼마나 큰 용량 이 었 습 니까?용량 이 10 인 Array List 를 초기 화 했 는데 11 개의 요 소 를 삽입 할 수 있 습 니 다. 어떻게 확장 할 수 있 습 니까?다음은 Array List 소스 코드 에서 이 문제 들 을 볼 것 입 니 다.
ArrayList 내부 구조 및 상용 방법 구현
Array List 는 배열 기반 저장 소 입 니 다.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 == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData;

변수의 설명 은 이 배열 은 ArrayList 요 소 를 저장 하 는 데 사 용 됩 니 다. 배열 의 길 이 는 ArrayList 의 용량 입 니 다.빈 Array List 의 element Data 는 빈 배열 입 니 다. 데 이 터 를 처음 추가 할 때 용량 이 DEFAULT 로 확 대 됩 니 다.CAPACITY (즉 10).
실례 화 방법
Array List 는 두 가지 실례 화 방법 이 있 는데 구조 함수 라 고도 부른다.무 참 실례 화 방법 코드 는 다음 과 같다.

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

이 실례 화 방법 은 매우 간단 하 다. 사실은 요 소 를 저장 하 는 배열 element Data 에 값 을 부여 하 는 것 이다. 빈 Object 배열 이다.
참조 가 있 는 실례 화 방법 은 다음 과 같다.

private static final Object[] EMPTY_ELEMENTDATA = {};    
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);
        }
    }

방법 수신 매개 변수 initialCapacity 는 element Data 의 길 이 를 초기 화 하 는 것 으로 이 수가 0 포 이상 보다 적 으 면 0 결과 와 무 참 구조 함수 와 같 습 니 다.
요소 추가 add () 방법
추가 방법 은 두 가지 가 있 습 니 다. 하 나 는 보통 삽입 이 고 하 나 는 지정 한 위치 삽입 입 니 다.일반 방법 코드 는 다음 과 같 습 니 다.

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

방법 첫 줄 은 용량 과 관련 된 것 이 므 로 아래 에 상세 하 게 분석 하 겠 습 니 다.여기 서 두 번 째 줄 을 봅 니 다. 요 소 를 추가 하 는 것 은 목표 요소 e 를 배열 element Data 의 size 아래 에 넣 는 것 입 니 다.동시에 size 에 1 을 추가 합 니 다.아래 에서 지정 한 위치 삽입 보기:

public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }

방법 은 두 개의 인 자 를 받 습 니 다: index - 위치 삽입, element - 목표 요소.첫 번 째 줄 은 삽입 위치 가 합 리 적 인지 확인 합 니 다 (0 < index
list 에 A, B, C, D, E5 자 모 를 저장 했다 고 가정 하고 현재 add (3, "F") 를 호출 하여 F 를 삽입 합 니 다. System. arraycopy 를 호출 하여 위 치 를 바 꾼 후 설명 도 는 다음 과 같 습 니 다.
A
B
C
D
E
A
B
C
D
E
그리고 elementData [3] = "F" 를 실행 합 니 다. 전체 과정 | 원본 | A | B | C | D | E | | | |: |: |: -- |:: |: --: |:: |:: |:: | |:: | | 위치 | A | B | C | E | | 삽입 | A | B | C | F | D | E |
get () 방법

    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

get 방법 첫 줄 에서 index 가 합 법 적 인지 확인 합 니 다. 예 를 들 어 get (- 1) 을 할 수 없 을 것 입 니 다. 그리고 element Data 배열 의 index 아래 표 시 된 요 소 를 꺼 냅 니 다.
원소 제거

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

remove 방법 은 element Data 에서 index 에 있 는 요 소 를 제거 하고 이 요 소 를 되 돌려 줍 니 다. numMoved 는 변위 가 필요 한 요소 의 개수 입 니 다. 그리고 변위 를 호출 합 니 다. 그리고 마지막 요 소 를 제거 합 니 다.
어떻게 확 대 했 어 요?
위 에서 보 듯 이 add () 방법 중 에 ensureCapacity Internal () 방법 이 있 습 니 다. 이 방법 은 실제 적 으로 확장 작업 을 완 료 했 습 니 다. 확장 작업 은 두 부분 으로 나 뉘 어 있 습 니 다. 1. 최소 용량 의 값 을 확인 합 니 다. (현재 요 소 를 삽입 하기 위해 용량 이 도달 할 값)
이 최소 용량 값 은 minCapacity 변수 입 니 다. 현재 element Data 배열 이 비어 있 으 면 minCapacity = 10 입 니 다. 그렇지 않 으 면 minCapacity = size + 1;
minCapacity 가 10 보다 작 으 면 10 을 가 져 옵 니 다. minCapacity 가 element Data 의 길이 보다 크 면 grow () 방법 으로 확장 합 니 다.
2. grow () 방법 을 호출 하고 grow () 방법 은 다음 과 같다.

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5 
        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);
    }

이 방법 은 element Data 배열 의 새로운 용량 을 확인 하고 Arrays. copy Of 를 호출 하여 확장 을 완료 합 니 다. 새 용량 이 이 세 가지 수 치 를 기반 으로 하 는 지 확인 합 니 다.

최소 용량 (size + 1) minCapacity

현재 용량 의 1.5 배 element Data. lenlt 1.5 배

허 용 된 최대 용량

new Array List () 를 호출 합 니 다. 초기 화 할 때 element Data 는 비어 있 습 니 다. add () 방법 을 처음 호출 할 때 10 으로 확장 합 니 다. 11 번 째 요 소 를 추가 할 때 확장 이 필요 합 니 다. 확장 후의 값 은 15 입 니 다. 10 + (10 > 1) = 15 입 니 다. 16 번 째 요 소 를 추가 할 때 15 + (15 > 1) = 22 로 확장 합 니 다.
그래서 확장 이 필요 할 때마다 원래 의 1.5 배, 최대 Integer. MAX VALUE 를 초과 하지 않 는 다 고 대충 이해 할 수 있다.
서열 화 된 문제
앞에서 언급 했 듯 이 Array List 는 배열 을 바탕 으로 하 는 것 입 니 다. 데 이 터 를 저장 하 는 것 은 배열 형식 구성원 변수 에 두 는 것 입 니 다. 즉, 이것 입 니 다.

    transient Object[] elementData; 

이 변 수 는 transient 로 수 정 됩 니 다. transient 키워드 의 역할 은 다음 과 같 습 니 다.
transient 로 인 스 턴 스 변 수 를 설명 하면 대상 이 저장 할 때 값 을 유지 할 필요 가 없습니다. 다시 말 하면 transient 키워드 로 표 시 된 구성원 변 수 는 직렬 화 과정 에 참여 하지 않 습 니 다.
배열 요소 가 직렬 화 에 참여 하지 않 는 것 은 아 닐 까? 내 가 힘 들 게 add 에 추가 한 데 이 터 는 없 는 것 이 아 닐 까? 그러나 실제 상황 은 그렇지 않다.
Array List 는 writeObject () 와 readObject () 방법 을 실 현 했 습 니 다. 직렬 화 와 반 직렬 화 를 맞 춘 것 과 같 습 니 다. element Data 변 수 는 transient 로 수식 되 었 지만 실제 element Data 의 요 소 는 직렬 화 될 때 기록 되 었 습 니 다. 방법 은 다음 과 같 습 니 다.

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i

왜 그 랬 을 까? 앞에서 말 했 듯 이 Array List 는 동적 확장 이기 때문에 하나의 array List 가 10 개의 용량 을 가지 고 있 을 때 실제 적 으로 하나의 요소 만 저장 되 어 있 을 수 있다. 즉, size = 1 이 고 element Data. length = 10 이다. 이 럴 때 element Data 를 서열 화하 여 무엇 을 할 까? 뒤쪽 은 모두 빈 값 이다.
스 레 드 보안 문제
ArrayList 는 스 레 드 가 안전 하지 않 습 니 다. 따라서 다 중 스 레 드 환경 에서 오류 가 발생 하기 쉽 습 니 다. 다음 예 에서 20 개의 스 레 드 를 시작 합 니 다. 각 스 레 드 는 공 유 된 ArrayList 에 20 개의 요 소 를 삽입 하여 ArrayList 의 길 이 를 출력 합 니 다. ArrayList 가 스 레 드 가 안전 하 다 면 최종 결 과 는 200 이 어야 합 니 다.

public class Test {

    public static void main(String[] args)throws Exception {
        ArrayList list = new ArrayList<>();
        final CyclicBarrier cb=new CyclicBarrier(20);
        final CountDownLatch latch=new CountDownLatch(20);
        for(int i=0;i<20;i++){
            Thread t1 = new Thread(()->{
                try{
                    long cur = System.nanoTime();
                    Thread.sleep(100);
                    System.out.println(cur+"    ");
                    cb.await();
                    for(int j=0;j<20;j++){
                        list.add(j);
                    }
                    System.out.println(cur+"    ");
                    latch.countDown();
                }catch (InterruptedException |BrokenBarrierException e){
                    e.printStackTrace();
                }
            });
            t1.start();
        }
        latch.await();
        System.out.println("    ："+list.size());
    }
}

나 는 마음대로 한 번 집행 하여 다음 과 같은 결 과 를 얻 었 다.
339278509731 준 비 됐 습 니 다 339278550899613 준 비 됐 습 니 다 339278550816171 준 비 됐 습 니 다 3392785506322 준 비 됐 습 니 다 339278550595294 준 비 됐 습 니 다 3392785150751470 준 비 됐 습 니 다 3392785116680 준 비 됐 습 니 다 33927851239628 준 비 됐 습 니 다 33927851821046 준 비 됐 습 니 다 33927851959373 준 비 됐 습 니 다 33927851351182 준 비 됐 습 니 다 33927851887532 준 비 됐 습 니 다 33927855107067 준 비 됐 습 니 다.33927852538799 준 비 됐 습 니 다 33927851433286 준 비 됐 습 니 다 339277852370336 준 비 됐 습 니 다 339277852448424 준 비 됐 습 니 다 339277852126703 준 비 됐 습 니 다 3392752215500 준 비 됐 습 니 다 339277852281986 준 비 됐 습 니 다 33927522821986 집행 완료 339278550979931 집행 완료 33927850899613 집행 완료 339278550816171 집행 완료 3392785506322 집행 완료 339278550595294 집행 완료완료 339278507511470 집행 완료 339278551168680 집행 완료 33927851239628 집행 완료 339278551821046 집행 완료 33927852370336 집행 완료 33927851433286 집행 완료 3392785520338799 집행 완료 33927851959373 집행 완료 33927855107067 집행 완료 3392785178577532 집행 완료 33927855215500 집행 완료 33927855135182 집행 완료완료 33927852448424 완료 배열 크기: 397
뚜렷 한 결과 와 맞지 않 습 니 다. 몇 번 더 실행 하면 배열 이 경 계 를 넘 는 것 을 발견 할 수 있 습 니 다. 그래서 Array List 는 스 레 드 가 안전 하지 않 습 니 다.