庖丁解牛之ArrayList 源代碼分析和設(shè)計(jì)

背景

最近也看了一篇ArrayList的文章，講了一些ArrayList的源碼相關(guān)的知識(shí)，一直也打算寫一篇ArrayList源碼的文件，今天正好有時(shí)間，搞起！

類圖結(jié)構(gòu)

ArrayList.png

先看一下List接口定義



package java.util;

import java.util.function.UnaryOperator;

public interface List<E> extends Collection<E> {
    int size();

    boolean isEmpty();
  
    boolean contains(Object o);

    Iterator<E> iterator();
   
    Object[] toArray();

    <T> T[] toArray(T[] a);

    boolean add(E e);

    boolean remove(Object o);

    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean addAll(int index, Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    boolean retainAll(Collection<?> c);
 
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
   
    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

    void clear();

    boolean equals(Object o);

    int hashCode();

    E get(int index);
    
    E set(int index, E element);

    E remove(int index);

    int indexOf(Object o);

    int lastIndexOf(Object o);
    
    ListIterator<E> listIterator();

    ListIterator<E> listIterator(int index);

    List<E> subList(int fromIndex, int toIndex);

    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }
}

源碼分析

我們先有這樣一個(gè)概念，ArrayList的本身就是一個(gè)數(shù)組結(jié)構(gòu)，存儲(chǔ)的對象都是Object類型，我們先看一下構(gòu)造方法

構(gòu)造方法

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    private static final int DEFAULT_CAPACITY = 10;

    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 = {};

    transient Object[] elementData; // non-private to simplify nested class access
    
    private int size;

    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 {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList 構(gòu)造方法有三個(gè)

  • 默認(rèn)的構(gòu)造方法，創(chuàng)建了一個(gè)空的Object數(shù)組
  • 指定容量的構(gòu)造方法，是根據(jù)initialCapacity的值大小創(chuàng)建一個(gè)指定的Object數(shù)據(jù)
  • 指定集合的構(gòu)造方法，copy原來的集合創(chuàng)建新的集合

add方法，添加元素

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
      // overflow-conscious code
     if (minCapacity - elementData.length > 0)
        grow(minCapacity);
 }

通過add的源碼我們可以了解到，ensureCapacityInternal主要是計(jì)算數(shù)組長度是否已經(jīng)滿了，滿了就需要對ArrayList的對象數(shù)組進(jìn)行擴(kuò)容， elementData[size++] = e; 這個(gè)比較好理解，就是對這個(gè)數(shù)據(jù)進(jìn)行賦值操作，關(guān)鍵的核心代碼還是ensureCapacityInternal這個(gè)方法，當(dāng)?shù)谝淮谓oArrayList添加元素的時(shí)候就會(huì)走過這個(gè)方法中

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

    ensureExplicitCapacity(minCapacity);
}

首先創(chuàng)建一個(gè)長多未10的Object數(shù)組，接著就調(diào)用了ensureExplicitCapacity這個(gè)方法

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

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

modCount這個(gè)變量很關(guān)鍵，不管是對ArrayList執(zhí)行add、remove操作這個(gè)值都會(huì)增加，modCount這個(gè)變量主要的作用是在集合遍歷的時(shí)候來判斷集合中的數(shù)據(jù)有沒有修改，如果有修改了就跑出異常了ConcurrentModificationException,當(dāng)minCapacity大于已經(jīng)分配數(shù)據(jù)的大小時(shí)候就需要對原數(shù)組進(jìn)行擴(kuò)容，

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

擴(kuò)容的數(shù)組大小是多少了呢？新擴(kuò)容的數(shù)組大小=原來的數(shù)組+原來的數(shù)組的/2，這個(gè)地方有注意事項(xiàng)，就是最大的數(shù)組長度=Integer.MAX_VALUE - 8，為什么是這樣呢？因?yàn)橐Ａ?個(gè)字節(jié)的空間給JVM，否則可能出現(xiàn)Oom異常

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

一般情況下我們也不會(huì)關(guān)注這個(gè)，這個(gè)地方了解一下就OK了

remove 方法

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    modCount++;
    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
}

首先根據(jù)o是否為空來進(jìn)行判斷，如果o==null,先判斷集合中是否有空元素，如果過有則執(zhí)行fastRemove(index);

如果o不是空的，就遍歷集合對集合中的元素進(jìn)行equals的判斷

fastRemove我們分析一下，建設(shè)ArrayList 中數(shù)據(jù)包含如何1、2、3、4


ArrayList remove.png

要想達(dá)到這樣的效果，我們看ArrayList源碼是怎么處理的

private void fastRemove(int index) {
    modCount++;
    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
}

numMoved=size(5)-2-1=2,numMoved計(jì)算出了修改后的數(shù)據(jù)的最后一位的位置，

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

arraycopy方法是從指定的索引位置拷貝數(shù)據(jù)到des對象中，desPos是目標(biāo)對象的啟示位置，length是拷貝的數(shù)量

clear 方法

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

這個(gè)比較簡單，就是對數(shù)組中的元素賦予null

總結(jié)

1.難度并不是很復(fù)雜

2.通過源碼學(xué)習(xí)了一下ArrayList的實(shí)現(xiàn)，有很高的借鑒意義，比如對擴(kuò)容的處理和和對異常情況擴(kuò)容的處理

3.看了ArrayList的源代碼，我們可以自己思考一下如何去實(shí)現(xiàn)這個(gè)數(shù)據(jù)結(jié)構(gòu)？

最后編輯于 ：
?著作權(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ù)。

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