arraylist和array在內存分配和調用、編譯上有什麼本質區別？

01-05

我知道怎麼用也知道一個有max size一個沒有。我想知道在底層實現上有什麼區別。比如array是連續的分配空間，list也是么？array的地址是首元素地址，獲取第n個元素是首地址+n-1，list是么？還是用一個連續空間存了一堆不連續的元素地址（我瞎猜的） cs轉專業學生基礎不好求大神指教！
更新：具體一些比如Java（我想C#差不多）里，最簡單的例子，int[]和ArrayList&的實現，或者複雜些SomeClass[] VS ArrayList&其實原理一樣看大家用哪個解釋方便一些

問題背景

題主最初的問題太過寬泛，所以我先在問題評論里求細化：

這個上下文是什麼？例如說什麼語言，什麼庫。
list和array在不同的上下文里可能會有很微妙的不同的意思。先確定題主想問的是什麼再說。
例如說是特指C++的std::list與std::array，還是std::vector與裸數組，還是別的上下文（例如泛指鏈表與裸數組）？

而題主補充的問題描述是：

更新：具體一些比如Java（我想C#差不多）里，最簡單的例子，int[]和ArrayList&的實現，或者複雜些SomeClass[] VS ArrayList&其實原理一樣看大家用哪個解釋方便一些

也就是說題主關心的不是偏向鏈表與數組的對比，而是「動態數組」與「數組」的對比。

事實上原本寬泛的問題描述在不同語境下可以有很多不同的有趣的答案。

最典型的「list」的理解就是採用「單向鏈表」的解釋。這在很多環境里都適用，例如各種函數式語言的list類型，以及例如C++的 std::list& 。

但更有趣的是對「array」的理解的差異。雖然一般大家說起「數組」就覺得應該是一種密集的、連續的存儲容器，但不同上下文里「array」具體說的是怎樣的東西還真不一定都是那樣。

例如說JavaScript里的Array類型就不保證是真的數組，而可能是下面的的任何一種可能：

密集數組（dense array）：此時具體實現可能跟下面要提到的C#的 List& 或者Java的 ArrayList& 類似
稀疏數組（sparse array）：此時具體實現可能實際上是個HashMap
關聯數組（associative array）：下標不是UInt32的情況。此時具體實現也可能是個HashMap。
還有以上的各種組合方式…

JavaScript的Array的情況可以參考另一個回答：JavaScript中使用object[key]查找屬性的過程是怎樣的呢（相對於Array查找元素）？ - RednaxelaFX 的回答

==============================================

先用C#來舉例回答題主的問題吧。

既然題主補充的具體例子是Java的 T[] vs java.util.ArrayList&，那麼對應C#里的 T[] vs System.Collections.Generic.List&就正好。

它們倆都屬於「動態數組」（dynamic array）的實現。看看它們與數組的關係就知道為啥這麼叫了。

在C#里，一個 List& 是通過一個 T[] 來實現其存儲的。可以參考其在CoreFX中的實現：

coreclr/List.cs at master · dotnet/coreclr · GitHub

public class List& : IList&, System.Collections.IList, IReadOnlyList& { private T[] _items; [ContractPublicPropertyName("Count")] private int _size;

// ... }

只說到這裡或許就已經足以解決題主對 T[] vs List& 的區別的疑惑之一：List& 的存儲方式與 T[] 是否一樣。答案是：當然一樣，畢竟 List& 就是用 T[] 來實現的，只不過中間多了一個 List& 對象作為間接層而已。

那麼很自然的下一個問題就是：為啥需要這個額外的 List& 間接層？

先繞道講個故事。上古時代，把面向對象概念發揚光大的 Smalltalk 語言，裡面有一個很強大的原語叫做「become:」——可以交換兩個對象的身份（identity）。例如說：

a become: b

會導致a引用的對象與b引用的對象互換身份。這種操作的威力之強大，如果我們用Java語法能做一樣的事情的話，會使得：

class Test { IFoo field;


  public void test() {

    IFoo foo = new Foo();

    IFoo bar = new Bar();

    this.field = foo;
    // 現在 foo and this.field 指向一個 Foo 實例,

    // 而 bar 指向一個 Bar 實例
    // 神奇的become!

    foo.become(bar);
    // 現在 foo and this.field 指向那個 Bar 實例,

    // 而 bar 指向那個 Foo 實例

    assert this.field.getClass() == Bar.class;

  }

}
interface IFoo {

}

class Foo implements IFoo { } class Bar implements IFoo { }

「become:」原語不是交換兩個引用那麼簡單，而是真正的交換了兩個對象的身份。

這種功能非常強大，可以用來實現許多有趣的功能。

例如說它可以用來實現延遲載入的Proxy：GUI里的一個Frame里如果包含一個圖片組件，它一開始可以是一個dummy，在後代並發載入好圖片後再創建出真正的渲染圖片的組件，然後把這倆相互become:一下，圖片就刷到GUI上了。

關於become:，可跳傳送門：The Miracle of become: - Gilad Bracha（打不開請自備工具…）

這become:跟C#的 List& 有啥關係呢？

試想一個場景，我們需要一個容器來存放不定個數的元素，但C#里的數組是固定大小的，創建的時候指定要多大就是多大，後面就無法擴容了。那不斷往裡面放元素髮現放滿了咋辦？

沒錯，創建個更大的數組，把原數組內容拷貝到新數組，然後讓這倆數組相互become:一下不就好了嘛！

string[] lines = new string[10]; int i = 0; while (true) { string line = Console.ReadLine(); if (line == "end") break;


    if (i == lines.Length) {  // 數組不夠大了，擴容到2倍！

      int newLength = lines.Length * 2;

      string[] newLines = new string[newLength];

      Array.Copy(lines, newLines, lines.Length); // 把原數組內容拷貝到新數組

      newLines.Become(lines); // 神奇的become!
      // 現在 lines 就指向新的擴容後的數組了

    }

// 現在數組肯定夠大了 assert(i &< lines.Length); lines[i] = line; i++; }

哈哈哈真方便！

呃。但是C#並沒有真的提供這種神奇的become:功能，因為實現它通常意味著顯著的額外開銷。

早期Smalltalk實現之所以能方便的實現become:原語，是因為它們大都採用了handle-based heap——語言里的引用並不是直接指向對象本體的，而是指向一個handle，然後handle再去指向真正的對象本體。每個對象在同一時間有且只有一個對應的handle，而多個語言層面的引用可以指向同一個handle——也就是代表指向同一個對象的意思。這裡的「handle」也被稱為「對象表」（object table）。

用前面的foo和bar的例子來說，在handle-based heap實現中，其實是這樣的：

variables handles objects [ this.field ] [ foo ] --－-&> [ handle 1 ] --－-&> [ a Foo instance ]

[ bar ] --－-&> [ handle 2 ] --－-&> [ a Bar instance ]

留意到引用類型的變數與真正的對象中間還多了一層handle間接層。

於是，要實現become:，只需要讓handle交換引用即可：

variables handles objects [ this.field ] [ foo ] --－-&> [ handle 1 ] /－&> [ a Foo instance ] x [ bar ] -－--&> [ handle 2 ] / －&> [ a Bar instance ]

很明顯，在handle-based heap的實現下，無論有多少變數指向一個對象，become:都只需要交換handle的指向，而不需要更新那些變數或者對象，非常方便。

但handle-based heap會使得所有對象訪問都要經過一層額外的間接層，會影響對象的訪問效率，所以現代的託管語言運行時（各種CLR、JVM、JavaScript引擎等的實現）都傾向與採用直接指針來實現引用，而不使用handle。這就是為什麼這些現代的實現上實現become:原語會有非常大的開銷：基本上要完成一次become:就得遍歷整個對象圖，跟做一次full GC的開銷相似。多可怕orz

（也有做法可以暫時讓舊對象的對象頭帶上forwarding pointer指向新對象，等到下次GC的時候再修正引用到新對象。但這也有其弊端，這裡就不展開聊了。）

講了那麼久的故事，回到正題。我們會發現，在C#里，要存不固定的個數的元素時，

可以用數組來存儲元素，但是數組是固定大小的，裝滿了無法對自身擴容，只有創建一個新的更大的數組才能解決問題；
C#沒有提供方便的become:原語來讓新數組替代舊數組的身份

那怎麼辦？很簡單，運行時沒有用handle來實現對象引用，我們就自己造一層handle就是了——這就是 List& 的本質。

我們的程序可以有多個變數引用著一個 List& 對象，而一個 List& 對象在內部會引用著一個 T[] 數組來實現實際存儲。

variables [ var1 ] [ var2 ] ---&> [ a List& ] ---&> [ a T[] ]

假如我們要裝的元素個數比當前的 T[] 的大小要大了，那就新造一個數組，把原數組的內容全部拷貝過去，並讓 List& 改為指向新數組：

variables [ var1 ] [ var2 ] ---&> [ a List& ] [ a T[] ] -&> [ a new T[] ]

就這麼簡單。

扯回到Smalltalk，事實上90年代中有個高效的Smalltalk實現——Strongtalk，在最初設計與實現的時候就覺得這become:原語很礙事。經過統計發現它在Smalltalk里用得最多的地方就是用於實現集合類型的擴容，所以Strongtalk在實現Smalltalk標準庫的時候就設計了跟上述 List& 類型類似的間接層對象，而在底層的VM層面則使用基於直接指針的對象模型而拋棄了handle。

=========================================

不過題主想用Java為例來提問，這就稍微更複雜一些。

Java直到Java 9為止，實現泛型的方式是「擦除法」（generics by erasure），不支持泛型參數的值為原始類型，而只能是引用類型。

所以Java的java.util.ArrayList&，只能實例化為 ArrayList& 而不能是 ArrayList& （java.lang.Integer 是 int 的包裝類型）。

參考OpenJDK8u里的ArrayList實現：

jdk8u/jdk8u/jdk: 0f6de62683a2 src/share/classes/java/util/ArrayList.java

public class ArrayList& extends AbstractList& implements List&, RandomAccess, Cloneable, java.io.Serializable { /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access


    /**

     * The size of the ArrayList (the number of elements it contains).

     *

     * @serial

     */

    private int size;

// ... }

所以在Java里，同樣裝著 { 1, 2, 3 } 三個元素的 int[] 與 ArrayList&，其存儲會有這樣的區別：

int[3] [ [0]: 1 ] [ [1]: 2 ] [ [2]: 3 ]

Integer ArrayList& Object[10] /-&> [ value: 1 ] [ elementData ] ---&> [ [0]: ref ] / Integer [ size: 3 ] [ [1]: ref ] ---&> [ value: 2 ] [ ... ] [ [2]: ref ] Integer [ [3]: null ] -&> [ value: 3 ] [ ... ] [ [9]: null ]

看到區別了么… Java里的 ArrayList& 背後存儲數據的數組不是 int[] 而是 Object[]，存的元素內容也不是 int 值而是指向 Integer 對象的引用。多糟糕。

但是別著急。Java早就直到這很不爽了，而在Java 10這個缺陷終於有機會被補上。Project Valhalla正在如火如荼進行中，等它完成的時候（希望是在Java 10發布前），我們就可以在Java里寫 ArrayList& 了，那樣就會跟C#的 List& 基本上一樣。

大家對Valhalla感興趣的話，現在就可以去項目官網下載代碼來自己build出來玩玩。

任何支持你用

var a = vars[i];

這種形式來進行快速索引的都不是真正的Abstract List。

它們大部分是實現了一些類List方法的Dynamic Array。

比較典型的，就是R大說的List&；這個就是玩意寫作List，讀作powerful array。

在C#中，真正的Abstract Data List是LinkedList(T) 類 (System.Collections.Generic). 這個是真·雙向鏈表。

Java我不懂，不過既然有也LinkedList和ArrayList之分，那麼相信也差不太多。

----------------------------

R大講解了

要區分Array和List，首先要知道什麼是List。

在下文，為了簡單地描述Array和List的區別，未加註明的List都是指最基本的單向抽象鏈表。

（C#的LinkedList是雙向鏈表，是單向列表的擴展，但其實現方式仍然是鏈表而不是數組）

wikipedia： List (abstract data type)

在上面的鏈接里，有一句非常關鍵的話：

In type theory and functional programming, abstract lists are usually defined inductively by two operations: nil that yields the empty list, and cons, which adds an item at the beginning of a list.

簡單來說，意思就是：鏈表由一個空鏈表和向頭部插入節點的操作來遞歸生成。

那麼List是什麼？是頭（Head）和後繼（Tail）組成的一個數據序列。對於一個抽象的List（單向）來說，你實際上能知道的信息就只有，

你拿到的節點（Head），
它的後繼（Tail）存在不存在，
如果存在，指向的是誰

你甚至沒法知道，你拿到的到底是全部的數據，還是只是某一個Item的後繼。

但是對Array，Head，Size，currentPositon都明明白白的告訴你了。你可以很容易地獲取數據列的整體信息。

所以，在Haskell 中，我們看到List經常被寫成這樣：

a:b:c

這段話翻譯成我們常用的命令式語言大概是這樣：

List.empty .prepend(c) .prepend(b) .prepend(a)

對於一個有序數據集合，一個很直觀的判斷它是Array還是List的方式，就是觀察它能否進行快速的進行prepend。

對於真正的List來說（比如Haskell的List），prepend是一個O(1)操作；只需要把新節點的後繼指向

List的Head，然後把新節點標記為Head即可。

（從這裡也可以看出，List並不要求一段連續的空間，但是他的每一項，除了數據本身的消耗外，還消耗一部分額外空間，用來存儲後繼的地址信息）。

但是對於Array來說，prepend是一個糟糕的操作（append在數組未滿的情況下並不慢，特別是針對單向列表來說）；因為Array申請的是固定內存空間，而且用偏移量來實現快速查詢——所以你既不能安全地移動Head，也不能隨意的把後面的地址據為己有。實際上做起來大概是這樣：

var newArray = new Array(currentArray.length*2); newArray[0] = itemToAppend; currentArray.copyTo(newArray,1); currentArray = newArray;

這個過程的複雜度是O(n)，因為你真的需要把一段內存里的數據拷到另一段內存。

當然，說到這裡，為什麼我說能快速索引的都是假List也就很清楚了。

對於一個真正的List來說，要想取得它的第n個元素，你必須得知道它的第n-1個，而想要知道第n-1個是啥……這是一個遞歸的過程，你可以看作通過prepend生成一個List的逆過程，它實耗費了O(n)時間；而Array是通過頭和偏移量來定義的，那麼想查找第n個元素，直接移動指針就好了。

---------------------

其實還有一個取巧的辦法可以判斷一個List的實現是基於Array還是基於LinkedList：

基於Array的一般都有用長度作參數的構造方法來方便你做優化。

ArrayList就是在底層維護一個Array,

所以這個問題的完整答案就在ArrayList.java里，至少java是的，

openjdk/ArrayList.java at jdk8u/jdk8u · dmlloyd/openjdk · GitHub

一樣的。只是因為目標數據結構定義的operation不一樣而已。因為arraylist內部存儲就是一個array。

- array在主存空間上是線性連續的；

- list是一種抽象，一般只要能夠進行append，insert，remove等操作，都可以叫做list；list可以由動態array（arraylist）或鏈表來實現（linkedlist）.

至於使用下標訪問[]操作，更像是一種「語法糖」，不是array專有語法，Csharp中可以通過索引器實現.