2.List接口

　　List 接口繼承了 Collection 接口以定義一個允許重復項的有序集合。該接口不但能夠對列表的一部分進行處理，還添加了面向位置的操作。

　　(1) 面向位置的操作包括插入某個元素或 Collection 的功能，還包括獲取、除去或更改元素的功能。在 List 中搜索元素可以從列表的頭部或尾部開始，如果找到元素，還將報告元素所在的位置 :

　　void add(int index, Object element): 在指定位置index上添加元素element

　　boolean addAll(int index, Collection c): 將集合c的所有元素添加到指定位置index

　　Object get(int index): 返回List中指定位置的元素

　　int indexOf(Object o): 返回第一個出現元素o的位置，否則返回-1

　　int lastIndexOf(Object o) ：返回最后一個出現元素o的位置，否則返回-1

　　Object remove(int index)　：刪除指定位置上的元素

　　Object set(int index, Object element) ：用元素element取代位置index上的元素，并且返回舊的元素

　　(2) List 接口不但以位置序列迭代的遍歷整個列表，還能處理集合的子集：

　　　ListIterator listIterator() : 返回一個列表迭代器，用來訪問列表中的元素

　　　ListIterator listIterator(int index) : 返回一個列表迭代器，用來從指定位置index開始訪問列表中的元素

　　List subList(int fromIndex, int toIndex) ：返回從指定位置fromIndex（包含）到toIndex（不包含）范圍中各個元素的列表視圖

　　“對子列表的更改（如 add()、remove() 和 set() 調用）對底層 List 也有影響。”

　　2.1.ListIterator接口

　　ListIterator 接口繼承 Iterator 接口以支持添加或更改底層集合中的元素，還支持雙向訪問。ListIterator沒有當前位置，光標位于調用previous和next方法返回的值之間。一個長度為n的列表，有n+1個有效索引值：




　　(1) void add(Object o): 將對象o添加到當前位置的前面

　　　void set(Object o): 用對象o替代next或previous方法訪問的上一個元素。如果上次調用后列表結構被修改了，那么將拋出IllegalStateException異常。

　　(2) boolean hasPrevious(): 判斷向后迭代時是否有元素可訪問

　　　Object previous()：返回上一個對象

　　　int nextIndex(): 返回下次調用next方法時將返回的元素的索引

　　　int previousIndex():　返回下次調用previous方法時將返回的元素的索引

　　“正常情況下，不用ListIterator改變某次遍歷集合元素的方向 — 向前或者向后。雖然在技術上可以實現，但previous() 后立刻調用next()，返回的是同一個元素。把調用 next()和previous()的順序顛倒一下，結果相同。”

　　“我們還需要稍微再解釋一下 add() 操作。添加一個元素會導致新元素立刻被添加到隱式光標的前面。因此，添加元素后調用 previous() 會返回新元素，而調用 next() 則不起作用，返回添加操作之前的下一個元素。”

　　2.2.AbstractList和AbstractSequentialList抽象類

　　有兩個抽象的 List 實現類：AbstractList 和 AbstractSequentialList。像 AbstractSet 類一樣，它們覆蓋了 equals() 和 hashCode() 方法以確保兩個相等的集合返回相同的哈希碼。若兩個列表大小相等且包含順序相同的相同元素，則這兩個列表相等。這里的 hashCode() 實現在 List 接口定義中指定，而在這里實現。

　　除了equals()和hashCode()，AbstractList和AbstractSequentialList實現了其余 List 方法的一部分。因為數據的隨機訪問和順序訪問是分別實現的，使得具體列表實現的創建更為容易。需要定義的一套方法取決于您希望支持的行為。您永遠不必親自提供的是 iterator方法的實現。

　　2.3. LinkedList類和ArrayList類

　　在“集合框架”中有兩種常規的 List 實現：ArrayList 和 LinkedList。使用兩種 List 實現的哪一種取決于您特定的需要。如果要支持隨機訪問，而不必在除尾部的任何位置插入或除去元素，那么，ArrayList 提供了可選的集合。但如果，您要頻繁的從列表的中間位置添加和除去元素，而只要順序的訪問列表元素，那么，LinkedList 實現更好。

　　“ArrayList 和 LinkedList 都實現 Cloneable 接口，都提供了兩個構造函數，一個無參的，一個接受另一個Collection”

　　2.3.1. LinkedList類

　　LinkedList類添加了一些處理列表兩端元素的方法。



　　(1) void addFirst(Object o): 將對象o添加到列表的開頭

　　　　void addLast(Object o)：將對象o添加到列表的結尾

　　(2) Object getFirst(): 返回列表開頭的元素

　　　　Object getLast(): 返回列表結尾的元素

　　(3) Object removeFirst(): 刪除并且返回列表開頭的元素

　　　　Object removeLast():刪除并且返回列表結尾的元素

　　(4) LinkedList(): 構建一個空的鏈接列表

　　　　LinkedList(Collection c): 構建一個鏈接列表，并且添加集合c的所有元素

　　“使用這些新方法，您就可以輕松的把 LinkedList 當作一個堆棧、隊列或其它面向端點的 數據結構 。”

　　2.3.2. ArrayList類

　　ArrayList類封裝了一個動態再分配的Object[]數組。每個ArrayList對象有一個capacity。這個capacity表示存儲列表中元素的數組的容量。當元素添加到ArrayList時，它的capacity在常量時間內自動增加。

　　在向一個ArrayList對象添加大量元素的程序中，可使用ensureCapacity方法增加capacity。這可以減少增加重分配的數量。

　　(1) void ensureCapacity(int minCapacity): 將ArrayList對象容量增加minCapacity

　　(2) void trimToSize(): 整理ArrayList對象容量為列表當前大小。程序可使用這個操作減少ArrayList對象存儲空間。

　　2.3.2.1. RandomAccess接口

　　一個特征接口。該接口沒有任何方法，不過你可以使用該接口來測試某個集合是否支持有效的隨機訪問。ArrayList和Vector類用于實現該接口。

3.Set接口

　　Set 接口繼承 Collection 接口，而且它不允許集合中存在重復項，每個具體的 Set 實現類依賴添加的對象的 equals()方法來檢查獨一性。Set接口沒有引入新方法，所以Set就是一個Collection，只不過其行為不同。

　　3.1. Hash表

　　Hash表是一種 數據結構 ，用來查找對象。Hash表為每個對象計算出一個整數，稱為Hash Code(哈希碼)。Hash表是個鏈接式列表的陣列。每個列表稱為一個buckets(哈希表元)。對象位置的計算　index = HashCode % buckets (HashCode為對象哈希碼，buckets為哈希表元總數)。

　　當你添加元素時，有時你會遇到已經填充了元素的哈希表元，這種情況稱為Hash Collisions(哈希沖突)。這時，你必須判斷該元素是否已經存在于該哈希表中。

　　如果哈希碼是合理地隨機分布的，并且哈希表元的數量足夠大，那么哈希沖突的數量就會減少。同時，你也可以通過設定一個初始的哈希表元數量來更好地控制哈希表的運行。初始哈希表元的數量為　buckets = size * 150% + 1 (size為預期元素的數量)。

　　如果哈希表中的元素放得太滿，就必須進行rehashing(再哈希)。再哈希使哈希表元數增倍，并將原有的對象重新導入新的哈希表元中，而原始的哈希表元被刪除。load factor(加載因子)決定何時要對哈希表進行再哈希。在Java編程語言中，加載因子默認值為0.75，默認哈希表元為101。

　　3.2. Comparable接口和Comparator接口

　　在“集合框架”中有兩種比較接口：Comparable接口和Comparator接口。像String和Integer等Java內建類實現Comparable接口以提供一定排序方式，但這樣只能實現該接口一次。對于那些沒有實現Comparable接口的類、或者自定義的類，您可以通過Comparator接口來定義您自己的比較方式。

　　3.2.1. Comparable接口

　　在java.lang包中，Comparable接口適用于一個類有自然順序的時候。假定對象集合是同一類型，該接口允許您把集合排序成自然順序。



　　(1) int compareTo(Object o): 比較當前實例對象與對象o，如果位于對象o之前，返回負值，如果兩個對象在排序中位置相同，則返回0，如果位于對象o后面，則返回正值

　　在 Java 2 SDK版本1.4中有二十四個類實現Comparable接口。下表展示了8種基本類型的自然排序。雖然一些類共享同一種自然排序，但只有相互可比的類才能排序。

　　利用Comparable接口創建您自己的類的排序順序，只是實現compareTo()方法的問題。通常就是依賴幾個數據成員的自然排序。同時類也應該覆蓋equals()和hashCode()以確保兩個相等的對象返回同一個哈希碼。

　　3.2.2. Comparator接口

　　若一個類不能用于實現java.lang.Comparable，或者您不喜歡缺省的Comparable行為并想提供自己的排序順序(可能多種排序方式)，你可以實現Comparator接口，從而定義一個比較器。




　　(1)int compare(Object o1, Object o2): 對兩個對象o1和o2進行比較，如果o1位于o2的前面，則返回負值，如果在排序順序中認為o1和o2是相同的，返回0，如果o1位于o2的后面，則返回正值

　　“與Comparable相似，0返回值不表示元素相等。一個0返回值只是表示兩個對象排在同一位置。由Comparator用戶決定如何處理。如果兩個不相等的元素比較的結果為零，您首先應該確信那就是您要的結果，然后記錄行為。”

　　(2)boolean equals(Object obj): 指示對象obj是否和比較器相等。

　　“該方法覆寫Object的equals()方法，檢查的是Comparator實現的等同性，不是處于比較狀態下的對象。”

?

全面接觸Java集合框架 三四