Android開(kāi)發(fā)數(shù)據(jù)結(jié)構(gòu)算法ArrayList源碼詳解

更新時(shí)間：2022年10月31日 09:39:02 作者：Coolbreeze

這篇文章主要為大家介紹了Android開(kāi)發(fā)數(shù)據(jù)結(jié)構(gòu)算法ArrayList源碼詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

簡(jiǎn)介

ArrayList是List接口的一個(gè)實(shí)現(xiàn)類(lèi)，它是一個(gè)集合容器，我們通常會(huì)通過(guò)指定泛型來(lái)存儲(chǔ)同一類(lèi)數(shù)據(jù)，ArrayList默認(rèn)容器大小為10，自身可以自動(dòng)擴(kuò)容，當(dāng)容量不足時(shí)，擴(kuò)大為原來(lái)的1.5倍，和上篇文章的Vector的最大區(qū)別應(yīng)該就是線程安全了，ArrayList不能保證線程安全，但我們也可以通過(guò)其他方式來(lái)實(shí)現(xiàn)線程安全。

ArrayList源碼講解

開(kāi)頭部分代碼

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    @java.io.Serial
    //序列化uid
    private static final long serialVersionUID = 8683452581122892189L;
    //默認(rèn)初始容量
    private static final int DEFAULT_CAPACITY = 10;
    //一個(gè)空對(duì)象
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //一個(gè)空對(duì)象，如果使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建，則默認(rèn)對(duì)象內(nèi)容默認(rèn)是該值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //當(dāng)前數(shù)據(jù)對(duì)象存放地方，當(dāng)前對(duì)象不參與序列化
    transient Object[] elementData; // non-private to simplify nested class access
    //當(dāng)前數(shù)組長(zhǎng)度
    private int size;　　//其他代碼}

這部分可做出有關(guān)ArrayList的相關(guān)結(jié)構(gòu)，如下圖所示

初始化

　　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) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            elementData = EMPTY_ELEMENTDATA;
        }
    }　　//此處為copyOf運(yùn)行代碼　　
    public static <T> T[] copyOf(T[] original, 
        int newLength) {    
        return (T[]) copyOf(original, newLength, original.getClass());　　}　　
    public static <T,U> T[] copyOf(U[] original, 
         int newLength, 
         Class<? extends T[]> newType) {   
        @SuppressWarnings("unchecked")   
        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;　　
         }

以上代碼為ArrayList的初始化，分為三種方式：

1.為給定容量的初始化，傳入?yún)?shù)為數(shù)組的初始化長(zhǎng)度，當(dāng)該參數(shù)大于等于0時(shí)，進(jìn)行初始化，當(dāng)該參數(shù)小于0時(shí)，拋出異常

2.過(guò)于簡(jiǎn)單

3.首先通過(guò)c.toArray()得到了集合c對(duì)應(yīng)的數(shù)據(jù)數(shù)組，如果c也是ArrayList，直接將c.toArray()賦給elementData，而關(guān)于toArray的關(guān)鍵代碼如上代碼中關(guān)于copyOf的部分所示，從該段代碼中可知此處的Arrays.copyOf調(diào)用的是三參數(shù)版本的函數(shù)。這個(gè)三參數(shù)的copyOf函數(shù)比較復(fù)雜，作用就是返回一個(gè)指定的newType類(lèi)型的數(shù)組，這個(gè)數(shù)組的長(zhǎng)度是newLength，值從original拷貝而來(lái)?？截惖墓δ苡蒘ystem.arraycopy( )完成：如果newLength大于原數(shù)組的長(zhǎng)度，多出來(lái)的元素初始化為null；如果小于原數(shù)組長(zhǎng)度，將會(huì)進(jìn)行截?cái)嗖僮?。在這里，兩參版本調(diào)用三參版本的三個(gè)參數(shù)為original, newLength, original.getClass()，故得到的數(shù)組元素類(lèi)型和原數(shù)組類(lèi)型一致，長(zhǎng)度為newLength，數(shù)據(jù)由原數(shù)組復(fù)制而來(lái)。

總之，ArrayList的無(wú)參版toArray( )返回了一個(gè)和elemantData一模一樣的拷貝數(shù)組。所以判斷c也是ArrayList對(duì)象時(shí)，直接令elemantData 為c.toArray( )了。否則，會(huì)執(zhí)行elementData = Arrays.copyOf(a, size, Object[].class)。經(jīng)過(guò)上面的分析，三參的copyOf( )是返回一個(gè)數(shù)據(jù)內(nèi)容和a一模一樣的數(shù)組，但是數(shù)組類(lèi)型轉(zhuǎn)為Object[ ]類(lèi)型。之所以有這條語(yǔ)句，猜想可能是某些集合的toArray( )方法，返回的數(shù)組不是Object[ ]類(lèi)型，比方說(shuō)用一個(gè)類(lèi)繼承ArrayList，并且重寫(xiě)toArray( )方法，讓它返回一些別的類(lèi)型。

擴(kuò)容

    public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
            modCount++;
            grow(minCapacity);
        }
    }
　　//核心部分
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
    private Object[] grow() {
        return grow(size + 1);
    }
　　//newLength部分
    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }
    private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError(
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            return minLength;
        }
    }　　 public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

關(guān)于擴(kuò)容部分，private Object[] grow(int minCapacity)為核心部分，故我們先看這部分，if(oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)部分說(shuō)明當(dāng)該數(shù)組不是還未初始化的數(shù)組時(shí)，用newLength以及位運(yùn)算來(lái)進(jìn)行相應(yīng)的擴(kuò)容，而newLength相應(yīng)的代碼已經(jīng)貼在了上面，讓我們來(lái)進(jìn)行具體分析：此處的minGrowth在grow部分為“minCapacity - oldCapacity”，即滿(mǎn)足我們需要的容量，此處的prefGrowth在grow部分為“oldCapacity >> 1”，即原來(lái)容量的一半，當(dāng)沒(méi)有溢出時(shí)，擴(kuò)容時(shí)所擴(kuò)的容量就是這兩者中最大的那個(gè)，而當(dāng)溢出時(shí)，調(diào)用hugeLength()來(lái)滿(mǎn)足minGrowth，如果還時(shí)溢出則最多只能給到 Integer.MAX_VALUE - 8 這個(gè)量。

那么當(dāng)計(jì)算好長(zhǎng)度之后，return elementData = Arrays.copyOf(elementData, newCapacity)，即得到一個(gè)長(zhǎng)度改變，元素類(lèi)型和原數(shù)組相同的新數(shù)組。而當(dāng)該數(shù)組不滿(mǎn)足oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA這個(gè)條件時(shí)，進(jìn)行數(shù)組的初始化。

增加元素

一個(gè)元素

　　//在尾部添加一個(gè)元素　　
　　private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)　　//此處s為size的意思
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }　　//在指定位置添加元素　　
    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;　
    }　　
        private void rangeCheckForAdd(int index) {    
            if (index > size || index < 0)        
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));　　
            
        }

此處分為兩個(gè)部分，一是向尾部添加一個(gè)元素的add()，如上面所示，當(dāng)size與elementData.length相等時(shí)，說(shuō)明數(shù)組中無(wú)多余空間進(jìn)行添加，故進(jìn)行擴(kuò)容操作。將你要添加的值放入elementData[s]即數(shù)組的尾部，然后將size加一，這里的modCount是用來(lái)計(jì)算ArrayList中的結(jié)構(gòu)性變化次數(shù)。

二是在指定位置添加元素的add()，如上面所示，首先對(duì)你想要添加的元素的位置進(jìn)行判定

一堆元素

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;
        //elementData剩余容量不足則進(jìn)行擴(kuò)容
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        //上文有提到的關(guān)于arraycopy的代碼，此處為從數(shù)組尾部添加元素
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        //上文提到的判定語(yǔ)句
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        modCount++;
        //要添加進(jìn)來(lái)的元素的數(shù)量
        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);
        //計(jì)算要將多少元素向后移動(dòng)
        int numMoved = s - index;
        if (numMoved > 0)
        //要在index位置，新增numNew個(gè)元素，所以從index位置開(kāi)始，往后挪numNew位，一共有numMoved個(gè)元素需要挪動(dòng)
            System.arraycopy(elementData, index,
                    elementData, index + numNew,
                    numMoved);
        //空出來(lái)的位置即為要添加的元素的位置
        System.arraycopy(a, 0, elementData, index, numNew);
        size = s + numNew;
        return true;
    }

關(guān)于添加一堆元素時(shí)的代碼與之前的代碼較為相似，故此處直接在代碼中注釋標(biāo)出，應(yīng)該很好理解。

刪除元素

一個(gè)元素

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;
}
public staticint checkIndex(int index, int length) {    return Preconditions.checkIndex(index, length, null);}
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;
}//刪除指定元素方法
public boolean remove(Object o) {    final Object[] es = elementData;    final int size = this.size;    int i = 0;    // 正序找對(duì)應(yīng)元素下標(biāo)    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;    }    // 找到了，調(diào)用fastRemove，進(jìn)行刪除    fastRemove(es, i);    return true;}

此處的刪除是按照下標(biāo)刪，首先檢查index是否合法，接著取到oldValue值也就是要?jiǎng)h的元素值，然后調(diào)用fastRemove( )函數(shù)。在fastRemove里，首先自增modCount，再判斷要?jiǎng)h的元素是不是elemantData的第size個(gè)元素（也就是實(shí)際上的最后一個(gè)元素），如果是，不需要挪動(dòng)元素操作，直接賦值為null即可，否則，還需要將刪除位置之后的元素都往前挪一位。

當(dāng)然也有個(gè)刪除指定元素的方法，具體如上面**public boolean remove(Object o)**所示。

一堆元素

//刪除集合c中的所有元素public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false, 0, size);
    }//保留集合c中的所有元素
public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true, 0, size);
    }//核心代碼
boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {　　　　　//判斷集合c是否為空
        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;
        }　　　　　//w用于寫(xiě)入保留的元素
        int w = r++;
        try {
            for (Object e; r < end; r++)
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;　　//當(dāng)這個(gè)元素可以保留時(shí)，將其賦給es[]
        } 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 {　　　　　　　//相關(guān)善后工作　　
            modCount += end - w;
            shiftTailOverGap(es, w, end);
        }
        return true;
    }
private void shiftTailOverGap(Object[] es, int lo, int hi) {　　　　//善后工作相關(guān)代碼    System.arraycopy(es, hi, es, lo, size - hi);
　　　// 從索引hi開(kāi)始，有size-hi個(gè)元素需要往左挪，這些元素依次挪到lo以及l(fā)o之后的位置
     // 它們都向左挪了hi-lo個(gè)單位
　　// 挪動(dòng)之后，原先的索引size-1的元素，對(duì)應(yīng)的是size-1-(hi-lo)，這個(gè)索引之后的元素都賦值為null    for (int to = size, i = (size -= hi - lo); i < to; i++)        es[i] = null;}

此處的關(guān)于多個(gè)元素的操作分為刪除多個(gè)元素和保留多個(gè)元素，而這兩個(gè)操作均需要調(diào)用 “batchRemove“ ，故進(jìn)行關(guān)于其的具體分析。

“batchRemove“ 首先進(jìn)行了變量”r“的聲明，接著是一段for循環(huán)，而不管是“removeAll”還是“retainAll”都是from = 0 ，end = size，即從頭到尾用r作為索引遍歷數(shù)組，當(dāng)c.contains(es[r]) != complement時(shí)break出去。對(duì)于“removeAll”，其complement為false，故當(dāng)c.contains(es[r])為true的時(shí)候退出循環(huán)，即c中包含es[r]，即找到了要?jiǎng)h除的元素，此時(shí)的r為第一個(gè)要?jiǎng)h除的元素的索引。

以此類(lèi)推，對(duì)于“retainAll”，r為要保留的第一個(gè)元素的索引。關(guān)于后面w的部分，w是第一個(gè)要?jiǎng)h的元素索引，找到要保留的元素，則把索引w的元素賦值為此元素，再自增w。這樣子r一遍遍歷完成后，要保留的元素也都向前移動(dòng)好了。最后再進(jìn)行善后工作，具體代碼如上所示，詳細(xì)過(guò)程已做注釋。

修改元素

public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
public static
    int checkIndex(int index, int length) {
        return Preconditions.checkIndex(index, length, null);
    }
public static <X extends RuntimeException>
    int checkIndex(int index, int length,
                   BiFunction<String, List<Number>, X> oobef) {
        if (index < 0 || index >= length)
            throw outOfBoundsCheckIndex(oobef, index, length);
        return index;
    }

修改元素部分也與之前大同小異，首先對(duì)index是否合法進(jìn)行判斷，成功后再對(duì)這個(gè)元素的值進(jìn)行修改，并返回舊值

查詢(xún)?cè)?/h2>

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

關(guān)于此處，首先是indexOf函數(shù)，就是根據(jù)元素找索引，調(diào)用”indexOfRange“，從左往右找，找到第一個(gè)索引就返回；在ArrayList中還有個(gè)lastIndexOf，與前面提到的查找正好相反，為從右往左找。

還有一些其他較為簡(jiǎn)單的函數(shù)，這里就不一一列出了，下一篇試著分析下迭代器。格式?jīng)]怎么調(diào)。

以上就是Android開(kāi)發(fā)中的部分技術(shù)點(diǎn)，屬于數(shù)據(jù)結(jié)構(gòu)與算法這塊。Android開(kāi)發(fā)需要進(jìn)階的東西有很多，我們?cè)撊绾巫屵M(jìn)階自己必須了解自己技術(shù)層在那個(gè)位置；

總結(jié)

ArrayList優(yōu)點(diǎn)

ArrayList底層以數(shù)組實(shí)現(xiàn)，是一種隨機(jī)訪問(wèn)模式，再加上它實(shí)現(xiàn)了
RandomAccess接口，因此查找也就是get的時(shí)候非?？?。
ArrayList在順序添加一個(gè)元素的時(shí)候非常方便，只是往數(shù)組里面添加了一個(gè)元素而已。
根據(jù)下標(biāo)遍歷元素，效率高
根據(jù)下標(biāo)訪問(wèn)元素，效率高
可以自動(dòng)擴(kuò)容，默認(rèn)為每次擴(kuò)容為原來(lái)的1.5倍

ArrayList的缺點(diǎn)

插入和刪除元素的效率不高
根據(jù)元素的值查找元素的下標(biāo)需要遍歷整個(gè)元素?cái)?shù)組，效率不高
線程不安全

以上就是Android開(kāi)發(fā)數(shù)據(jù)結(jié)構(gòu)算法ArrayList源碼詳解的詳細(xì)內(nèi)容，更多關(guān)于Android數(shù)據(jù)結(jié)構(gòu)算法ArrayList的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: