源碼篇-ArrayList

一、主要的成員變量

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 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; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

protected transient int modCount = 0;
  • DEFAULT_CAPACITY 表示初始的list容量大小
  • EMPTY_ELEMENTDATA 表示空的list集合
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 表示帶有默認(rèn)容量的空的數(shù)值集合，與EMPTY_ELEMENTDATA區(qū)分是為了第一次添加元素時(shí)如何去擴(kuò)容
  • elementData表示list對象
  • size表示list大小
  • modCount 表示集合修改次數(shù)，防止并發(fā)造成數(shù)據(jù)不一致問題

二、創(chuàng)建ArrayList

1、空構(gòu)造函數(shù)
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
  • 這里是將elementData賦予DEFAULTCAPACITY_EMPTY_ELEMENTDATA
2、帶集合參數(shù)的構(gòu)造函數(shù)
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
  • 將collection轉(zhuǎn)為集合elementData
  • 如果elementData 的長度為0，那么將elementData 賦予EMPTY_ELEMENTDATA，這里要與空構(gòu)造函數(shù)賦值進(jìn)行區(qū)別
  • 如果elementData的長讀不為0，賦值size；如果elementData對象不是Object[].class類型，轉(zhuǎn)換為Object[].class類型
3、帶初始容量大小的構(gòu)造函數(shù)
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);
    }
}
  • 如果初始容量大于0，創(chuàng)建對應(yīng)容量的數(shù)值對象，并賦給elementData
  • 如果初始容量等于0，將EMPTY_ELEMENTDATA賦給elementData

三、添加元素

1、在list末尾添加單個(gè)元素

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
  • modCount++表示修改次數(shù)加1
  • add執(zhí)行元素添加
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
  • 如果添加元素的數(shù)量與數(shù)組的長度相等，開始擴(kuò)容
  • 如果添加元素的數(shù)量與數(shù)組的長度不相等，向數(shù)組的末尾添加元素，元素的總數(shù)量加1
private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}
  • newCapacity(minCapacity)，傳入最小的擴(kuò)容大小，最后返回實(shí)際的擴(kuò)容大小
  • Arrays.copyOf會(huì)根據(jù)原數(shù)組，返回指定大小的數(shù)值
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}
  • 將容量擴(kuò)大0.5倍，如果擴(kuò)大后的容量newCapacity 小于最小擴(kuò)容量minCapacity，若elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，則返回DEFAULT_CAPACITY與minCapacity之間的最大值，否則返回minCapacity
  • 如果擴(kuò)大后的容量大于最小擴(kuò)容量，若擴(kuò)大后的容量小于最大允許容量MAX_ARRAY_SIZE ，則返回?cái)U(kuò)大后的容量newCapacity，否則根據(jù)hugeCapacity(minCapacity)進(jìn)一步判斷需要擴(kuò)大的容量
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}
  • 若最小的擴(kuò)容量minCapacity大于最大允許擴(kuò)容量MAX_ARRAY_SIZE，則返回Integer的最大值，否則返回MAX_ARRAY_SIZE
2、指定位置添加單個(gè)元素
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}
  • 檢查索引值index
  • 修改次數(shù)加1
  • 判斷是否需要擴(kuò)容
  • System.arraycopy復(fù)制元素，System.arraycopy是本地方法，用的是淺拷貝
  • 在指定位置添加元素
  • 元素?cái)?shù)量加1
3、在末尾添加集合
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}
  • 將集合轉(zhuǎn)為Object數(shù)組
  • 修改次數(shù)加1
  • 獲取要添加集合的長度
  • 判斷是否需要擴(kuò)容
  • 利用System.arraycopy將集合添加至末尾
  • 元素?cái)?shù)量加numNew
4、在指定位置添加集合
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);

    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size = s + numNew;
    return true;
}
  • 前面主要是對index的驗(yàn)證，獲取要添加集合的長度以及判斷是否需要擴(kuò)容
  • 第一次System.arraycopy主要是將原index之后的數(shù)據(jù)移動(dòng)到index+numNew
  • 第二次System.arraycopy是將集合數(shù)據(jù)添加到原list列表中
  • list元素的數(shù)量加numNew

四、查找元素

1、獲取元素的索引值
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

  • 分兩種情況，如果元素為null，遍歷elementData，返回第一個(gè)未null元素的索引值

  • 如果元素不為null，遍歷elementData，根據(jù)元素實(shí)現(xiàn)的equals方法去判斷是否相等，返回第一個(gè)相等元素索引值

  • 如果沒有查到，返回-1

2、根據(jù)索引值獲取元素
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}
  • 直接根據(jù)索引值從數(shù)值中獲取元素

五、刪除元素

1、根據(jù)索引值刪除元素
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}
  • 獲取該索引值
  • 修改次數(shù)加1，元素?cái)?shù)量減1，利用System.arraycopy對數(shù)據(jù)移動(dòng)，將末尾值改為null
  • 返回被刪除的值
2、刪除指定元素
public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}
  • 主要是遍歷獲取元素的索引值，最后根據(jù)索引值，調(diào)用fastRemove進(jìn)行刪除操作
3、批量刪除

public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false, 0, size);
}

boolean batchRemove(Collection<?> c, boolean complement,
                    final int from, final int end) {
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r;
    // Optimize for initial run of survivors
    for (r = from;; r++) {
        if (r == end)
            return false;
        if (c.contains(es[r]) != complement)
            break;
    }
    int w = r++;
    try {
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement)
                es[w++] = e;
    } catch (Throwable ex) {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        throw ex;
    } finally {
        modCount += end - w;
        shiftTailOverGap(es, w, end);
    }
    return true;
}
  • batchRemove有個(gè)參數(shù)complement，若為false，則刪除與參數(shù)c匹配的元素，本次刪除是false；若為true，則保留與c匹配的元素，retainAll函數(shù)傳入的值就是true
  • 首先遍歷elementData，如果c包含該元素，則跳出，此時(shí)已經(jīng)獲取第一個(gè)需要重寫的位置
  • 再次遍歷elementData，如果c包含該元素，則繼續(xù)遍歷；如果不包含，則將該元素寫入到es
  • 更改修改次數(shù)
  • 調(diào)用shiftTailOverGap修改元素個(gè)數(shù)，已經(jīng)剩下位置的元素置為null

4、條件批量刪除

public boolean removeIf(Predicate<? super E> filter) {
    return removeIf(filter, 0, size);
}

boolean removeIf(Predicate<? super E> filter, int i, final int end) {
    Objects.requireNonNull(filter);
    int expectedModCount = modCount;
    final Object[] es = elementData;
    // Optimize for initial run of survivors
    for (; i < end && !filter.test(elementAt(es, i)); i++)
        ;
    // Tolerate predicates that reentrantly access the collection for
    // read (but writers still get CME), so traverse once to find
    // elements to delete, a second pass to physically expunge.
    if (i < end) {
        final int beg = i;
        final long[] deathRow = nBits(end - beg);
        deathRow[0] = 1L;   // set bit 0
        for (i = beg + 1; i < end; i++)
            if (filter.test(elementAt(es, i)))
                setBit(deathRow, i - beg);
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        modCount++;
        int w = beg;
        for (i = beg; i < end; i++)
            if (isClear(deathRow, i - beg))
                es[w++] = es[i];
        shiftTailOverGap(es, w, end);
        return true;
    } else {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        return false;
    }
}
  • filter.test函數(shù)判斷是否匹配，匹配返回真，不匹配返回false
  • 獲取第一個(gè)匹配的索引值
  • 定義deathRow，若符合條件則相應(yīng)的元素位置置為1
  • isClear判斷是否需要清除，若為0，返回為真，不需要清除，那么賦值給es
  • shiftTailOverGap將剩下的位置元素置為null
5、刪除索引區(qū)間的元素
protected void removeRange(int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
        throw new IndexOutOfBoundsException(
                outOfBoundsMsg(fromIndex, toIndex));
    }
    modCount++;
    shiftTailOverGap(elementData, fromIndex, toIndex);
}


private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, size - hi);
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}
  • System.arraycopy將數(shù)值元素遷移
  • 將剩下的位置元素置為null

六、改變元素

@Override
public void replaceAll(UnaryOperator<E> operator) {
    replaceAllRange(operator, 0, size);
    modCount++;
}

private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
    Objects.requireNonNull(operator);
    final int expectedModCount = modCount;
    final Object[] es = elementData;
    for (; modCount == expectedModCount && i < end; i++)
        es[i] = operator.apply(elementAt(es, i));
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}
  • 遍歷elementData，對每個(gè)元素執(zhí)行operator.apply，最相應(yīng)的更改
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容