Java容器Collection├List 接口│├LinkedList 鏈表│├ArrayList 順序結構動態數組類│└Vector 向量│ └Stack 棧└Set Map├Hashtable├HashMap└WeakHashMap首先介紹Collection接口
Collection是最基本的集合接口一個Collection代表一組Object即Collection的元素（Elements）
Java SDK不提供直接繼承自Collection的類Java SDK提供的類都是繼承自Collection的子接口如List和Set
所有實現Collection接口的類都必須提供兩個標准的構造函數無參數的構造函數用於創建一個空的Collection有一個Collection參數的構造函數用於創建一個新的Collection這個新的Collection與傳入的Collection有相同的元素後一個構造函數允許用戶復制一個Collection
List是有序的Collection使用此接口能夠精確的控制每個元素插入的位置用戶能夠使用索引（元素在List中的位置類似於數組下標）來訪問List中的元素這類似於Java的數組
對應list的用法分為對數據進行操作（增刪改查）對數據存儲後遍歷顯示這兩大類應用
數據定位List接口提供了兩種搜索指定對象的方法從性能的觀點來看應該小心使用這些方法
為了提高效率通常我們對list中元素排好序進行折半查找通過獲取子列表縮小查找范圍子列表的獲取實現時注意列表中存在重復元素對獲取邊界值的影響
對於元素對象需要重寫equals（Object o）和hashCode（）方法 實現自定義的對象相等在比較元素相等時我們應先判斷元素的hashCode值是否相等對於判斷列表是否相等（元素的值和元素的順序）也可以使用列表的hashCode方法來提高判讀的效率
利用Collections也可以實現對list元素進行排序及其查找列表中的所有元素都必須實現Comparable接口 對於支持范型的jdk版本來說<T> T[] toArray（T[] a）
返回按適當順序（從第一個元素到最後一個元素）包含列表中所有元素的數組返回數組的運行時類型是指定數組的運行時類型
indexOf（Object o）
返回此列表中第一次出現的指定元素的索引如果此列表不包含該元素則返回
lastIndexOf（Object o）
返回此列表中最後出現的指定元素的索引如果列表不包含此元素則返回
get（int index）
返回列表中指定位置的元素
List<E> subList（int fromIndex int toIndex）
返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之間的部分視圖
inthashCode（）
返回列表的哈希碼值列表的哈希碼定義為以下計算的結果int hashCode = Iterator<E> i = erator（）while （ihasNext（）） { E obj = inext（）hashCode = *hashCode + （obj==null ？ objhashCode（））}
這確保了 listequals（list）意味著對於任何兩個列表 list 和 list 而言可實現 listhashCode（）==listhashCode（）正如 ObjecthashCode（） 的常規協定所要求的
增boolean add（E e）
向列表的尾部添加指定的元素（可選操作）
void add（int indexE element）
在列表的指定位置插入指定元素（可選操作）
刪刪除單個一組全部元素
E remove（int index）
移除列表中指定位置的元素（可選操作）
boolean remove（Object o）
從此列表中移除第一次出現的指定元素（如果存在）（可選操作）
boolean removeAll（Collection<？> c）
從列表中移除指定 collection中包含的其所有元素（可選操作）
boolean retainAll（Collection<？> c）
僅在列表中保留指定 collection中所包含的元素（可選操作）
void clear（）
從列表中移除所有元素（可選操作）
改E set（int indexE element）
用指定元素替換列表中指定位置的元素（可選操作）
遍歷iterator（）和ListIterator的差別？
Iterator<E> iterator（）
返回按適當順序在列表的元素上進行迭代的迭代器
ListIterator<E> listIterator（）
返回此列表元素的列表迭代器（按適當順序）
ListIterator<E> listIterator（int index）
返回列表中元素的列表迭代器（按適當順序）從列表的指定位置開始
Object[] toArray（）
返回按適當順序包含列表中的所有元素的數組（從第一個元素到最後一個元素）
<T> T[] toArray（T[] a）
返回按適當順序（從第一個元素到最後一個元素）包含列表中所有元素的數組返回數組的運行時類型是指定數組的運行時類型
針對list接口的實現類LinkedList ArrayListVectorStack各自都增加了那些方法實際使用時如何選擇？
首先來看List接口的鏈接列表實現LinkedList所有已實現的接口SerializableCloneable Iterable<E> Collection<E> Deque<E> List<E> Queue<E>實現所有可選的列表操作並且允許所有元素（包括null）除了實現 List接口外LinkedList 類還為在列表的開頭及結尾 getremove和 insert 元素提供了統一的命名方法這些操作允許將鏈接列表用作堆棧隊列或雙端隊列
此類實現 Deque接口為 addpoll提供先進先出隊列操作以及其他堆棧和雙端隊列操作
再來看List接口的數組列表實現 ArrayList所有已實現的接口SerializableCloneable Iterable<E> Collection<E> List<E> RandomAccess List接口的大小可變數組的實現實現了所有可選列表操作並允許包括 null在內的所有元素除了實現 List 接口外此類還提供一些方法來操作內部用來存儲列表的數組的大小（此類大致上等同於 Vector類除了此類是不同步的）
sizeisEmptygetsetiterator和 listIterator 操作都以固定時間運行add 操作以分攤的固定時間 運行也就是說添加 n個元素需要 O（n） 時間其他所有操作都以線性時間運行（大體上講）與用於 LinkedList實現的常數因子相比此實現的常數因子較低
每個 ArrayList實例都有一個容量該容量是指用來存儲列表元素的數組的大小它總是至少等於列表的大小隨著向 ArrayList中不斷添加元素其容量也自動增長並未指定增長策略的細節因為這不只是添加元素會帶來分攤固定時間開銷那樣簡單
在添加大量元素前應用程序可以使用 ensureCapacity操作來增加 ArrayList 實例的容量這可以減少遞增式再分配的數量
關於arrayList的容量和元素個數trimToSize（）
將此 ArrayList實例的容量調整為列表的當前大小
int size（）
返回此列表中的元素數
void ensureCapacity（int minCapacity）
如有必要增加此 ArrayList 實例的容量以確保它至少能夠容納最小容量參數所指定的元素數
總結 對於頻繁使用插入與刪除操作使用linkedlist是個不錯的選擇對於經常進行索引操作則arrylist較好從元素個數來判斷對於知道元素個數用來遍歷顯示時我們用arrayList更高效對於將列表用作堆棧隊列或雙端隊列操作時選擇linkedlist實際應用從數據庫返回結果集顯示在頁面時arrayList更合適
Linkedlistarrylist此實現不是同步的如果多個線程同時訪問一個ArrayList或鏈接列表實例而其中至少一個線程從結構上修改了列表那麼它必須保持外部同步（結構上的修改是指任何添加或刪除一個或多個元素的操作或者顯式調整底層數組的大小僅僅設置元素的值不是結構上的修改）這一般通過對自然封裝該列表的對象進行同步操作來完成如果不存在這樣的對象則應該使用CollectionssynchronizedList方法將該列表包裝起來這最好在創建時完成以防止意外對列表進行不同步的訪問List list = CollectionssynchronizedList（new ArrayList（……））List list = CollectionssynchronizedList（new LinkedList（……））vector的Vector中的所有方法前面都有一個synchronized關鍵字做修飾是線程安全的
Linkedlistarrylistvector類的iterator 和 listIterator方法返回的迭代器是快速失敗的在創建迭代器之後除非通過迭代器自身的 remove或 add 方法從結構上對列表進行修改否則在任何時間以任何方式對列表進行修改迭代器都會拋出ConcurrentModificationException因此面對並發的修改迭代器很快就會完全失敗而不是冒著在將來某個不確定時間發生任意不確定行為的風險注意迭代器的快速失敗行為無法得到保證因為一般來說不可能對是否出現不同步並發修改做出任何硬性保證快速失敗迭代器會盡最大努力拋出ConcurrentModificationException因此為提高這類迭代器的正確性而編寫一個依賴於此異常的程序是錯誤的做法迭代器的快速失敗行為應該僅用於檢測 bug因此實際應用是先通過iterator和 listIterator遍歷數組確定元素後再進行增刪時應用迭代器自身的方法來修改是否類似？個人覺得也不能在迭代器中修改如果修改重新生成迭代器
From:http://tw.wingwit.com/Article/program/Java/hx/201311/26291.html
