天天看點
傳回

ArrayList源碼分析-基于JDK1.8

ArrayList基本介紹

ArrayList是一個可變的數組，相當于動态數組。與Java中的數組相比，它提供了動态的增加和減少元素。

源碼分析

成員變量 

private static final long serialVersionUID = 8683452581122892189L;//用于序列化的Id
private static final int DEFAULT_CAPACITY = 10;//預設初始化的大小
private static final Object[] EMPTY_ELEMENTDATA = {};//空的資料
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空的資料
transient Object[] elementData; //存儲資料的數組
private int size;//數組的大小

構造方法

ArrayList提供了三種構造方法

//指定初始化數組大小
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);
    }
}
//采用預設參數初始化數組，初始化一個空的數組
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//傳入一個集合
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 {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

對于不傳參數的構造方法，我們初始化的時候隻會指派一個空的數組，隻有當我們第一次add的時候才會初始化elementData為預設的初始化大小(10)。對于c.toArray might (incorrectly) not return Object[] (see 6260652)可以看這篇

文章

主要是解決toArray傳回的不是object[]的問題的一個規避方案。

Arrays#copyOf的參數說明

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    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;
}
參數 說明
original 原始數組
newLength 新資料的長度
newType 新數組的類型

Arrays#copyOf調用的是System#arraycopy
src
srcPos 原始數組的起始位置
dest 目标數組
destPos 目标數組的起始位置
length 要複制的數組元素的數目

add方法

在數組的最後添加一個

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //檢測資料是否需要擴容
    elementData[size++] = e;//給數組最後的一位
    return true;
}

擴容機制

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //第一次add的時候會走進這個if語句中，此時minCapacity是1，是以這個時候會建立的資料預設長度是10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
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);//擴容的大小是原來的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);//建立新大小的數組，并将數來的值指派給新的數組
}

在指定位置添加

public void add(int index, E element) {
    rangeCheckForAdd(index);//驗證 index的合法性
    ensureCapacityInternal(size + 1);  //檢測資料是否需要擴容
    System.arraycopy(elementData, index, elementData, index + 1, size - index);//将index及其以後的資料往數組後面移一位
    elementData[index] = element;//将index的位置指派為element
    size++;
}

set方法 

public E set(int index, E element) {
    rangeCheck(index);//index合法性判斷
    E oldValue = elementData(index);//找到原始的值
    elementData[index] = element;//将數組index替換為新值
    return oldValue;//傳回舊的值
}
E elementData(int index) {
    return (E) elementData[index];
}

remove方法

指定元素删除

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {//如果remove的為元素空，找到為空的index
                fastRemove(index);//删除
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {//找到object對應的index
                fastRemove(index);//删除
                return true;
            }
    }
    return false;
}

fastRemove

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;//需要移動的資料大小
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);//将index之後的資料往前移一位
    elementData[--size] = null; //最後一位清空
}

根據索引删除

public E remove(int index) {
    rangeCheck(index);//index合法性檢查
    modCount++;
    E oldValue = elementData(index);//index地方的值
    int numMoved = size - index - 1;//需要移動的資料大小
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);//将index之後的資料往前移一位
    elementData[--size] = null; //最後一位清空
    return oldValue;
}

public E remove(int index)

public boolean remove(Object o)

當remove的是Integer的時候，remove(5)會調用public E remove(int index)，如果想調用public boolean remove(Object o)可以remove((Integer)5)

indexOf方法

如果有這個值則傳回索引，否則傳回-1。代碼很簡單，先周遊再判斷。

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

contains方法

contains本質是調用indexOf進行判斷

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

iterator

ArrayList的周遊都是通過疊代器，我們可以通過iterator得到。通過調用hasNext和next來 不斷擷取下一個元素，直到周遊結束。進階for底層對于ArrayList也是轉化為疊代器來實作的。

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }
    //數組中下一個元素
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    //删除
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;//修改expectedModCount的值
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    //省略一些代碼
    //驗證expectedModCount和modCount
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

我們知道在周遊集合的時候不能調用集合的remove，否則會抛出ConcurrentModificationException。調用疊代器的remove則不會，我們通過對比可以看到，疊代器的remove也是通過集合remove去删除，但是還做了expectedModCount = modCount操作，這樣保證了expectedModCount和modCount相等，checkForComodification不會抛出異常。抛出ConcurrentModificationException是由于觸發了fast-fail機制引起的。

fail-fast和fail-safe
java 索引 java索引問題 java索引庫 ArrayList源碼分析 java叢集索引 java參數索引
上一篇: 阿裡雲 肖文鵬：邊緣雲創新場景探索與實踐
下一篇: LinkedList源碼-基于JDK1.8

繼續閱讀