ArrayList의 일반적인 메소드에 대한 자세한 소스 코드 설명

　저는 거의 모든 학생들이 필기시험과 면접 시 ArrayList와 LinkedList의 유사점과 차이점에 대해 질문을 받을 것이라고 믿습니다. 전자는 배열 구현을 기반으로 하고 후자는 연결 목록 구현을 기반으로 하는 반면 전자는 임의의 방법이 빠르며 지정된 위치에 삭제 및 삽입이 느립니다. 임의 액세스는 느리고 지정된 위치에서 삭제 및 삽입은 빠릅니다. 둘 다 목록과 배열 사이의 차이점입니다.

　목록과 배열의 가장 큰 차이점 중 하나는 배열은 초기화 중에 크기를 조정해야 하며 동적으로 확장할 수 없는 반면 목록은 동적으로 확장할 수 있다는 것입니다. ArrayList는 배열을 기반으로 구현되는데 어떻게 동적 확장을 달성합니까?
ArrayList를 초기화하는 방법에는 세 가지가 있습니다.
첫 번째 기본 구성 방법의 경우 ArrayList는 용량을 초기화하지 않지만 목록의 요소 데이터 참조를 빈 배열로 가리킵니다.

private transient Object[] elementData;private static final Object[] EMPTY_ELEMENTDATA = {};

//1.ArrayList默认构造方法public ArrayList() {    super();this.elementData = EMPTY_ELEMENTDATA;
}

JDK1.6은 기본 생성자를 호출할 때에도 용량을 초기화합니다. JDK1.7은 확실히 초기화를 사용하지 않으면 낭비가 됩니다. 저장 공간을 추가한 후 용량을 초기화할 때까지 기다리세요.

//JDK1.6 ArrayListpublic ArrayList() {this(10);
}

두 번째 구성 방법은 지정된 크기의 배열을 직접 만들고 목록의 요소 배열 참조를 가리킵니다.

//2.ArrayList带有初始化大小的构造方法public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+   initialCapacity);this.elementData = new Object[initialCapacity];
}

　세 번째 생성 방법은 컬렉션을 매개 변수로 전달할 수 있지만 컬렉션의 요소는 ArrayList의 요소에서 상속되어야 합니다.

//3.可将一个集合作为ArrayList的参数构造成ArrayListpublic ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();    //将集合转换为数组size = elementData.length;    //集合中的元素大小// c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug，参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

　위에 언급된 버그가 있는데, 이는 컬렉션을 배열로 변환할 때 실수로 Object[]가 반환되지 않을 수 있다는 것을 의미합니다.

 1 package com.algorithm.sort; 2  3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.List; 6  7 /** 8  * bug编号:6260652。toArray有可能不会返回Object[] 9  * Created by yulinfeng on 2017/6/26.10  */11 public class Test {12     public static void main(String[] args) {13         correctly();14         incorrectly();15     }16     17     /**18      * 返回Object[]19      */20     private static void correctly() {21         List<String> list = new ArrayList<String>();22         list.add("test");23         System.out.println(list.getClass());24         Object[] objArray = list.toArray();25         System.out.println(objArray.getClass());26     }27     /**28      * 不返回Object[]29      */30     private static void incorrectly() {31         List<String> list = Arrays.asList("test");32         System.out.println(list.getClass());33         Object[] objArray = list.toArray();34         System.out.println(objArray.getClass());35     }36 }

실행 결과:

위의 예에서는 toArray가 항상 Object[]를 반환하지 않는다는 것을 보여줍니다. Object[]가 반환되면 Object 요소를 삽입할 수 없으므로 JDK는 "6260652"에 있습니다. 이 버그는 수정되었습니다.

　 다음으로 요소 삽입, 삭제 등 다른 방법을 살펴보겠습니다.

//ArrayList#addpublic boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保容量是否充足elementData[size++] = e;    //将元素添加至数组return true;
}

//ArrayList#ensureCapacityInternalprivate void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);     //如果此时还没有初始化列表容量大小，则对其初始化，默认容量为10    }
    ensureExplicitCapacity(minCapacity); //检查容量是否充足}

//ArrayList#ensureEcplicitCapacityprivate void ensureExplicitCapacity(int minCapacity) {
    modCount++;    //注意此变量if (minCapacity - elementData.length > 0)
        grow(minCapacity);    //容量不够则进行扩容}

　sureEcplicitCapacity 메소드에서 증가하는 modCount(수정 횟수) 변수가 있습니다.

protected transient int modCount = 0;

　이 변수는 add 메소드에서 자동으로 증가할 뿐만 아니라 추가 또는 삭제 등 ArrayList 구조가 변경될 때마다 기록되어 1씩 증가합니다. 그 이유는 Iterator 순회와 관련이 있습니다. 멀티스레딩에서. AbstractList$Itr에도 이에 해당하는 변수가 있습니다.

//AbstractList$Itrint expectedModCount = modCount;

　checkForComodification 메소드는 AbstractList$Itr#next에서 호출됩니다.

//AbstractList$Itr#checkForComodificationfinal void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

현재 실행 중인 환경이 단일 스레드인 경우 추가, 수정, 삭제 등 목록에서 어떤 작업이 수행되더라도 예기치 않은ModCount는 항상 modCount와 동일합니다. 환경은 다중 스레드이므로 한 스레드가 반복 순회 중에 다른 스레드가 이를 추가하거나 수정하는 동안 JDK는 이를 허용하지 않습니다. 이 때 ConcurrentModificationException 예외가 발생합니다. 여기에 modCount 변수가 있습니다.
ArrayList#add 메소드로 돌아가서 목록 용량이 부족할 경우, 용량을 확장하기 위해 성장 메소드가 호출됩니다.

//ArrayList#growprivate void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);    //扩容策略为，每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10，则第一次扩容大小为10 / 2 = 5，第二次扩容大小为15 / 2 = 7。if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;    //扩容策略扩得太小if (newCapacity - MAX_ARRAY_SIZE > 0)    //扩容策略扩得太大，大于最大数组大小时，最多等于Integer.MAX_VALUEnewCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

　 ArrayList는 지정된 인덱스 위치에서 요소 get 메소드를 가져옵니다.

public E get(int index) {
    rangeCheck(index);    //检查索引是否越界return elementData(index);
}

ArrayList는 배열을 기반으로 구현되므로 이 방법은 비교적 간단합니다. 범위를 벗어났는지 여부만 판단하면 됩니다. 그렇지 않으면 배열 첨자에 따라 요소를 색인화하고 반환하면 됩니다. 제거 메소드는 지정된 위치의 요소를 삭제합니다. ​

//ArrayList#removepublic E remove(int index) {
    rangeCheck(index);    //检查索引是否越界modCount++;    //记录modCount，上面已提及E oldValue = elementData(index);    //取出指定索引元素int numMoved = size - index - 1;    //移动的元素个数if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //将最后一个数组元素置为null，方便GCreturn oldValue;
}

​ 코드는 비교적 간단하며, 지정된 요소를 삭제할 때 배열 관행에 따른 ArrayList의 효율성 문제도 반영합니다. Arrays.copyOf 및 System.arraycopy 메서드에 대한 자세한 내용은 "System.arraycopy(src, srcPos, dest, destPos, length)와 Arrays.copyOf(original, newLength)의 차이점"을 참조하세요.

위 내용은 ArrayList의 일반적인 메소드에 대한 자세한 소스 코드 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!