Java平臺(tái)提供了一個(gè)全新的集合框架。“集合框架”主要由一組用來操作對(duì)象的接口組成。不同接口描述一組不同數(shù)據(jù)類型。


Java 2集合框架圖

　　集合接口：6個(gè)接口（短虛線表示），表示不同集合類型，是集合框架的基礎(chǔ)。

　　抽象類：5個(gè)抽象類（長(zhǎng)虛線表示），對(duì)集合接口的部分實(shí)現(xiàn)。可擴(kuò)展為自定義集合類。

　　實(shí)現(xiàn)類：8個(gè)實(shí)現(xiàn)類（實(shí)線表示），對(duì)接口的具體實(shí)現(xiàn)。

　　在很大程度上，一旦您理解了接口，您就理解了框架。雖然您總要?jiǎng)?chuàng)建接口特定的實(shí)現(xiàn)，但訪問實(shí)際集合的方法應(yīng)該限制在接口方法的使用上；因此，允許您更改基本的數(shù)據(jù)結(jié)構(gòu)而不必改變其它代碼。

　　· Collection 接口是一組允許重復(fù)的對(duì)象。

　　· Set 接口繼承 Collection，但不允許重復(fù)，使用自己內(nèi)部的一個(gè)排列機(jī)制。

　　· List 接口繼承 Collection，允許重復(fù)，以元素安插的次序來放置元素，不會(huì)重新排列。

　　· Map接口是一組成對(duì)的鍵－值對(duì)象，即所持有的是key-value pairs。Map中不能有重復(fù)的key。擁有自己的內(nèi)部排列機(jī)制。

　　· 容器中的元素類型都為Object。從容器取得元素時(shí)，必須把它轉(zhuǎn)換成原來的類型。


　　Java 2簡(jiǎn)化集合框架圖


集合接口

　　1.Collection 接口

　　用于表示任何對(duì)象或元素組。想要盡可能以常規(guī)方式處理一組元素時(shí)，就使用這一接口。



　　(1) 單元素添加、刪除操作：

　　　boolean add(Object o):將對(duì)象添加給集合

　　　boolean remove(Object o): 如果集合中有與o相匹配的對(duì)象，則刪除對(duì)象o

　　(2) 查詢操作：

　　　int size() ：返回當(dāng)前集合中元素的數(shù)量

　　　boolean isEmpty() ：判斷集合中是否有任何元素

　　　boolean contains(Object o) ：查找集合中是否含有對(duì)象o

　　　Iterator iterator() ：返回一個(gè)迭代器，用來訪問集合中的各個(gè)元素

　　(3) 組操作 ：作用于元素組或整個(gè)集合

　　　boolean containsAll(Collection c): 查找集合中是否含有集合c 中所有元素

　　　boolean addAll(Collection c) : 將集合c 中所有元素添加給該集合

　　　void clear(): 刪除集合中所有元素

　　　void removeAll(Collection c) : 從集合中刪除集合c 中的所有元素

　　　void retainAll(Collection c) : 從集合中刪除集合c 中不包含的元素

　　(4) Collection轉(zhuǎn)換為Object數(shù)組 ：

　　　Object[] toArray() ：返回一個(gè)內(nèi)含集合所有元素的array

　　　Object[] toArray(Object[] a) ：返回一個(gè)內(nèi)含集合所有元素的array。運(yùn)行期返回的array和參數(shù)a的型別相同，需要轉(zhuǎn)換為正確型別。

　　此外，您還可以把集合轉(zhuǎn)換成其它任何其它的對(duì)象數(shù)組。但是，您不能直接把集合轉(zhuǎn)換成基本數(shù)據(jù)類型的數(shù)組，因?yàn)榧媳仨毘钟袑?duì)象。

　　“斜體接口方法是可選的。因?yàn)橐粋€(gè)接口實(shí)現(xiàn)必須實(shí)現(xiàn)所有接口方法，調(diào)用程序就需要一種途徑來知道一個(gè)可選的方法是不是不受支持。如果調(diào)用一種可選方法時(shí)，一個(gè) UnsupportedOperationException 被拋出，則操作失敗，因?yàn)榉椒ú皇苤С帧４水惓ｎ惱^承 RuntimeException 類，避免了將所有集合操作放入 try-catch 塊。”

　　Collection不提供get()方法。如果要遍歷Collectin中的元素，就必須用Iterator。

　　1.1.AbstractCollection 抽象類

　　AbstractCollection 類提供具體“集合框架”類的基本功能。雖然您可以自行實(shí)現(xiàn) Collection 接口的所有方法，但是，除了iterator()和size()方法在恰當(dāng)?shù)淖宇愔袑?shí)現(xiàn)以外，其它所有方法都由 AbstractCollection 類來提供實(shí)現(xiàn)。如果子類不覆蓋某些方法，可選的如add()之類的方法將拋出異常。

　　1.2.Iterator 接口

　　Collection 接口的iterator()方法返回一個(gè) Iterator。Iterator接口方法能以迭代方式逐個(gè)訪問集合中各個(gè)元素，并安全的從Collection 中除去適當(dāng)?shù)脑亍?



　　(1) boolean hasNext(): 判斷是否存在另一個(gè)可訪問的元素

　　　　Object next(): 返回要訪問的下一個(gè)元素。如果到達(dá)集合結(jié)尾，則拋出NoSuchElementException異常。

　　(2) void remove(): 刪除上次訪問返回的對(duì)象。本方法必須緊跟在一個(gè)元素的訪問后執(zhí)行。如果上次訪問后集合已被修改，方法將拋出IllegalStateException。

　　“Iterator中刪除操作對(duì)底層Collection也有影響。”

　　迭代器是 故障快速修復(fù)（fail-fast）的。這意味著，當(dāng)另一個(gè)線程修改底層集合的時(shí)候，如果您正在用 Iterator 遍歷集合，那么，Iterator就會(huì)拋出 ConcurrentModificationException （另一種 RuntimeException異常）異常并立刻失敗。

　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種基本類型的自然排序。雖然一些類共享同一種自然排序，但只有相互可比的類才能排序。



類 排序
BigDecimal,BigInteger,Byte, Double, Float,Integer,Long,Short 按數(shù)字大小排序
Character 按 Unicode 值的數(shù)字大小排序
String 按字符串中字符 Unicode 值排序

類	排序
BigDecimal,BigInteger,Byte, Double, Float,Integer,Long,Short	按數(shù)字大小排序
Character	按 Unicode 值的數(shù)字大小排序
String	按字符串中字符 Unicode 值排序

　　
　　利用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ì)象。”


3.3. SortedSet接口

　　“集合框架”提供了個(gè)特殊的Set接口：SortedSet，它保持元素的有序順序。SortedSet接口為集的視圖(子集)和它的兩端（即頭和尾）提供了訪問方法。當(dāng)您處理列表的子集時(shí)，更改視圖會(huì)反映到源集。此外，更改源集也會(huì)反映在子集上。發(fā)生這種情況的原因在于視圖由兩端的元素而不是下標(biāo)元素指定，所以如果您想要一個(gè)特殊的高端元素（toElement）在子集中，您必須找到下一個(gè)元素。

　　添加到SortedSet實(shí)現(xiàn)類的元素必須實(shí)現(xiàn)Comparable接口，否則您必須給它的構(gòu)造函數(shù)提供一個(gè)Comparator接口的實(shí)現(xiàn)。TreeSet類是它的唯一一份實(shí)現(xiàn)。

　　“因?yàn)榧仨毎ㄒ坏捻?xiàng)，如果添加元素時(shí)比較兩個(gè)元素導(dǎo)致了0返回值（通過Comparable的compareTo()方法或Comparator的compare()方法），那么新元素就沒有添加進(jìn)去。如果兩個(gè)元素相等，那還好。但如果它們不相等的話，您接下來就應(yīng)該修改比較方法，讓比較方法和 equals() 的效果一致。”



　　(1) Comparator comparator(): 返回對(duì)元素進(jìn)行排序時(shí)使用的比較器，如果使用Comparable接口的compareTo()方法對(duì)元素進(jìn)行比較，則返回null

　　(2) Object first(): 返回有序集合中第一個(gè)(最低)元素

　　(3) Object last(): 返回有序集合中最后一個(gè)(最高)元素

　　(4) SortedSet subSet(Object fromElement, Object toElement): 返回從fromElement(包括)至toElement(不包括)范圍內(nèi)元素的SortedSet視圖(子集)

　　(5) SortedSet headSet(Object toElement): 返回SortedSet的一個(gè)視圖，其內(nèi)各元素皆小于toElement

　　(6) SortedSet tailSet(Object fromElement): 返回SortedSet的一個(gè)視圖，其內(nèi)各元素皆大于或等于fromElement

　　3.4. AbstractSet抽象類

　　AbstractSet類覆蓋了Object類的equals()和hashCode()方法，以確保兩個(gè)相等的集返回相同的哈希碼。若兩個(gè)集大小相等且包含相同元素，則這兩個(gè)集相等。按定義，集的哈希碼是集中元素哈希碼的總和。因此，不論集的內(nèi)部順序如何，兩個(gè)相等的集會(huì)有相同的哈希碼。

　　3.4.1. Object類

　　(1) boolean equals(Object obj): 對(duì)兩個(gè)對(duì)象進(jìn)行比較，以便確定它們是否相同

　　(2) int hashCode(): 返回該對(duì)象的哈希碼。相同的對(duì)象必須返回相同的哈希碼

　　3.5. HashSet類類和TreeSet類

　　“集合框架”支持Set接口兩種普通的實(shí)現(xiàn)：HashSet和TreeSet(TreeSet實(shí)現(xiàn)SortedSet接口)。在更多情況下，您會(huì)使用 HashSet 存儲(chǔ)重復(fù)自由的集合。考慮到效率，添加到 HashSet 的對(duì)象需要采用恰當(dāng)分配哈希碼的方式來實(shí)現(xiàn)hashCode()方法。雖然大多數(shù)系統(tǒng)類覆蓋了 Object中缺省的hashCode()和equals()實(shí)現(xiàn)，但創(chuàng)建您自己的要添加到HashSet的類時(shí)，別忘了覆蓋 hashCode()和equals()。

　　當(dāng)您要從集合中以有序的方式插入和抽取元素時(shí)，TreeSet實(shí)現(xiàn)會(huì)有用處。為了能順利進(jìn)行，添加到TreeSet的元素必須是可排序的。

　　3.5.1.HashSet類

　　(1) HashSet(): 構(gòu)建一個(gè)空的哈希集

　　(2) HashSet(Collection c): 構(gòu)建一個(gè)哈希集，并且添加集合c中所有元素

　　(3) HashSet(int initialCapacity): 構(gòu)建一個(gè)擁有特定容量的空哈希集

　　(4) HashSet(int initialCapacity, float loadFactor): 構(gòu)建一個(gè)擁有特定容量和加載因子的空哈希集。LoadFactor是0.0至1.0之間的一個(gè)數(shù)

　　3.5.2. TreeSet類

　　(1) TreeSet():構(gòu)建一個(gè)空的樹集

　　(2) TreeSet(Collection c): 構(gòu)建一個(gè)樹集，并且添加集合c中所有元素

　　(3) TreeSet(Comparator c): 構(gòu)建一個(gè)樹集，并且使用特定的比較器對(duì)其元素進(jìn)行排序

　　“comparator比較器沒有任何數(shù)據(jù)，它只是比較方法的存放器。這種對(duì)象有時(shí)稱為函數(shù)對(duì)象。函數(shù)對(duì)象通常在“運(yùn)行過程中”被定義為匿名內(nèi)部類的一個(gè)實(shí)例。”

　　TreeSet(SortedSet s): 構(gòu)建一個(gè)樹集，添加有序集合s中所有元素，并且使用與有序集合s相同的比較器排序

　　3.6. LinkedHashSet類

　　LinkedHashSet擴(kuò)展HashSet。如果想跟蹤添加給HashSet的元素的順序，LinkedHashSet實(shí)現(xiàn)會(huì)有幫助。LinkedHashSet的迭代器按照元素的插入順序來訪問各個(gè)元素。它提供了一個(gè)可以快速訪問各個(gè)元素的有序集合。同時(shí)，它也增加了實(shí)現(xiàn)的代價(jià)，因?yàn)楣１碓械母鱾€(gè)元素是通過雙重鏈接式列表鏈接在一起的。

　　(1) LinkedHashSet(): 構(gòu)建一個(gè)空的鏈接式哈希集

　　(2) LinkedHashSet(Collection c): 構(gòu)建一個(gè)鏈接式哈希集，并且添加集合c中所有元素

　　(3) LinkedHashSet(int initialCapacity): 構(gòu)建一個(gè)擁有特定容量的空鏈接式哈希集

　　(4) LinkedHashSet(int initialCapacity, float loadFactor): 構(gòu)建一個(gè)擁有特定容量和加載因子的空鏈接式哈希集。LoadFactor是0.0至1.0之間的一個(gè)數(shù)

　　“為優(yōu)化HashSet空間的使用，您可以調(diào)優(yōu)初始容量和負(fù)載因子。TreeSet不包含調(diào)優(yōu)選項(xiàng)，因?yàn)闃淇偸瞧胶獾摹?#8221;

4. Map接口

　　Map接口不是Collection接口的繼承。Map接口用于維護(hù)鍵/值對(duì)(key/value pairs)。該接口描述了從不重復(fù)的鍵到值的映射。



　　(1) 添加、刪除操作：

　　Object put(Object key, Object value): 將互相關(guān)聯(lián)的一個(gè)關(guān)鍵字與一個(gè)值放入該映像。如果該關(guān)鍵字已經(jīng)存在，那么與此關(guān)鍵字相關(guān)的新值將取代舊值。方法返回關(guān)鍵字的舊值，如果關(guān)鍵字原先并不存在，則返回null

　　Object remove(Object key): 從映像中刪除與key相關(guān)的映射

　　void putAll(Map t): 將來自特定映像的所有元素添加給該映像

　　void clear(): 從映像中刪除所有映射

　　“鍵和值都可以為null。但是，您不能把Map作為一個(gè)鍵或值添加給自身。”

　　(2) 查詢操作：

　　Object get(Object key): 獲得與關(guān)鍵字key相關(guān)的值，并且返回與關(guān)鍵字key相關(guān)的對(duì)象，如果沒有在該映像中找到該關(guān)鍵字，則返回null

　　boolean containsKey(Object key): 判斷映像中是否存在關(guān)鍵字key

　　boolean containsValue(Object value): 判斷映像中是否存在值value

　　int size(): 返回當(dāng)前映像中映射的數(shù)量

　　boolean isEmpty() ：判斷映像中是否有任何映射

　　(3) 視圖操作 ：處理映像中鍵/值對(duì)組

　　Set keySet(): 返回映像中所有關(guān)鍵字的視圖集

　　“因?yàn)橛成渲墟I的集合必須是唯一的，您用Set支持。你還可以從視圖中刪除元素，同時(shí)，關(guān)鍵字和它相關(guān)的值將從源映像中被刪除，但是你不能添加任何元素。”

　　Collection values():返回映像中所有值的視圖集

　　“因?yàn)橛成渲兄档募喜皇俏ㄒ坏模肅ollection支持。你還可以從視圖中刪除元素，同時(shí)，值和它的關(guān)鍵字將從源映像中被刪除，但是你不能添加任何元素。”

　　Set entrySet(): 返回Map.Entry對(duì)象的視圖集，即映像中的關(guān)鍵字/值對(duì)

　　“因?yàn)橛成涫俏ㄒ坏模肧et支持。你還可以從視圖中刪除元素，同時(shí)，這些元素將從源映像中被刪除，但是你不能添加任何元素。”

　　4.1. Map.Entry接口

　　Map的entrySet()方法返回一個(gè)實(shí)現(xiàn)Map.Entry接口的對(duì)象集合。集合中每個(gè)對(duì)象都是底層Map中一個(gè)特定的鍵/值對(duì)。



　　通過這個(gè)集合的迭代器，您可以獲得每一個(gè)條目(唯一獲取方式)的鍵或值并對(duì)值進(jìn)行更改。當(dāng)條目通過迭代器返回后，除非是迭代器自身的remove()方法或者迭代器返回的條目的setValue()方法，其余對(duì)源Map外部的修改都會(huì)導(dǎo)致此條目集變得無效，同時(shí)產(chǎn)生條目行為未定義。

　　(1) Object getKey(): 返回條目的關(guān)鍵字

　　(2) Object getValue(): 返回條目的值

　　(3) Object setValue(Object value): 將相關(guān)映像中的值改為value，并且返回舊值

　　4.2. SortedMap接口

　　“集合框架”提供了個(gè)特殊的Map接口：SortedMap，它用來保持鍵的有序順序。



　　SortedMap接口為映像的視圖(子集)，包括兩個(gè)端點(diǎn)提供了訪問方法。除了排序是作用于映射的鍵以外，處理SortedMap和處理SortedSet一樣。

　　添加到SortedMap實(shí)現(xiàn)類的元素必須實(shí)現(xiàn)Comparable接口，否則您必須給它的構(gòu)造函數(shù)提供一個(gè)Comparator接口的實(shí)現(xiàn)。TreeMap類是它的唯一一份實(shí)現(xiàn)。

　　“因?yàn)閷?duì)于映射來說，每個(gè)鍵只能對(duì)應(yīng)一個(gè)值，如果在添加一個(gè)鍵/值對(duì)時(shí)比較兩個(gè)鍵產(chǎn)生了0返回值（通過Comparable的compareTo()方法或通過Comparator的compare()方法），那么，原始鍵對(duì)應(yīng)值被新的值替代。如果兩個(gè)元素相等，那還好。但如果不相等，那么您就應(yīng)該修改比較方法，讓比較方法和 equals() 的效果一致。”

　　(1) Comparator comparator(): 返回對(duì)關(guān)鍵字進(jìn)行排序時(shí)使用的比較器，如果使用Comparable接口的compareTo()方法對(duì)關(guān)鍵字進(jìn)行比較，則返回null

　　(2) Object firstKey(): 返回映像中第一個(gè)(最低)關(guān)鍵字

　　(3) Object lastKey(): 返回映像中最后一個(gè)(最高)關(guān)鍵字

　　(4) SortedMap subMap(Object fromKey, Object toKey): 返回從fromKey(包括)至toKey(不包括)范圍內(nèi)元素的SortedMap視圖(子集)

　　(5) SortedMap headMap(Object toKey): 返回SortedMap的一個(gè)視圖，其內(nèi)各元素的key皆小于toKey

　　(6) SortedSet tailMap(Object fromKey): 返回SortedMap的一個(gè)視圖，其內(nèi)各元素的key皆大于或等于fromKey

　　4.3. AbstractMap抽象類

　　和其它抽象集合實(shí)現(xiàn)相似，AbstractMap 類覆蓋了equals()和hashCode()方法以確保兩個(gè)相等映射返回相同的哈希碼。如果兩個(gè)映射大小相等、包含同樣的鍵且每個(gè)鍵在這兩個(gè)映射中對(duì)應(yīng)的值都相同，則這兩個(gè)映射相等。映射的哈希碼是映射元素哈希碼的總和，其中每個(gè)元素是Map.Entry接口的一個(gè)實(shí)現(xiàn)。因此，不論映射內(nèi)部順序如何，兩個(gè)相等映射會(huì)報(bào)告相同的哈希碼。

　　4.4. HashMap類和TreeMap類

　　“集合框架”提供兩種常規(guī)的Map實(shí)現(xiàn)：HashMap和TreeMap (TreeMap實(shí)現(xiàn)SortedMap接口)。在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會(huì)更好。使用HashMap要求添加的鍵類明確定義了hashCode()和equals()的實(shí)現(xiàn)。

　　這個(gè)TreeMap沒有調(diào)優(yōu)選項(xiàng)，因?yàn)樵摌淇偺幱谄胶鉅顟B(tài)。

　　4.4.1. HashMap類

　　為了優(yōu)化HashMap空間的使用，您可以調(diào)優(yōu)初始容量和負(fù)載因子。

　　(1) HashMap(): 構(gòu)建一個(gè)空的哈希映像

　　(2) HashMap(Map m): 構(gòu)建一個(gè)哈希映像，并且添加映像m的所有映射

　　(3) HashMap(int initialCapacity): 構(gòu)建一個(gè)擁有特定容量的空的哈希映像

　　(4) HashMap(int initialCapacity, float loadFactor): 構(gòu)建一個(gè)擁有特定容量和加載因子的空的哈希映像

　　4.4.2. TreeMap類

　　TreeMap沒有調(diào)優(yōu)選項(xiàng)，因?yàn)樵摌淇偺幱谄胶鉅顟B(tài)。

　　(1) TreeMap():構(gòu)建一個(gè)空的映像樹

　　(2) TreeMap(Map m): 構(gòu)建一個(gè)映像樹，并且添加映像m中所有元素

　　(3) TreeMap(Comparator c): 構(gòu)建一個(gè)映像樹，并且使用特定的比較器對(duì)關(guān)鍵字進(jìn)行排序

　　(4) TreeMap(SortedMap s): 構(gòu)建一個(gè)映像樹，添加映像樹s中所有映射，并且使用與有序映像s相同的比較器排序

　　4.5. LinkedHashMap類

　　LinkedHashMap擴(kuò)展HashMap，以插入順序?qū)㈥P(guān)鍵字/值對(duì)添加進(jìn)鏈接哈希映像中。象LinkedHashSet一樣，LinkedHashMap內(nèi)部也采用雙重鏈接式列表。

　　(1) LinkedHashMap(): 構(gòu)建一個(gè)空鏈接哈希映像

　　(2) LinkedHashMap(Map m): 構(gòu)建一個(gè)鏈接哈希映像,并且添加映像m中所有映射

　　(3) LinkedHashMap(int initialCapacity): 構(gòu)建一個(gè)擁有特定容量的空的鏈接哈希映像

　　(4) LinkedHashMap(int initialCapacity, float loadFactor): 構(gòu)建一個(gè)擁有特定容量和加載因子的空的鏈接哈希映像

　　(5) LinkedHashMap(int initialCapacity, float loadFactor,

　　boolean accessOrder): 構(gòu)建一個(gè)擁有特定容量、加載因子和訪問順序排序的空的鏈接哈希映像

　　“如果將accessOrder設(shè)置為true,那么鏈接哈希映像將使用訪問順序而不是插入順序來迭

　　代各個(gè)映像。每次調(diào)用get或者put方法時(shí)，相關(guān)的映射便從它的當(dāng)前位置上刪除，然后放到鏈接式映像列表的結(jié)尾處（只有鏈接式映像列表中的位置才會(huì)受到影響，哈希表元?jiǎng)t不受影響。哈希表映射總是待在對(duì)應(yīng)于關(guān)鍵字的哈希碼的哈希表元中）。”

　　“該特性對(duì)于實(shí)現(xiàn)高速緩存的“刪除最近最少使用”的原則很有用。例如，你可以希望將最常訪問的映射保存在內(nèi)存中，并且從數(shù)據(jù)庫中讀取不經(jīng)常訪問的對(duì)象。當(dāng)你在表中找不到某個(gè)映射，并且該表中的映射已經(jīng)放得非常滿時(shí)，你可以讓迭代器進(jìn)入該表，將它枚舉的開頭幾個(gè)映射刪除掉。這些是最近最少使用的映射。”

　　(6) protected boolean removeEldestEntry(Map.Entry eldest): 如果你想刪除最老的映射，則覆蓋該方法，以便返回true。當(dāng)某個(gè)映射已經(jīng)添加給映像之后，便調(diào)用該方法。它的默認(rèn)實(shí)現(xiàn)方法返回false，表示默認(rèn)條件下老的映射沒有被刪除。但是你可以重新定義本方法，以便有選擇地在最老的映射符合某個(gè)條件，或者映像超過了某個(gè)大小時(shí)，返回true。

　　4.6. WeakHashMap類

　　WeakHashMap是Map的一個(gè)特殊實(shí)現(xiàn)，它使用WeakReference(弱引用)來存放哈希表關(guān)鍵字。使用這種方式時(shí)，當(dāng)映射的鍵在 WeakHashMap 的外部不再被引用時(shí)，垃圾收集器會(huì)將它回收，但它將把到達(dá)該對(duì)象的弱引用納入一個(gè)隊(duì)列。WeakHashMap的運(yùn)行將定期檢查該隊(duì)列，以便找出新到達(dá)的弱應(yīng)用。當(dāng)一個(gè)弱引用到達(dá)該隊(duì)列時(shí)，就表示關(guān)鍵字不再被任何人使用，并且它已經(jīng)被收集起來。然后WeakHashMap便刪除相關(guān)的映射。

　　(1) WeakHashMap(): 構(gòu)建一個(gè)空弱哈希映像

　　(2) WeakHashMap(Map t): 構(gòu)建一個(gè)弱哈希映像,并且添加映像t中所有映射

　　(3) WeakHashMap(int initialCapacity): 構(gòu)建一個(gè)擁有特定容量的空的弱哈希映像

　　(4) WeakHashMap(int initialCapacity, float loadFactor): 構(gòu)建一個(gè)擁有特定容量和加載因子的空的弱哈希映像

　　4.6. IdentityHashMap類

　　IdentityHashMap也是Map的一個(gè)特殊實(shí)現(xiàn)。在這個(gè)類中，關(guān)鍵字的哈希碼不應(yīng)該由hashCode()方法來計(jì)算，而應(yīng)該由System.identityHashCode方法進(jìn)行計(jì)算(即使已經(jīng)重新定義了hashCode方法)。這是Object.hashCode根據(jù)對(duì)象的內(nèi)存地址來計(jì)算哈希碼時(shí)使用的方法。另外，為了對(duì)各個(gè)對(duì)象進(jìn)行比較，IdentityHashMap將使用==，而不使用equals方法。

　　換句話說，不同的關(guān)鍵字對(duì)象，即使它們的內(nèi)容相同，也被視為不同的對(duì)象。IdentityHashMap類可以用于實(shí)現(xiàn)對(duì)象拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)換(topology-preserving object graph transformations)(比如實(shí)現(xiàn)對(duì)象的串行化或深度拷貝)，在進(jìn)行轉(zhuǎn)換時(shí)，需要一個(gè)“節(jié)點(diǎn)表”跟蹤那些已經(jīng)處理過的對(duì)象的引用。即使碰巧有對(duì)象相等，“節(jié)點(diǎn)表”也不應(yīng)視其相等。另一個(gè)應(yīng)用是維護(hù)代理對(duì)象。比如，調(diào)試工具希望在程序調(diào)試期間維護(hù)每個(gè)對(duì)象的一個(gè)代理對(duì)象。

　　“IdentityHashMap類不是一般意義的Map實(shí)現(xiàn)！它的實(shí)現(xiàn)有意的違背了Map接口要求通過equals方法比較對(duì)象的約定。這個(gè)類僅使用在很少發(fā)生的需要強(qiáng)調(diào)等同性語義的情況。”

　　(1) IdentityHashMap (): 構(gòu)建一個(gè)空的全同哈希映像，默認(rèn)預(yù)期最大尺寸為21

　　“預(yù)期最大尺寸是映像期望把持的鍵/值映射的最大數(shù)目”

　　(2) IdentityHashMap (Map m): 構(gòu)建一個(gè)全同哈希映像,并且添加映像m中所有映射

　　(3) IdentityHashMap (int expectedMaxSize): 構(gòu)建一個(gè)擁有預(yù)期最大尺寸的空的全同哈希映像。放置超過預(yù)期最大尺寸的鍵/值映射時(shí)，將引起內(nèi)部數(shù)據(jù)結(jié)構(gòu)的增長(zhǎng)，有時(shí)可能很費(fèi)時(shí)