2.List接口

　　List 接口繼承了 Collection 接口以定義一個(gè)允許重復(fù)項(xiàng)的有序集合。該接口不但能夠?qū)α斜淼囊徊糠诌M(jìn)行處理，還添加了面向位置的操作。

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

　　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): 返回第一個(gè)出現(xiàn)元素o的位置，否則返回-1

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

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

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

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

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

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

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

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

　　2.1.ListIterator接口

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




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

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

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

　　　Object previous()：返回上一個(gè)對(duì)象

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

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

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

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

　　2.2.AbstractList和AbstractSequentialList抽象類

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

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

　　2.3. LinkedList類和ArrayList類

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

　　“ArrayList 和 LinkedList 都實(shí)現(xiàn) Cloneable 接口，都提供了兩個(gè)構(gòu)造函數(shù)，一個(gè)無參的，一個(gè)接受另一個(gè)Collection”

　　2.3.1. LinkedList類

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



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

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

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

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

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

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

　　(4) LinkedList(): 構(gòu)建一個(gè)空的鏈接列表

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

　　“使用這些新方法，您就可以輕松的把 LinkedList 當(dāng)作一個(gè)堆棧、隊(duì)列或其它面向端點(diǎn)的 數(shù)據(jù)結(jié)構(gòu) 。”

　　2.3.2. ArrayList類

　　ArrayList類封裝了一個(gè)動(dòng)態(tài)再分配的Object[]數(shù)組。每個(gè)ArrayList對(duì)象有一個(gè)capacity。這個(gè)capacity表示存儲(chǔ)列表中元素的數(shù)組的容量。當(dāng)元素添加到ArrayList時(shí)，它的capacity在常量時(shí)間內(nèi)自動(dòng)增加。

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

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

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

　　2.3.2.1. RandomAccess接口

　　一個(gè)特征接口。該接口沒有任何方法，不過你可以使用該接口來測(cè)試某個(gè)集合是否支持有效的隨機(jī)訪問。ArrayList和Vector類用于實(shí)現(xiàn)該接口。

3.Set接口

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

　　3.1. Hash表

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

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

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

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

　　3.2. Comparable接口和Comparator接口

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

　　3.2.1. Comparable接口

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



　　(1) int compareTo(Object o): 比較當(dāng)前實(shí)例對(duì)象與對(duì)象o，如果位于對(duì)象o之前，返回負(fù)值，如果兩個(gè)對(duì)象在排序中位置相同，則返回0，如果位于對(duì)象o后面，則返回正值

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

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

　　3.2.2. Comparator接口

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




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

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

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

　　“該方法覆寫Object的equals()方法，檢查的是Comparator實(shí)現(xiàn)的等同性，不是處于比較狀態(tài)下的對(duì)象。”

?

全面接觸Java集合框架 三四