ArrayList源碼詳解

来源:https://www.cnblogs.com/Ch1nYK/archive/2018/03/10/8542356.html
-Advertisement-
Play Games

ArrayList是一個容量能夠動態增漲的數組，它是java集合框架中一個重要的類，繼承抽象類AbstractList，實現了List介面。 實現了RandomAccess介面，該介面為標記介面，即提供了隨機訪問功能。 實現了Cloneable介面，可以調用Object的clone方法，返回對象的淺 ...


    public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是一個容量能夠動態增漲的數組，它是java集合框架中一個重要的類，繼承抽象類AbstractList，實現了List介面。
實現了RandomAccess介面，該介面為標記介面，即提供了隨機訪問功能。
實現了Cloneable介面，可以調用Object的clone方法，返回對象的淺拷貝。
實現了java.io.Serializable介面，可以進行序列化功能。

  • ArrayList的屬性

    private static final int DEFAULT_CAPACITY = 10;　　　　　　　　　//預設大小
private static final Object[] EMPTY_ELEMENTDATA = {};　　　　　 //空的數組
private transient Object[] elementData;　//存放ArrayList內元素的數組，定義了transient在實現Serializable序列化時，不會被串列化
private int size;　　//ArrayList的大小，成員變數，系統預設初始化0， 存在堆記憶體中,實際為ArrayList存放元素的個數

  • ArrayList的構造方法

    public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];　　　　　　　　//初始化一個initialCapacity大小的數組
 }
 public ArrayList() {
    super();                                                                     //ArrayList(10) jdk1.6該構造方法的實現，預設就創建10個大小的數組
    this.elementData = EMPTY_ELEMENTDATA;　　　　　　　　　//將elementData的引用指向定義的空數組（本文基於jdk1.7）
 }
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    if (elementData.getClass() != Object[].class)　　　　　　　//返回若不是Object[]將調用Arrays.copyOf方法將其轉為Object[]
        elementData = Arrays.copyOf(elementData, size, Object[].class);　　
}

  • ArrayList的方法

add方法

    //直接添加元素，添加至數組末尾
   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;        //把元素追加到數組最後一個，size+1
        return true;
    }

    //通過下標添加元素，假如當前數組大小為10，數組裡有5個元素,下標傳參只能<=5，
    //index=5 則元素直接添加至末尾
    //index<5 index原位置元素及後續所有元素都往後移一個單位，新元素插入原index元素位置
    //eg: 此時有arraylist有[1,2,3,4,5,6,7,8]size：8,我想在索引為5的時候插入1個數字1
    //add(5,1) ,arrayList最後是[1,2,3,4,5,1,6,7,8]
    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 ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {                 //假如elementDate是個空的數組，即沒有容量大小
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  //比較大小，返回大的那個數值，作為初始化數組的大小 
        }

        ensureExplicitCapacity(minCapacity);                //檢查容量是否夠，不夠就擴容
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;                             ////AbstractList里所定義，假如使用迭代器將會用到 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;                   //假設當前的ArrayList大小為12，即oldCapacity大小為12
        //12二進位為1100，右移一個單位，即0110，十進位就是6，newCapacity即為18
        int newCapacity = oldCapacity + (oldCapacity >> 1);     
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            //MAX_ARRAY_SIZE=Integer.MAX_VALUE-8 Integer.MAX_VALUE = 2147483647
        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);      //創建一個原來大小1.5倍的數組，將原數組數據複製過去
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();                           //小於0則報記憶體溢出 
            //當天arrayList大小假如大於定義的MAX_ARRAY_SIZE大小，則返回Integer的最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :                             
            MAX_ARRAY_SIZE;
    }

     private void rangeCheckForAdd(int index) {                     //檢查數組下標是否越界
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

關於方法：擴容方法grow()里Arrays.copyOf(elementData, newCapacity)，就是根據class的類型來決定是new 還是反射去構造一個泛型數組，同時利用System.arraycopy函數，批量賦值元素至新數組中。

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        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;
    }

remove方法

public E remove(int index) {
        rangeCheck(index);                      //檢查數組下標越界

        modCount++;        
        E oldValue = elementData(index);        //讀出要刪除的值
        //eg:假設當前數組值為{1,2,3,4,5,6,7,8},size為8，要刪除index為5的值，在數組裡是6
        int numMoved = size - index - 1;        //numMoved = 8 - 5 -1 = 2
        if (numMoved > 0)
        //eg:System.arraycopy(elementData,5+1,elementData,5,2)
        //eg:從數組elementData中的第6個位置開始複製2個數，複製到elementData中，從elementData中的5位置開始存放
        //eg:{1,2,3,4,5,7,8}
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
}
    //刪除該元素在數組中第一次出現的位置上的數據。 如果有該元素返回true，如果false。
    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
    }
    //for迴圈使數組裡每一個元素為null
    public void clear() {
        modCount++;

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

        size = 0;
    }
    //從2個集合中刪除重疊的數據
    public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false);
    }
    //從2個集合中獲取重疊的數據
    public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true);
    }
    //
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;  //獲得當前對象的所有元素
        int r = 0, w = 0;           //w：標記兩個集合公共元素的個數
        boolean modified = false;
        try {
            for (; r < size; r++)           ////遍歷集合A
                if (c.contains(elementData[r]) == complement)  //判斷集合B中是否包含集合A中的當前元素
                    elementData[w++] = elementData[r];          //如果包含則直接保存。
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {   //出現異常會導致 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;                   //記錄集合中元素的改變(add/remove)
                size = w;
                modified = true;
            }
        }
        return modified;
    }

set方法

    public E set(int index, E element) {
        rangeCheck(index);                      //檢查數組下標越界

        E oldValue = elementData(index);            //取出原來的元素
        elementData[index] = element;               //替換元素
        return oldValue;                            //返回原來的元素
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

get方法

    public E get(int index) {
        rangeCheck(index);              //檢查數組下標越界

        return elementData(index);
    }

iterator

    public Iterator<E> iterator() {
        return new Itr();
    }
    private class Itr implements Iterator<E> {
        int cursor;                                 //預設0
        int lastRet = -1;                           //上次返回的元素
        int expectedModCount = modCount;            //用於判斷集合是否修改過結構的標識

        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;                     //游標+1
            return (E) elementData[lastRet = i];//返回元素，並將記錄上次返回元素的下標
        }

        public void remove() {              //remove掉上次next的元素
            if (lastRet < 0)                 //判斷有沒有執行過next方法
                throw new IllegalStateException();
            checkForComodification();          //

            try {
                ArrayList.this.remove(lastRet);     //刪除上次next的元素，會修改modCount
                cursor = lastRet;                   //被刪除位置賦值給游標
                lastRet = -1;                       //不能連續刪除
                expectedModCount = modCount;        //更新expectedModCount
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {           //Fail-Fast 機制 
            if (modCount != expectedModCount)           //因此如果在使用迭代器的過程中有其他線程修改了modCount,就會拋ConcurrentModificationException()
                throw new ConcurrentModificationException();
        }

總結

ArrayList基於數組方式實現，容量限制不大於Integer.MAX_VALUE的小大，每次擴容1.5倍。有序，可以為null,允許重覆，非線程安全。

elementData屬性採用了transient來修飾，不使用Java預設的序列化機制來實例化，自己實現了序列化writeObject()和反序列化readObject()的方法。

增加和刪除會修改modCount,在迭代的時候需要保持單線程的唯一操作，如果期間進行了插入或者刪除操作，就會被迭代器檢查獲知，從而出現運行時異常。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Java併發編程實戰（chapter_1）原子性
    這是閱讀《Java編髮編程實戰》這本Java多線程領域的寶典書籍的自我總結與融匯貫通的過程。現在看到了第二部分的第七章，我自己先在我們幾個人中，做一個開頭，把自己學習到的分享出來。現在只是多線程原子性總結了出來，今天陸續吧可見性和不變性都總結出來，貼上來。這些學習，都算是基礎夯實的過程，再多的框架，... ...
  • PYTHON之路(第二篇)：PYTHON基本數據類型
    一、基礎 1、編碼 UTF-8:中文占3個位元組 GBK：中文占2個位元組 Unicode、UTF-8、GBK三者關係 2、input（）函數 輸入數字10，這裡的n是字元串'10',而非數字10 這裡如果 n * 10將輸出 '10101010101010101010'如果將字元串轉換數字，可以用In ...
  • eclipse指定jdk版本
    背景：機器上裝有jdk7和8兩個版本，命令行中查看java版本為1.7，而neon對jdk的版本要求是1.8，又不想修改系統預設的jdk版本。 解決方法：eclipse安裝目錄下找到eclipse.ini文件，增加如下參數： -vmD:\java\jdk1.8\bin 完整文件： ...
  • Python 學習筆記（四）數字（二）
    Python Python2 中除法的問題 Python2 中是除法 取整數部分 ，因而得到3/6 =0，5/2=2 可引用 from __future__ import division 模塊解決 Python 中 餘數 餘數的兩種方式 1、 % 2、divmod() ，得到商和餘數 ...
  • Struts2【UI標簽、數據回顯、資源國際化】
    Struts2UI標簽 Sturts2為了簡化我們的開發，也為我們提供了UI標簽...也就是 顯示頁面的標簽 ..... 但是呢，Struts2是服務端的框架,因此使用頁面的標簽是 需要在伺服器端解析然後再被瀏覽器解析 ， 最後才顯示在頁面上的。 因此，它的性能是不夠HTML標簽好的...HTML直 ...
  • Lucene詳解
    Lucene 是apache軟體基金會一個開放源代碼的全文檢索引擎工具包，是一個全文檢索引擎的架構，提供了完整的查詢引擎和索引引擎，部分文本分析引擎。它不是一個完整的搜索應用程式，而是為你的應用程式提供索引和搜索功能。lucene 能夠為文本類型的數據建立索引，所以你只要能把你要索引的數據格式轉化的 ...
  • centos7安裝與配置zookeeper
    由於要學習dubbo，需要用到zookeeper，所以這裡記錄一下linux的zookeeper安裝與配置 一、下載zookeeper的包：官方地址 二、把包上傳到linux上，同樣也是放到 /usr/local 目錄下，當然同樣也是放在哪裡都行，最後解壓到 /usr/local/zookeeper ...
  • JSON解析的幾種方式
    在開發中，網路請求和json解析使用的頻率是一樣高的，因為網路請求返回來的一般都是json（當然還有xml），這裡討論的是json，網路請求的工具類前面我的博客已經寫過了，這裡給出網址：http://blog.csdn.net/u014727709/article/details/53389840 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類