ArrayList概述

Hello大家好，今天就來介紹一下ArrayList，說到ArrayList，很多人都知道它的底層是使用數(shù)組實(shí)現(xiàn)的，線程不安全的，說到它的特點(diǎn)，都會(huì)說查找快，增刪慢，因?yàn)槊嬖囶}大家都是這么背過來的。今天就來說說它的底層源碼吧。

10年積累的做網(wǎng)站、網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有化州免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

ArrayList更準(zhǔn)確的說是動(dòng)態(tài)數(shù)組去實(shí)現(xiàn)的，這里使用動(dòng)態(tài)兩字，是為了能夠充分體現(xiàn)它的特點(diǎn)。

再者就是ArrayList不是線程安全的，所以效率比較高，但是否這個(gè)是絕對(duì)的呢？答案是否定的 。

ArrayList底層源碼

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

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

private int size;

}

(1) ArrayList繼承AbstractList抽象類，實(shí)現(xiàn)了RandomAccess、Cloneable、Serializable接口，RandomAccess使其擁有快速訪問的能力。

(2) Cloneable其實(shí)就是一個(gè)標(biāo)記接口，只有實(shí)現(xiàn)這個(gè)接口后，然后在類中重寫Object中的clone方法，然后通過類調(diào)用clone方法才能克隆成功，如果不實(shí)現(xiàn)這個(gè)接口，則會(huì)拋出CloneNotSupportedException(克隆不被支持)異常。

(3) Serializable是序列化接口，支持序列化和反序列化。

(4) DEFAULT_CAPACITY 是ArrayList默認(rèn)的初始化集合的大小。

(5) EMPTY_ELEMENTDATA是一個(gè)空對(duì)象數(shù)組，用于空實(shí)例的共享空數(shù)組實(shí)例。

(6) DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建集合的時(shí)候使用該對(duì)象

(7) elementData用于存放當(dāng)前數(shù)據(jù)的數(shù)組對(duì)象。

(8) size是集合的大小。

(9) 當(dāng)集合中的元素超出數(shù)組規(guī)定的長(zhǎng)度時(shí)，數(shù)組就會(huì)進(jìn)行擴(kuò)容操作，擴(kuò)容操作就是ArrayList存儲(chǔ)操作緩慢的原因，尤其是當(dāng)數(shù)據(jù)量較大的時(shí)候，每次擴(kuò)容消耗的時(shí)間會(huì)越來越多。

ArrayList的構(gòu)造方法源碼

ArrayList(int initialCapacity)

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

(1) 該構(gòu)造函數(shù)很簡(jiǎn)單，直接判斷傳進(jìn)來的數(shù)值大小，要是大于零，直接初始一個(gè)該長(zhǎng)度的數(shù)組對(duì)象，并賦值給elementData，要是等于零，將空數(shù)組對(duì)象EMPTY_ELEMENTDATA賦給elementData，否則，直接拋出異常。

(2) ?該構(gòu)造函數(shù)一般使用在要初始化一個(gè)比較大數(shù)據(jù)量的的集合的時(shí)候使用。

ArrayList()

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

(1) 將DEFAULTCAPACITY_EMPTY_ELEMENTDATA空數(shù)組對(duì)象賦給elementData

ArrayList(Collection c)

public ArrayList(Collection<? extends E> c) {

    elementData = c.toArray();

    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

這里主要做了兩件事:
(1) 先將集合c轉(zhuǎn)化為數(shù)組，然后賦值給elementData數(shù)組對(duì)象。

(2) 然后判斷size和是否相等并且不等于0，是則執(zhí)行數(shù)據(jù)的賦值并重新賦值給數(shù)組對(duì)象elementData，否則直接將空數(shù)組對(duì)象賦值給elementData。

ArrayList的方法源碼分析

add()方法

public boolean add(E e) {
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}

(1) 執(zhí)行ensureCapacityInternal方法，判斷原有的數(shù)組對(duì)象是否需要擴(kuò)容。

(2) 將e對(duì)象添加到elementData數(shù)組對(duì)象中。

接下來我們來看看ensureCapacityInternal方法的源碼。

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

在ensureCapacityInternal 中調(diào)用了ensureExplicitCapacity 方法和 calculateCapacity 方法，我們來看下calculateCapacity 方法

private static int calculateCapacity(Object[] elementData, int minCapacity) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

(1) 這里的任務(wù)主要是計(jì)算容量的大小，先判斷elementData數(shù)組對(duì)象是否有初始化大小，若沒有就取DEFAULT_CAPACITY或 minCapacit中的較大者為容量的大小，若已經(jīng)初始化了就minCapacity為容量大小。

接著來看看ensureExplicitCapacity的源碼：

private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

(1) 執(zhí)行modCount自增，modCount為當(dāng)前列表結(jié)構(gòu)被修改次數(shù)。

(2) 判斷minCapacity要是大于elementData.length就執(zhí)行擴(kuò)容，否則，直接退出此方法，進(jìn)行添加元素的操作。

接著我們來看看grow方法的源碼：

private void grow(int minCapacity) {

    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    elementData = Arrays.copyOf(elementData, newCapacity);
}

(1) 這里先拿到原來數(shù)據(jù)elementData的長(zhǎng)度賦給一個(gè)變量oldCapacity，然后將原來的長(zhǎng)度擴(kuò)大1.5倍并付給oldCapacity。

(2) 判斷minCapacity 是否大于newCapacity，成立則將minCapacity賦給newCapacity，為什么要這么做呢？因?yàn)閺那暗囊粚訉拥姆椒ㄟM(jìn)行解析之后來看，minCapacity是允許擴(kuò)容后的最小長(zhǎng)度，也就是實(shí)際存有數(shù)據(jù)的最小長(zhǎng)度，要是你擴(kuò)容后的長(zhǎng)度還比minCapacity要小，那么只能將minCapacity作為容器的長(zhǎng)度。

(3) 然后判斷容器新長(zhǎng)度newCapacity是否大于容器所允許的大長(zhǎng)度MAX_ARRAY_SIZE，成立則將擴(kuò)容長(zhǎng)度設(shè)置為大可用長(zhǎng)度。

(4) 拷貝，擴(kuò)容，構(gòu)建一個(gè)新的數(shù)組。

接著我們來看看grow方法調(diào)用的hugeCapacity的源碼：

private static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();

    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

(1) 直接判斷minCapacity是否小于零，成立拋出異常，然后比較容器所允許的最小長(zhǎng)度值是否大于MAX_ARRAY_SIZE，成立則將Integer的大值賦值給minCapacity作為容器的大長(zhǎng)度。

add(int index, E element)方法

public void add(int index, E element) {

    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!

    System.arraycopy(elementData, index, elementData, index + 1,size - index);

    elementData[index] = element;
    size++;
}

(1) ?這里主要做三件事，第一件就是判斷下標(biāo)是否越界，如果是則拋出IndexOutOfBoundsException異常。

(2) 然后就是判斷是否需要擴(kuò)容，這個(gè)方法和上面的一樣，已經(jīng)說過了，就不再贅述了。

(3) 最后就是執(zhí)行數(shù)組對(duì)象index后的對(duì)象后移一位，將元素添加到指定位置。

接下來我們來看看rangeCheckForAdd的源碼

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

(1) 直接就是判斷index > size或者index < 0條件，成立就直接拋出數(shù)組下標(biāo)越界異常。

addAll(Collection c)方法

public boolean addAll(Collection<? extends E> c) {
    return addAll(this.size, c);
}

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

    rangeCheckForAdd(index);

    int cSize = c.size();

    if (cSize==0)
        return false;

    checkForComodification();

    parent.addAll(parentOffset + index, c);

    this.modCount = parent.modCount;

    this.size += cSize;
    return true;
}

private void checkForComodification() {
    if (ArrayList.this.modCount != this.modCount)
        throw new ConcurrentModificationException();
}

(1) addAll(Collection c)方法里面直接調(diào)用addAll(this.size, c)，在addAll(this.size, c)里面第一件事就是判斷是否下標(biāo)越界。

(2) 然后判斷c的大小是否大于0，如果等于0 返回 false。

(3) 檢查修改的次數(shù)是否相等，若不相等直接則拋出ConcurrentModificationException（并發(fā)修改）異常，這個(gè)也就是當(dāng)我們用迭代器循環(huán)list的時(shí)候，在其中用list的方法新增/刪除元素，就會(huì)出現(xiàn)這個(gè)錯(cuò)誤。

(4) 將元素插入到數(shù)組中，將修改次數(shù)賦值給 modCount，最后size大小加一

(5) 在進(jìn)行 add 操作時(shí)先判斷下標(biāo)是否越界，是否需要擴(kuò)容，如果需要擴(kuò)容，就復(fù)制數(shù)組，默認(rèn)擴(kuò)容一半，如果擴(kuò)容一半不夠的話，就用目標(biāo)的size作為擴(kuò)容后的容量，然后設(shè)置對(duì)應(yīng)的下標(biāo)元素值。

get()方法

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
    return (E) elementData[index];
}

(1) 這個(gè)就很簡(jiǎn)單了直接就是先判斷是否下標(biāo)越界，越界就拋出異常，最后返回指定index位置的元素值。

set()方法

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

(1) 先判斷是否越界，然后取出原來index位置的值為oldValue，將新的值element設(shè)置到index位置，最后將舊的值oldValue返回。

remove()方法

public E remove(int index) {
    rangeCheck(index);

    modCount++;

    E oldValue = elementData(index);

    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

    return oldValue;
}

(1) 判斷是否越界，然后將修改次數(shù)modCount值加1，然后就是獲得原來index位置的舊值。

(2) 然后是計(jì)算index位置后面有多少個(gè)元素，接著將index位置后的元素向前移動(dòng)一位，最后將舊值返回。

remove(Object o)方法

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

(1) 這個(gè)根據(jù)對(duì)象刪除的方法比較簡(jiǎn)單，首先判斷o對(duì)象是否為null對(duì)象，為null就遍歷集合中的元素，是否存在null值，存在執(zhí)行刪除，刪除指定對(duì)象的方法是fastRemove，原理就是計(jì)算index位置后的元素個(gè)數(shù)，然后將index后的元素都往前移動(dòng)一位，最后將最后的一位賦值為null值。

(2) 若o對(duì)象是不為null對(duì)象的時(shí)候，執(zhí)行的邏輯是一樣的，那么為什么要分開寫呢？很簡(jiǎn)單，因?yàn)樗竺嬉{(diào)用o.equals(elementData[index]方法進(jìn)行判斷，要是為null，不就報(bào)空指針異常了。

Iterator迭代器

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

private class Itr implements Iterator<E> {
    int cursor; 
    int lastRet = -1;
    int expectedModCount = modCount;
    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    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;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

(1) 迭代器中有幾個(gè)屬性比較重要，int cursor是下一個(gè)要返回的元素的索引， int lastRet = -1 ?是返回的最后一個(gè)元素的索引，默認(rèn)為-1，就是沒有的情況。

(2) hasNext方法判斷是否存在下一個(gè)元素，通過判斷以下一個(gè)下標(biāo)是否為數(shù)組大小。

(3) next方法獲取下一個(gè)元素，首先先調(diào)用checkForComodification方法檢查修改的次數(shù)是否一致，然后定義下一個(gè)元素的下標(biāo)，判斷下標(biāo)，如果下標(biāo)大于ArrayList包含的元素個(gè)數(shù)，拋出 NoSuchElementException （沒有這樣的元素異常）異常，接著拿到ArrayList中的elementData數(shù)據(jù)對(duì)象，再次判斷下標(biāo)，如果此次判斷不一致則說明數(shù)組被修改過，最后將cursor +1，指向下一個(gè)元素的下標(biāo)，最后將lastRet定義為返回的元素的下標(biāo)，然后返回下標(biāo)對(duì)應(yīng)的值。

(4) remove移除當(dāng)前元素，首先判斷最后一個(gè)元素的下標(biāo)lastRet 是否小于0，成立則不存在該元素，拋出異常，然后又調(diào)用 checkForComodification，判斷修改次數(shù)是否一致，接著調(diào)用ArrayList的remove方法，最后重新更新cursor 、 lastRet、expectedModCount的值。

本文題目：手撕ArrayList底層，透徹分析源碼-創(chuàng)新互聯(lián)
網(wǎng)站鏈接：http://chinadenli.net/article14/edgde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、建站公司、網(wǎng)站制作、企業(yè)建站、App設(shè)計(jì)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)