源碼|jdk源碼-ArrayList與Vector源碼閱讀

0x584a 發布于2019-08-16 12:42 / 1223人閱讀

摘要：畢業兩個星期了，開始成為一名正式的碼農了。將指定位置的數據移除。但是問題是，為時，并不是直接一個大小為的數組，而是使用靜態變量來代替。此外，函數還做了越界檢查。返回迭代器，與之有一個搭配的輔助類。

畢業兩個星期了，開始成為一名正式的java碼農了。
一直對偏底層比較感興趣，想著深入自己的java技能，看書、讀源碼、總結、造輪子實踐都是付諸行動的方法。
說到看源碼，就應該由簡入難，逐漸加深，那就從jdk的源碼開始看起吧。

ArrayList和Vector是java標準庫提供的一種比較簡單的數據結構，也是最常用的一種。

線性表的概念 表ADT

表這種抽象概念指的是一種存放數據的容器，其中數據A1, A2, A3, ..., A_i, ... A_N有序排列。

那么在表這一抽象的數據結構模型中：

數據是有序排列的，有前后之分。

表中每個數據都有一個索引，A1元素的索引為0, A_i元素的索引為i - 1。至于索引從0開始還是從1開始編號這個不是重點。

表的大小為即為數據的個數，即N。

它的操作有：

獲取表的大小。

取出表中給定索引的數據。

給表中給定索引的位置放入數據。

向指定位置插入數據。

將指定位置的數據移除。

表有兩種實現方式，數組實現和鏈表實現。這兩種實現方式各有優劣，其中這里所說的ArrayList是數組實現方式。

實現思路

線性表的實現中是將元素放到數組中的。如果是C的數組，那其實是一塊連續的內存。
在java中也是java的原生數組，內存布局中邏輯上是連續的，物理上不一定。印象中有的jvm實現為了解決內存碎片搞類似邏輯內存的這種操作。

往線性表取出數據或拿出元素都能很直接對應到原生數組中去。
但是，線性表插入數據的這一操作要求表是能夠動態增長的，但是原生數組的大小是固定的。

線性表實現的一大重點是實現表動態增長這一要求，將其轉換、化歸到固定大小的原生數據上去。思路是，當線性表內部保存數據的數組如果不夠用了，就申請一個更大的數組，將原來數組的數據拷貝進去。

時間空間復雜度

由于線性表用數組實現，因此定位元素實際上只需要計算內存偏移量即可訪問得到，取出和放入元素的時間復雜度為O(1)。

由于數組中的元素是緊密排列的，因此在中間插入一個元素或移除一個元素需要移動后面一排數據，所以往指定位置插入或移除數據的平均時間復雜度為O(n)。

如果是往表末尾插入元素，情況比較復雜因為這可能觸發擴容操作。不觸發擴容就是O(1)，如果觸發了擴容，假設是2倍擴容，我們可以把擴容的時間均攤到前面每一個元素的插入操作上，平均來說，也是O(1)。

ArrayList的繼承結構

如上圖所示，在設計上，它的結構應該理解成 ArrayList --> List --> Collection --> Iterable：

List接口表示抽象的表，也就是上面所說的表。

Collection接口表示抽象的容器，能放元素的都算。

Iterable接口表示可迭代的對象。也即該容器內的元素都能夠通過迭代器迭代。

但是在繼承結構上，ArrayList繼承了AbstractList。這是java中通用的一種技巧，由于java8之前的接口無法指定默認方法，如果你要實現List接口，你需要實現其中的所有方法。
但是，List接口中的所有方法是大而全的，有大量方法是為了方便調用者使用而設計的衍生方法，并非實現該接口的必須方法。比如說，isEmpty方法就可以化歸到size方法上。
所以，java對于List接口會提供一個AbstractList抽象類，里面提供了部分方法的默認實現，而繼承該類的只需要實現一組最小的必須方法即可。
總而言之一句話，AbstractList的作用是給List接口提供某些方法的默認實現。

ArrayList源碼分析 屬性

先看ArrayList內部保存的屬性和狀態。

    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;

其中，最關鍵的為elementData和size。 elementData也即真正存儲元素的java原生數組。
由于ArrayList中實際保存的元素個數是少于elementData數組的大小的，也即會有部分空間的浪費，因此size屬性是用來保存ArrayList存儲的元素個數。

值得注意的是，elementData沒有訪問修飾符，我們知道默認是對包內可見的。這樣做的目的是：

即能保證使用者（包外）無法訪問到這個屬性，保證了數據隱藏；

另外一方面，實現ArrayList需要一些輔助作用的嵌套類，它們需要知道部分ArrayList的實現細節。由于它們和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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

第一個帶參數的構造函數，行為上這個都知道，創建出來的依然是個空表，看代碼也可發現執行完后size屬性為0。initialCapacity的含義是指定內部存儲數據的原生數組的初始化大小。
代碼邏輯很簡單，initialCapacity大于0時對elementData分配該大小的原生數組。但是問題是，initialCapacity為0時，并不是直接new一個大小為0的數組，而是使用靜態變量EMPTY_ELEMENTDATA來代替。
為什么？EMPTY_ELEMENTDATA是靜態變量，所有實例共享，個人猜測應該是為了省點內存吧?？墒沁@個占不了多大的內存啊，這個理由可能說服力不太強。

第二個默認構造函數，這個函數行為上也是創建空表。但是會預先將存儲數據的原生數組的大小設置為DEFAULT_CAPACITY，也就是默認值10。這樣，能避免在大小較小時頻繁擴容帶來性能損耗。

按照這個思路，代碼應該長這樣才對：

    public ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

但是實際上，我們發現DEFAULTCAPACITY_EMPTY_ELEMENTDATA其實是個空表，也是靜態變量，多實例共享的。
這實際上也可以認為是一種優化手段，因為很多場景都是直接默認構造的一個空表在哪里放著，為了節約內存，jdk實現先不實際分配空間，僅僅做一個類似標記作用的操作，之后真正使用了才會分配空間，達到一個類似“延遲分配”的效果。這些思路在擴容相關的代碼中有所體現。

get和set

get和set沒什么好說的，實際上是直接操作內部的原生數組。
不過，從下面的代碼中可以看到，在get和set之前，會做越界檢查。

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

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

        return elementData(index);
    }

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

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

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

add

下面再來看插入元素。插入有兩種：

第一種是在末尾插入。

第二種是在中間插入。

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

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

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

思路都特別顯然，主要是在操作之前，調用了ensureCapacityInternal函數，這個函數調用完畢后會保證內部數組的空間能存儲下這么多元素。
此外，void add(int, E)函數還做了越界檢查。

擴容操作

接下來看ensureCapacityInternal函數，相關實現涉及到四個函數。
這個函數的目的是保證執行完后，內部的原生數組至少能容納minCapacity個元素。
之前所說的那種“延遲分配”操作在這里就體現出來了。分析代碼流程不難發現，當elementData為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，也即前面所說到的那個標記，那么之后擴容后的原生數組空間一定不小于DEFAULT_CAPACITY，也就是前面定義處的10。

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

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

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

再看具體的擴容邏輯，也即grow函數。邏輯還不單一。首先擴容嘗試按照原來大小的1.5倍擴容，為了性能，這里除以2優化成了右移運算。
如果1.5倍不夠怎么辦？如果是我，我可能會優雅的遞歸再擴大，然而，jdk的做法是如果1.5倍不夠的話直接按照需要的大小擴容。
最后，如果實在太大，也要做一下限制，最大可達到的大小為Integer.MAX_VALUE，否則就超過了int的范圍，溢出了。

移除操作

下面是移除相關的函數，有兩個：

E remove(int)是通過索引移除。

boolean remove(Object)是通過元素移除。

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

    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
    }

按索引移除的的思路很簡單，首先把需要移除的元素拿出來，然后后面的都往前挪一個，通過數據拷貝實現。
但是，有個 特別需要注意的地方是，假設刪除之后的表大小為N，往前挪一個后，elementData[N - 1]和elementData[N]都指向了最后一個元素。這時elementData[N]仍然持有對該元素的引用。如果之后試圖移除表中最后一個元素，它可能不會及時的被gc干掉，造成無意義的額外內存占用。

按元素移除的思路也很顯然，先是找到該元素的索引，然后按索引移除。fastRemove的代碼幾乎和remove(int)一模一樣，不知道為什么復用一下。。。

最后，從代碼可以看到一點，表內元素會被移除，但是jdk對ArrayList的實現只會擴容表，而不會縮小表以減小內存占用。不過，它提供了一個trimToSize方法，將表中原生數組的空閑空間去掉：

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

很明顯，它重新分配一個正好合適的原生數組，然后拷貝過去。

removeAll&retainAll

這兩個函數很好理解：

removeAll是移除所有c中的元素

retainAll是保留所有c中的元素

這兩個函數算法幾乎一模一樣，因此抽象出一個函數batchRemove來實現。

    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

    public boolean retainAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

    private boolean batchRemove(Collection c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

核心在于try中的那三行代碼。這個算法簡化了就是這樣：

有兩個數組data和isRemove，isRemove[i]為true表示data[i]應該被移除。
要求在O(n)時間復雜度，O(1)空間復雜度，將data中isRemove[i]為true的元素移除。

算法這種東西，思路我能在腦子里想象出來畫面，但是說不清楚。。。大學里學習算法時候都寫過，就不多說了。

其它

感覺寫的有點多。。。以上是和ArrayList操作密切相關的，其它的簡單總結下吧。

subList. subList返回的是一個List，代表著該ArrayList的中間一段。這個subList實際上返回的是類似視圖的對象，它本身不存儲數據，所有的對subList的操作最終會反映到原來的那個ArrayList上來。實現在輔助類SubList中。

iterator. 返回迭代器，與之有一個搭配的輔助類Itr?；径际且恍┌b代碼。

sort. 排序是通過調用Arrays.sort實現的，所以，具體的排序算法要看Arrays.sort。

還有一個沒有看懂的問題，即在AbstractList中有一個modCount字段，ArrayList的實現中多次操作該字段。但是仍然沒有理解該字段的作用。

Vector

Vector提供的容器模型和ArrayList幾乎一模一樣，只不過它是線程安全的。
它的代碼思路上和ArrayList差不多，但是有一些實現細節上的小區別。

首先，它有一個參數capacityIncrement，能夠控制擴容的細節，看構造函數：

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

如果不指定的話，這個initialCapacity默認值為0。在內部使用屬性capacityIncrement保存。

其次，再看控制擴容的核心函數grow，研究下擴容邏輯是不是有什么差異:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

可以發現，capacityIncrement控制的是擴容的步長。
如果沒有指定步長，那么則是按照兩倍擴容，這是與ArrayList不同的地方。

總體上，它相當于synchronized同步過的ArrayList，也即它對線程安全的實現非常暴力，并未用到太多的技巧。很顯然，在并發環境下，對vector的操作直接鎖住整個vector，相當于操作vector的線程是串行操作vector，性能不高。

云服務器 GPU云服務器 ArrayList源碼源碼閱讀 Vector與ArrayList webrtc源碼閱讀

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71554.html

JDK源碼（容器篇）

摘要：三系列用于保存鍵值對，無論是，還是已棄用的或者線程安全的等，都是基于紅黑樹。是完全基于紅黑樹的，并在此基礎上實現了接口?？梢钥吹剑挥屑t黑樹，且紅黑樹是通過內部類來實現的。 JDK容器前言閱讀JDK源碼有段時間了，準備以博客的形式記錄下來，也方便復習時查閱，本文參考JDK1.8源碼。一、Collection Collection是所有容器的基類，定義了一些基礎方法。List、Se...

Soarkey 2019-08-15 14:27 評論0 收藏0
Week 2 - Java 容器 - 詳細剖析 List 之 ArrayList, Vector,

摘要：底層使用的是雙向鏈表數據結構之前為循環鏈表，取消了循環。快速隨機訪問就是通過元素的序號快速獲取元素對象對應于方法。而接口就是用來標識該類支持快速隨機訪問。僅僅是起標識作用。，中文名為雙端隊列。不同的是，是線程安全的，內部使用了進行同步。前言學習情況記錄時間：week 2 SMART子目標：Java 容器記錄在學習Java容器知識點中，關于List的需要重點記錄的知識點。...

MartinDai 2019-08-16 18:35 評論0 收藏0
List集合就這么簡單【源碼剖析】

摘要：線程不安全底層數據結構是鏈表。的默認初始化容量是，每次擴容時候增加原先容量的一半，也就是變為原來的倍刪除元素時不會減少容量，若希望減少容量則調用它不是線程安全的。前言聲明，本文用得是jdk1.8 前一篇已經講了Collection的總覽：Collection總覽，介紹了一些基礎知識。現在這篇主要講List集合的三個子類： ArrayList 底層數據結構是數組。線程不安全 ...

cpupro 2019-08-15 15:18 評論0 收藏0
這幾道Java集合框架面試題在面試中幾乎必問

摘要：若遇到哈希沖突，則將沖突的值加到鏈表中即可。之后相比于之前的版本，之后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值默認為時，將鏈表轉化為紅黑樹，以減少搜索時間。有序，唯一紅黑樹自平衡的排序二叉樹。本文是最最最常見Java面試題總結系列第三周的文章。主要內容： Arraylist 與 LinkedList 異同 ArrayList 與 Vector 區別 HashMap的底層...

bigdevil_s 2019-08-19 11:01 評論0 收藏0
Java集合總結【面試題+腦圖】，將知識點一網打盡！

摘要：而在集合中，值僅僅是一個對象罷了該對象對本身而言是無用的。將這篇文章作為集合的總結篇，但覺得沒什么好寫就回答一些面試題去了，找了一會面試題又覺得不夠系統。前言聲明，本文用的是jdk1.8 花了一個星期，把Java容器核心的知識過了一遍，感覺集合已經無所畏懼了！！(哈哈哈....)，現在來總結一下吧~~ 回顧目錄： Collection總覽 List集合就這么簡單【源碼剖析】 Ma...

yearsj 2019-08-15 15:29 評論0 收藏0