Collection及其子類ArrayList和LinkedList和Vector的底層實現和區別

點選上方「羅曉勝」，馬上關注，您的支援對我幫助很大

上期文章

/ 前言 /

在使用java的時候，我們都會遇到使用集合（collection）的時候，但是java api提供了多種集合的實現。

像我們常使用的list，arraylist，set，總的說來，java api中所用的集合類，都是實現了collection介面

/ 正文 /

數據結構

線性表，鏈表，雜湊表是常用的數據結構，在進行Java開發時，JDK已經爲我們提供了一系列相應的類來實現基本的數據結構。這些類均在java.util包中。

Java集合工具包位於Java.util包下，包含了很多常用的數據結構，如陣列、鏈表、棧、佇列、集合、雜湊表等。
組成：
- List列表
- Set集合
- Collection
- Map對映
- 迭代器（Iterator、Enumeration）
- 工具類（Arrays、Collections）

Java集合類的整體框架如下：

集合類主要分爲兩大類：
Collection：繼承了超級介面Iterable，是List、Set等集合高度抽象出來的介面，它包含了這些集合的基本操作
List: List介面通常表示一個列表（陣列、佇列、鏈表、棧等），其中的元素可以重複，常用實現類爲ArrayList和LinkedList，另外還有不常用的Vector。另外，LinkedList還是實現了Queue介面，因此也可以作爲佇列使用。
Set: Set介面通常表示一個集合，其中的元素不允許重複（通過hashcode和equals函數保證），常用實現類有HashSet和TreeSet，HashSet是通過Map中的HashMap實現的，而TreeSet是通過Map中的TreeMap實現的。另外，TreeSet還實現了SortedSet介面，因此是有序的集合（集閤中的元素要實現Comparable介面，並覆寫Compartor函數才行）。
說明：抽象類AbstractCollection、AbstractList和AbstractSet分別實現了Collection、List和Set介面，這就是在Java集合框架中用的很多的適配器設計模式，用這些抽象類去實現介面，在抽象類中實現介面中的若幹或全部方法，這樣下面下麪的一些類只需直接繼承該抽象類，並實現自己需要的方法即可，而不用實現介面中的全部抽象方法。

Map
- Map是一個對映介面，其中的每個元素都是一個key-value鍵值對，同樣抽象類AbstractMap通過適配器模式實現了Map介面中的大部分函數，TreeMap、HashMap、WeakHashMap等實現類都通過繼承AbstractMap來實現，另外，不常用的HashTable直接實現了Map介面，它和Vector都是JDK1.0就引入的集合類。

迭代器：Iterator是遍歷集合的迭代器（不能遍歷Map，只用來遍歷Collection），Collection的實現類都實現了iterator()函數，它返回一個Iterator物件，用來遍歷集合，ListIterator則專門用來遍歷List。而Enumeration則是JDK1.0時引入的，作用與Iterator相同，但它的功能比Iterator要少，它只能在Hashtable、Vector和Stack中使用。
工具類：Arrays和Collections是用來運算元組、集合的兩個工具類，例如在ArrayList和Vector中大量呼叫了Arrays.Copyof()方法，而Collections中有很多靜態方法可以返回各集合類的synchronized版本，即執行緒安全的版本，當然了，如果要用執行緒安全的結合類，首選Concurrent併發包下的對應的集合類。

Collection

是一個最基本的集合介面，也是一個泛型的介面
繼承了超級介面Iterable，子介面：List、Set、Queue等
每個Collection的物件包含了一組物件
所有的實現類都有兩個構造方法，一個是無參構造方法，第二個是用另外一個Collection物件作爲構造方法的參數
遍歷Collection使用Iterator迭代器實現
retainAll(collection),AddAll(),removeAll(c)分別對應了集合的交併差運算
沒有具體的直接實現，但提供了更具體的子介面，如Set、List等

Collection簡介

一個Collection代表一組Object，即Collection的元素（Elements），一些Collection允許相同的元素而另一些不行。一些能排序而另一些不行。
Java SDK不提供直接繼承自Collection的類，Java SDK提供的類都是繼承自Collection的「子介面」如List和Set。

如何遍歷Collection中的每一個元素？

不論Collection的實際型別如何，它都支援一個iterator()的方法，該方法返回一個迭代子，使用該迭代子即可逐一存取Collection中每一個元素，程式碼如下：

	Iterator it = collection.iterator(); // 獲得一個迭代子
    while(it.hasNext())　　
    {
        Object obj = it.next(); // 得到下一個元素
    }

其他方法
- retainAll(Collection<? extends E> c)**：保留，交運算
- addAll(Collection<? extends E> c)**：新增，並運算
- removeAll(Collection<? extends E> c)**：移除，減運算

List

是一個介面
繼承的介面：Collection
間接繼承的介面：Iterable
List是有序的Collection
- 可以對每個元素的插入位置進行精準控制
- 可以根據索引存取元素
和Set介面的最大區別是，List允許重複值，Set不能
它的直接實現類有ArrayList，LinkedList，Vector等
List有自己的迭代器ListIterator，可以通過這個迭代器進行逆序的迭代，以及用迭代器設定元素的值
如果元素包含自身，equals()和hashCode()不再是良定義的
實現類：ArrayList、LinkedList、Vector等

List方法

boolean add(E e): 新增到末尾
void add(int index, E e): 新增到指定位置

E set(int index, E e): 設定指定位置的元素,返回一個E
get(int index): 獲得指定位置的元素

Iterator iterator()
ListIterator listIterator()
ListIterator listIterator(int index)

int indexOf(E e)
int lastIndexOf(E e)

List subList(int fromIndex, int toIndex)

子類介紹

ArrayList
- 實現的介面：List、Collectin、Iterable、Serializable、Cloneable、RandomAccess
- 子類：AttributeList、RoleList、RoleUnresolvedList
- ArrayList是一個順序表，大小可變。當更多的元素加入到ArrayList中時，其大小將會動態的增長
- 內部的元素可以直接通過get與set方法進行存取，因爲ArrayList本質上就是一個數組
- 但速度較快，ArrayList相比LinkedList在查詢和修改元素上比較快，但是在新增和刪除上比LinkedList慢
- ArrayList和LinkedList一樣，不具備執行緒同步的安全性，Vector執行緒安全
- ArrayList、Vector底部都是採用陣列實現的
- 第一次定義的時候沒有指定陣列的長度則長度是0，在第一次新增的時候判斷如果是空則追加10。
- 擴容機制機製：ArrayList每次對size增長50%.
LinkedList
- 是一個雙鏈表
- 它還是佇列、雙端佇列，可以用作堆疊
- 和ArrayList一樣，不具有執行緒安全性
- 在新增和刪除元素時具有比ArrayList更好的效能.但在get與set方面弱於ArrayList.當然,這些對比都是指數據量很大或者操作很頻繁的情況下的對比,如果數據和運算量很小,那麼對比將失去意義。
- LinkedList還實現了Queue介面，所以它還是一個雙端佇列，該介面比List提供了更多的方法，包括offer(),peek(),poll等
Vector（執行緒安全）
- 執行緒安全
- 和ArrayList類似,但屬於強同步類。
- 如果你的程式本身是執行緒安全的(thread-safe,沒有在多個執行緒之間共用同一個集合/物件),那麼使用ArrayList是更好的選擇。
- Vector和ArrayList在更多元素新增進來時會請求更大的空間。Vector每次請求其大小的雙倍空間，而ArrayList每次對size增長50%.