1、1 / 58Java 集合排序及集合排序及 java 集合類詳解集合類詳解(C Co ol ll le ec ct ti io on n, , L Li is st t, , S Se et t, , M Ma ap p)摘摘要要內內容容集合是 Java 里面最常用的，也是最重要的一部分。能夠用好集合和理解好集合對于做Java 程序的開發擁有無比的好處。本文詳細解釋了關于 Java 中的集合是如何實現的，以及他們的實現原理。目目 錄錄1 集合框架.21.1 集合框架概述.21.1.1 容器簡介.21.1.2 容器的分類.51.2 Collection.61.2.1 常用方法.61.2.2 迭代

2、器.91.3 List .111.3.1 概述.111.3.2 常用方法.121.3.3 實現原理.171.4 Map.201.4.1 概述.201.4.2 常用方法.211.4.3 Comparable 接口.271.4.4 實現原理.291.4.5 覆寫 hashCode().341.5 Set .391.5.1 概述.391.5.2 常用方法.391.5.3 實現原理.451.6 總結:集合框架中常用類比較 .462 練習.473 附錄：排序.481 集集合合框框架架1.1 集集合合框框架架概概述述1.1.1 容容器器簡簡介介到目前為止，我們已經學習了如何創建多個不同的對象，定義了這些對

3、象以后，我們就可以利用它們來做一些有意義的事情。舉例來說，假設要存儲許多雇員，不同的雇員的區別僅在于雇員的身份證號。我們可以通過身份證號來順序存儲每個雇員，但是在內存中實現呢？是不是要準備足夠的內存來存儲1000 個雇員，然后再將這些雇員逐一插入？如果已經插入了500 條記錄，這時需要插入一個身份證號較低的新雇員，該怎么辦呢？是在內存中將500 條記錄全部下移后，再從開頭插入新的記錄 ? 還是創建一個映射來記住每個對象的位置？當決定如何存儲對象的集合時，必須考慮如下問題。對于對象集合，必須執行的操作主要以下三種： 添加新的對象 刪除對象 查找對象我們必須確定如何將新的對象添加到集合中。可以將對

4、象添加到集合的末尾、開頭或者中間的某個邏輯位置。從集合中刪除一個對象后，對象集合中現有對象會有什么影響呢？可能必須將內存移來移去，或者就在現有對象所駐留的內存位置下一個“洞”。在內存中建立對象集合后，必須確定如何定位特定對象。可建立一種機制，利用該機制可根據某些搜索條件（例如身份證號）直接定位到目標對象；否則，便需要遍歷集合中的每個對象，直到找到要查找的對象為止。前面大家已經學習過了數組。數組的作用是可以存取一組數據。但是它卻存在一些缺點，使得無法使用它來比較方便快捷的完成上述應用場景的要求。1. 首先，在很多數情況下面，我們需要能夠存儲一組數據的容器，這一點雖然數組可以實現，但是如果我們需要

5、存儲的數據的個數多少并不確定。比如說：我們需要在容器里面存儲某個應用系統的當前的所有的在線用戶信息，而當前的在線用戶信息是時刻都可能在變化的。 也就是說，我們需要一種存儲數據的容器，它能夠自動的改變這個容器的所能存放的數據數量的大小。這一點上，如果使用數組來存儲的話，就顯得十分的笨拙。2. 我們再假設這樣一種場景：假定一個購物網站，經過一段時間的運行，我們已經存儲了一系列的購物清單了，購物清單中有商品信息。如果我們想要知道這段時間里面有多少種商品被銷售出去了。那么我們就需要一個容器能夠自動的過濾掉購物清單中的關于商品的重復信息。如果使用數組，這也是很難實現的。3. 最后再想想，我們經常會遇到這

6、種情況，我知道某個人的帳號名稱，希望能夠進一步了解這個人的其他的一些信息。也就是說，我們在一個地方存放一些用戶信息，我們希望能夠通過用戶的帳號來查找到對應的該用戶的其他的一些信息。再舉個查字典例子：假設我們希望使用一個容器來存放單詞以及對于這個單詞的解釋，而當我們想要查找某個單詞的意思的時候，能夠根據提供的單詞在這個容器中找到對應的單詞的解釋。如果使用數組來實現的話，就更加的困難了。為解決這些問題， Java 里面就設計了容器集合，不同的容器集合以不同的格式保存對象。數數學學背背景景在常見用法中，集合（ collection）和數學上直觀的集（ set）的概念是相同的。集是一個唯一項組，也就是

7、說組中沒有重復項。實際上，“集合框架 ”包含了一個 Set 接口和許多具體的 Set 類。但正式的集概念卻比 Java 技術提前了一個世紀，那時英國數學家 George Boole 按邏輯正式的定義了集的概念。大部分人在小學時通過我們熟悉的維恩圖引入的 “集的交 ”和“集的并 ”學到過一些集的理論。集的基本屬性如下： 集內只包含每項的一個實例 集可以是有限的，也可以是無限的 可以定義抽象概念 集不僅是邏輯學、數學和計算機科學的基礎，對于商業和系統的日常應用來說，它也很實用。 “連接池 ”這一概念就是數據庫服務器的一個開放連接集。 Web 服務器必須管理客戶機和連接集。文件描述符提供了操作系統中

8、另一個集的示例。映射是一種特別的集。它是一種對（pair）集，每個對表示一個元素到另一元素的單向映射。一些映射示例有： IP 地址到域名（ DNS）的映射 關鍵字到數據庫記錄的映射 字典（詞到含義的映射） 2 進制到 10 進制轉換的映射 就像集一樣，映射背后的思想比 Java 編程語言早的多，甚至比計算機科學還早。而Java 中的 Map 就是映射的一種表現形式。1.1.2 容容器器的的分分類類既然您已經具備了一些集的理論，您應該能夠更輕松的理解“集合框架”。 “集合框架 ”由一組用來操作對象的接口組成。不同接口描述不同類型的組。在很大程度上，一旦您理解了接口，您就理解了框架。雖然您總要創建

9、接口特定的實現，但訪問實際集合的方法應該限制在接口方法的使用上；因此，允許您更改基本的數據結構而不必改變其它代碼。框架接口層次結構如下圖所示。 Java 容器類類庫的用途是 “保存對象 ”，并將其劃分為兩個不同的概念：1） Collection 。 一組對立的元素，通常這些元素都服從某種規則。List 必須保持元素特定的順序，而Set 不能有重復元素。2） Map 。 一組 成對的 “鍵值對 ”對象。初看起來這似乎應該是一個 Collection ，其元素是成對的對象，但是這樣的設計實現起來太笨拙了，于是我們將Map 明確的提取出來形成一個獨立的概念。Map 一樣容易擴展成多維Map ，無需增

10、加新的概念，只要讓Map 中的鍵值對的每個 “值”也是一個 Map 即可。Collection 和 Map 的區別在于容器中每個位置保存的元素個數。Collection 每個位置只能保存一個元素（對象）。此類容器包括：List ，它以特定的順序保存一組元素；Set 則是元素不能重復。Map 保存的是 “鍵值對 ”，就像一個小型數據庫。我們可以通過“鍵”找到該鍵對應的 “值”。 Collection 對象之間沒有指定的順序，允許重復元素。 Set 對象之間沒有指定的順序，不允許重復元素 List 對象之間有指定的順序，允許重復元素,并引入位置下標。 Map 接口用于保存關鍵字（ Key）和數值（

11、 Value）的集合，集合中的每個對象加入時都提供數值和關鍵字。Map 接口既不繼承 Set 也不繼承 Collection。 List、Set、Map 共同的實現基礎是Object 數組除了四個歷史集合類外， Java 2 框架還引入了六個集合實現，如下表所示。接口接口實現實現歷史集合類歷史集合類Set HashSet TreeSet List ArrayList Vector LinkedList Stack Map HashMap Hashtable TreeMap Properties 歷史集合類部分解釋歷史集合類部分解釋Vector 是個像可增大數組的歷史集合類，但它可以存儲不同類型

12、的數據元素。 Java 2 SDK，版本 2 中 Vector 類被改良到 “集合框架 ”層次結構中以實現 List 接口。但是，如果您在使用新框架，您應該使用 ArrayList，而不是 List。從 Vector 轉換為 ArrayList 時，一個關鍵的差別是 為了更改元素值的位置，參數的順序被顛倒了。 Stack 類繼承 Vector，通過 push() 和 pop() 方法以實現一個標準的后進先出（ last-in-first-out（LIFO）堆棧。可是，我們要當心。因為 Stack 類繼承 Vector 類，您仍然可以用被繼承的 Vector 的方法訪問或修改 Stack。Enu

13、meration 接接口口Enumeration 接口允許您迭代集合中的所有元素。在“集合框架 ”中，該接口被 Iterator 接口替代。但是，并不是所有的庫都支持較新的接口，所以您可能會發現自己常常使用 Enumeration。盡管有些人更喜歡 Iterator 這個方法名稱，但用 Enumeration 迭代和用 Iterator 迭代類似。不過， Enumeration 不支持除去操作。Enumeration enum = .; while (enum.hasNextElement() Object element = iterator.nextElement(); / process

14、 element Hashtable 實現是個一般的字典，它允許存儲任何對象作為它的鍵或值（包括 null）。在 Java 2 SDK，版本 1.2 中，這個類被重新改寫到“集合框架 ”中去實現 Map 接口。所以，您可用原始的 Hashtable 方法或較新的 Map 方法。如果您需要一個同步的 Map，使用 Hashtable 比使用同步的 HashMap 稍快一些。任何集合 ( Collection )都能產生一個迭代器 ( Iterator )，而一個 List 除了能生成一個 ListIterator （列表迭代器）外 ,還能生成一個普通迭代器 ,因為 List 正是從集合繼承來的

15、.1.2 Collection1.2.1 常常用用方方法法Collection 接口用于表示任何對象或元素組。想要盡可能以常規方式處理一組元素時，就使用這一接口。Collection 在前面的大圖也可以看出，它是List 和 Set 的父類。并且它本身也是一個接口。它定義了作為集合所應該擁有的一些方法。如下：注意 :集合必須只有對象，集合中的元素不能是基本數據類型。Collection 接口支持如添加和除去等基本操作。設法除去一個元素時，如果這個元素存在，除去的僅僅是集合中此元素的一個實例。 boolean add(Object element) boolean remove(Object e

16、lement) Collection 接口還支持查詢操作： int size() boolean isEmpty() boolean contains(Object element) Iterator iterator() 組操作 ：Collection 接口支持的其它操作，要么是作用于元素組的任務，要么是同時作用于整個集合的任務。 boolean containsAll(Collection collection) boolean addAll(Collection collection) void clear() void removeAll(Collection collection)

17、void retainAll(Collection collection) containsAll() 方法允許您查找當前集合是否包含了另一個集合的所有元素，即另一個集合是否是當前集合的子集。其余方法是可選的，因為特定的集合可能不支持集合更改。 addAll() 方法確保另一個集合中的所有元素都被添加到當前的集合中，通常稱為并。 clear() 方法從當前集合中除去所有元素。 removeAll() 方法類似于 clear() ，但只除去了元素的一個子集。 retainAll() 方法類似于 removeAll() 方法，不過可能感到它所做的與前面正好相反：它從當前集合中除去不屬于另一個集合的

18、元素，即交。 我們看一個簡單的例子，來了解一下集合類的基本方法的使用：import java.util.*;public class CollectionToArray public static void main(String args) Collection collection1=new ArrayList();/創建一個集合對象collection1.add(000);/添加對象到 Collection 集合中collection1.add(111);collection1.add(222);System.out.println(集合 collection1 的大小：+collect

19、ion1.size();System.out.println(集合 collection1 的內容：+collection1);collection1.remove(000);/從集合 collection1 中移除掉 000 這個對象System.out.println(集合 collection1 移除 000 后的內容：+collection1);System.out.println(集合 collection1 中是否包含 000 ：+collection1.contains(000);System.out.println(集合 collection1 中是否包含 111 ：+coll

20、ection1.contains(111);Collection collection2=new ArrayList();collection2.addAll(collection1);/將 collection1 集合中的元素全部都加到 collection2中System.out.println(集合 collection2 的內容：+collection2);collection2.clear();/清空集合 collection1 中的元素System.out.println(集合 collection2 是否為空 ：+collection2.isEmpty();/將集合 collec

21、tion1 轉化為數組Object s= collection1.toArray();for(int i=0;is.length;i+)System.out.println(si);運行結果為：集合 collection1 的大小：3集合 collection1 的內容：000, 111, 222集合 collection1 移除 000 后的內容：111, 222集合 collection1 中是否包含 000 ：false集合 collection1 中是否包含 111 ：true集合 collection2 的內容：111, 222集合 collection2 是否為空 ：true111

22、222這里需要注意的是， Collection 它僅僅只是一個接口，而我們真正使用的時候，確是創建該接口的一個實現類。做為集合的接口，它定義了所有屬于集合的類所都應該具有的一些方法。而 ArrayList （列表）類是集合類的一種實現方式。 這里需要一提的是，因為Collection 的實現基礎是數組，所以有轉換為 Object 數組的方法： Object toArray() Object toArray(Object a)其中第二個方法 Object toArray(Object a) 的參數 a 應該是集合中所有存放的對象的類的父類。1.2.2 迭迭代代器器任何容器類，都必須有某種方式可以

23、將東西放進去，然后由某種方式將東西取出來。畢竟，存放事物是容器最基本的工作。對于ArrayList，add（）是插入對象的方法，而get()是取出元素的方式之一。 ArrayList 很靈活，可以隨時選取任意的元素，或使用不同的下標一次選取多個元素。如果從更高層的角度思考，會發現這里有一個缺點：要使用容器，必須知道其中元素的確切類型。初看起來這沒有什么不好的，但是考慮如下情況：如果原本是ArrayList ，但是后來考慮到容器的特點，你想換用Set ，應該怎么做？或者你打算寫通用的代碼，它們只是使用容器，不知道或者說不關心容器的類型，那么如何才能不重寫代碼就可以應用于不同類型的容器？所以迭代器

24、 (Iterator)的概念，也是出于一種設計模式就是為達成此目的而形成的。所以Collection 不提供 get()方法。如果要遍歷Collectin 中的元素，就必須用Iterator。迭代器（ Iterator）本身就是一個對象，它的工作就是遍歷并選擇集合序列中的對象，而客戶端的程序員不必知道或關心該序列底層的結構。此外，迭代器通常被稱為“輕量級 ”對象，創建它的代價小。但是，它也有一些限制，例如，某些迭代器只能單向移動。Collection 接口的 iterator() 方法返回一個 Iterator。Iterator 和您可能已經熟悉的 Enumeration 接口類似。使用 It

25、erator 接口方法，您可以從頭至尾遍歷集合，并安全的從底層 Collection 中除去元素。下面，我們看一個對于迭代器的簡單使用：import java.util.ArrayList;import java.util.Collection;import java.util.Iterator; public class IteratorDemo public static void main(String args) Collection collection = new ArrayList();collection.add(s1);collection.add(s2);collectio

26、n.add(s3);Iterator iterator = collection.iterator();/得到一個迭代器while (iterator.hasNext() /遍歷Object element = iterator.next();System.out.println(iterator = + element);if(collection.isEmpty()System.out.println(collection is Empty!);elseSystem.out.println(collection is not Empty! size=+collection.size();I

27、terator iterator2 = collection.iterator();while (iterator2.hasNext() /移除元素Object element = iterator2.next();System.out.println(remove: +element);iterator2.remove();Iterator iterator3 = collection.iterator();if (!iterator3.hasNext() /察看是否還有元素System.out.println(還有元素 );if(collection.isEmpty()System.out

28、.println(collection is Empty!);/使用 collection.isEmpty()方法來判斷程序的運行結果為：iterator = s1iterator = s2iterator = s3collection is not Empty! size=3remove: s1remove: s2remove: s3還有元素collection is Empty!可以看到， Java 的 Collection 的 Iterator 能夠用來，：1) 使用方法 iterator() 要求容器返回一個Iterator .第一次調用 Iterator 的 next() 方法時，它

29、返回集合序列的第一個元素。2) 使用 next() 獲得集合序列的中的下一個元素。3) 使用 hasNext()檢查序列中是否元素。4) 使用 remove()將迭代器新返回的元素刪除。需要注意的是：方法刪除由next 方法返回的最后一個元素，在每次調用 next 時，remove 方法只能被調用一次 。Comment i1: 它有兩個子接口：1、List 2、Set大家看， Java 實現的這個迭代器的使用就是如此的簡單。Iterator（跌代器） 雖然功能簡單，但仍然可以幫助我們解決許多問題，同時針對 List 還有一個更復雜更高級的ListIterator。您可以在下面的List講解中得

30、到進一步的介紹。1.3 List1.3.1 概概述述前面我們講述的Collection 接口實際上并沒有直接的實現類。而 List 是容器的一種，表示列表的意思。當我們不知道存儲的數據有多少的情況，我們就可以使用 List 來完成存儲數據的工作。例如前面提到的一種場景。我們想要在保存一個應用系統當前的在線用戶的信息。我們就可以使用一個List 來存儲。因為 List 的最大的特點就是能夠自動的根據插入的數據量來動態改變容器的大小。下面我們先看看List 接口的一些常用方法。1.3.2 常常用用方方法法List 就是列表的意思，它是Collection 的一種，即繼承了 Collection 接

31、口，以定義一個允許重復項的有序集合。該接口不但能夠對列表的一部分進行處理，還添加了面向位置的操作。List 是按對象的進入順序進行保存對象，而不做排序或編輯操作。 它除了擁有 Collection 接口的所有的方法外還擁有一些其他的方法。面向位置的操作包括插入某個元素或 Collection 的功能，還包括獲取、除去或更改元素的功能。在 List 中搜索元素可以從列表的頭部或尾部開始，如果找到元素，還將報告元素所在的位置。 void add(int index, Object element) ：添加對象 element 到位置 index 上 boolean addAll(int index

32、, Collection collection) ：在 index 位置后添加容器 collection 中所有的元素 Object get(int index) ：取出下標為 index 的位置的元素 int indexOf(Object element) ：查找對象 element 在 List 中第一次出現的位置 int lastIndexOf(Object element) ：查找對象 element 在 List 中最后出現的位置 Object remove(int index) ：刪除 index 位置上的元素 Object set(int index, Object elemen

33、t) ：將 index 位置上的對象替換為element 并返回老的元素。先看一下下面表格： 簡述簡述 實現實現 操作特性操作特性 成員要求成員要求 ArrayList 提供快速的基于索引的成員訪提供快速的基于索引的成員訪問，對尾部成員的增加和刪除問，對尾部成員的增加和刪除支持較好支持較好 成員可為任意成員可為任意Object 子類的對象子類的對象 List 提供基于索引提供基于索引的對成員的隨的對成員的隨機訪問機訪問 LinkedList 對列表中任何位置的成員的增對列表中任何位置的成員的增加和刪除支持較好，但對基于加和刪除支持較好，但對基于索引的成員訪問支持性能較差索引的成員訪問支持性能較

34、差 成員可為任意成員可為任意Object 子類的對象子類的對象 在“集合框架 ”中有兩種常規的 List 實現：ArrayList 和 LinkedList。使用兩種 List 實現的哪一種取決于您特定的需要。如果要支持隨機訪問，而不必在除尾部的任何位置插入或除去元素，那么，ArrayList 提供了可選的集合。但如果，您要頻繁的從列表的中間位置添加和除去元素，而只要順序的訪問列表元素，那么，LinkedList 實現更好。我們以 ArrayList 為例，先看一個簡單的例子：例子中，我們把 12 個月份存放到 ArrayList 中，然后用一個循環，并使用 get（）方法將列表中的對象都取出

35、來。而 LinkedList 添加了一些處理列表兩端元素的方法（下圖只顯示了新方法）：使用這些新方法，您就可以輕松的把 LinkedList 當作一個堆棧、隊列或其它面向端點的數據結構。我們再來看另外一個使用LinkedList 來實現一個簡單的隊列的例子：import java.util.*; public class ListExample public static void main(String args) LinkedList queue = new LinkedList(); queue.addFirst(Bernadine); queue.addFirst(Elizabeth)

36、; queue.addFirst(Gene); queue.addFirst(Elizabeth); queue.addFirst(Clara); System.out.println(queue); queue.removeLast(); queue.removeLast(); System.out.println(queue); 運行程序產生了以下輸出。請注意，與 Set 不同的是 List 允許重復。Clara, Elizabeth, Gene, Elizabeth, BernadineClara, Elizabeth, Gene該的程序演示了具體 List 類的使用。第一部分，創建一個

37、由 ArrayList 支持的 List。填充完列表以后，特定條目就得到了。示例的 LinkedList 部分把 LinkedList 當作一個隊列，從隊列頭部添加東西，從尾部除去。List 接口不但以位置友好的方式遍歷整個列表，還能處理集合的子集： ListIterator listIterator() ：返回一個 ListIterator 跌代器，默認開始位置為 ListIterator listIterator(int startIndex) ：返回一個 ListIterator 跌代器，開始位置為startIndex List subList(int fromIndex, int to

38、Index) ：返回一個子列表List ,元素存放為從 fromIndex 到 toIndex 之前的一個元素。處理 subList() 時，位于 fromIndex 的元素在子列表中，而位于 toIndex 的元素則不是，提醒這一點很重要。以下 for-loop 測試案例大致反映了這一點：for (int i=fromIndex; itoIndex; i+) / process element at position i此外，我們還應該提醒的是：對子列表的更改（如 add()、remove() 和 set() 調用）對底層 List 也有影響。ListIterator 接接口口 ListIt

39、erator 接口繼承 Iterator 接口以支持添加或更改底層集合中的元素，還支持雙向訪問 。以下源代碼演示了列表中的反向循環。請注意 ListIterator 最初位于列表尾之后（ list.size()），因為第一個元素的下標是0。List list = .;ListIterator iterator = list.listIterator(list.size();while (iterator.hasPrevious() Object element = iterator.previous(); / Process element正常情況下，不用 ListIterator 改變某次遍

40、歷集合元素的方向 向前或者向后。雖然在技術上可能實現時，但在 previous() 后立刻調用 next()，返回的是同一個元素。把調用 next() 和 previous() 的順序顛倒一下，結果相同。 我們看一個 List 的例子：import java.util.*; public class ListIteratorTest public static void main(String args) List list = new ArrayList();list.add(aaa);list.add(bbb);list.add(ccc);list.add(ddd);System.out.

41、println(下標 0 開始： +list.listIterator(0).next();/next()System.out.println(下標 1 開始 :+list.listIterator(1).next();System.out.println(子 List 1-3:+list.subList(1,3);/子列表ListIterator it = list.listIterator();/默認從下標 0 開始/隱式光標屬性add 操作 ,插入到當前的下標的前面it.add(sss);while(it.hasNext()System.out.println(next Index=+i

42、t.nextIndex()+,Object=+it.next();/set 屬性ListIterator it1 = list.listIterator();it1.next();it1.set(ooo);ListIterator it2 = list.listIterator(list.size();/下標while(it2.hasPrevious()System.out.println(previous Index=+it2.previousIndex()+,Object=+it2.previous();程序的執行結果為：下標 0 開始： aaa下標 1 開始 :bbb子 List 1-3

43、:bbb, cccnext Index=1,Object=aaanext Index=2,Object=bbbnext Index=3,Object=cccnext Index=4,Object=dddprevious Index=4,Object=dddprevious Index=3,Object=cccprevious Index=2,Object=bbbprevious Index=1,Object=aaaprevious Index=0,Object=ooo我們還需要稍微再解釋一下 add() 操作。添加一個元素會導致新元素立刻被添加到隱式光標的前面。因此，添加元素后調用 previ

44、ous() 會返回新元素，而調用 next() 則不起作用，返回添加操作之前的下一個元素。下標的顯示方式，如下圖所示：對于 List 的基本用法我們學會了，下面我們來進一步了解一下List 的實現原理，以便價升我們對于集合的理解。1.3.3 實實現現原原理理前面已經提了一下Collection 的實現基礎都是基于數組的。下面我們就已 ArrayList 為例， 簡單分析一下 ArrayList 列表的實現方式。首先，先看下它的構造函數。下列表格是在 SUN 提供的 API 中的描述： ArrayList() Constructs an empty list with an initial ca

45、pacity of ten.ArrayList(Collection c) Constructs a list containing the elements of the specified collection, in the order they are returned by the collections iterator.ArrayList(int initialCapacity) Constructs an empty list with the specified initial capacity.其中第一個構造函數ArrayList()和第二構造函數ArrayList(Col

46、lection c) 是按照Collection 接口文檔所述，所應該提供兩個構造函數，一個無參數，一個接受另一個 Collection。第 3 個構造函數：ArrayList(int initialCapacity) 是 ArrayList 實現的比較重要的構造函數，雖然，我們不常用它，但是某認的構造函數正是調用的該帶參數：initialCapacity 的構造函數來實現的。 其中參數： initialCapacity 表示我們構造的這個ArrayList 列表的初始化容量是多大。如果調用默認的構造函數，則表示默認調用該參數為initialCapacity =10 的方式，來進行構建一個 A

47、rrayList 列表對象。為了更好的理解這個initialCapacity 參數的概念，我們先看看ArrayList 在 Sun 提供的源碼中的實現方式。先看一下它的屬性有哪些：ArrayList 繼承了 AbstractList 我們主要看看 ArrayList 中的屬性就可以了。ArrayList 中主要包含 2 個屬性： private transient Object elementData; private int size;其中數組 :：elementData 是列表的實現核心屬性：數組。 我們使用該數組來進行存放集合中的數據。而我們的初始化參數就是該數組構建時候的長度，即該數組

48、的 length 屬性就是 initialCapacity 參數。Keys：transient 表示被修飾的屬性不是對象持久狀態的一部分，不會自動的序列化 。第 2 個屬性：size 表示列表中真實數據的存放個數。我們再來看一下ArrayList 的構造函數 ,加深一下 ArrayList 是基于數組的理解。從源碼中可以看到默認的構造函數調用的就是帶參數的構造函數： public ArrayList(int initialCapacity)不過參數 initialCapacity10。我們主要看 ArrayList(int initialCapacity)這個構造函數。可以看到：t th hi

49、 is s. .e el le em me en nt tD Da at ta a = = n ne ew w O Ob bj je ec ct t i in ni it ti ia al lC Ca ap pa ac ci it ty y ; ;我們就是使用的initialCapacity這個參數來創建一個Object 數組。而我們所有的往該集合對象中存放的數據，就是存放到了這個Object 數組中去了。我們在看看另外一個構造函數的源碼：這里，我們先看size() 方法的實現形式。它的作用即是返回size 屬性值的大小。然后我們再看另外一個構造函數public ArrayList(Colle

50、ction c)，該構造函數的作用是把另外一個容器對象中的元素存放到當前的List 對象中。可以看到，首先，我們是通過調用另外一個容器對象C 的方法 size()來設置當前的 List 對象的 size 屬性的長度大小。接下來，就是對elementData數組進行初始化，初始化的大小為原先容器大小的 1.1 倍。最后，就是通過使用容器接口中的Object toArray(Object a)方法來把當前容器中的對象都存放到新的數組elementData中。這樣就完成了一個ArrayList 的建立。可能大家會存在一個問題，那就是，我們建立的這個ArrayList是使用數組來實現的，但是數組的長度

51、一旦被定下來，就不能改變了。而我們在給ArrayList 對象中添加元素的時候，卻沒有長度限制。這個時候，ArrayList中的 elementData屬性就必須存在一個需要動態的擴充容量的機制。我們看下面的代碼，它描述了這個擴充機制： 這個方法的作用就是用來判斷當前的數組是否需要擴容，應該擴容多少。其中屬性： modCount 是繼承自父類，它表示當前的對象對elementData 數組進行了多少次擴容，清空，移除等操作。該屬性相當于是一個對于當前List 對象的一個操作記錄日志號。 我們主要看下面的代碼實現：1. 首先得到當前 elementData屬性的長度 oldCapacity。2.

52、 然后通過判斷 oldCapacity 和 minCapacity 參數誰大來決定是否需要擴容 如果 minCapacity 大于 oldCapacity，那么我們就對當前的 List 對象進行擴容。擴容的的策略為：取(oldCapacity * 3)/2 + 1 和 minCapacity 之間更大的那個。然后使用數組拷貝的方法，把以前存放的數據轉移到新的數組對象中 如果 minCapacity 不大于 oldCapacity 那么就不進行擴容。下面我們看看上的那個ensureCapacity 方法的是如何使用的 :上的兩個方法都是往List 中添加元素。每次在添加元素的時候，我們就需要判斷

53、一下，是否需要對于當前的數組進行擴容。我們主要看看 public boolean add(Object o)方法，可以發現在添加一個元素到容器中的時候，首先我們會判斷是否需要擴容。因為只增加一個元素，所以擴容的大小判斷也就為當前的size+1 來進行判斷。然后，就把新添加的元素放到數組 elementData 中。第二個方法 public boolean addAll(Collection c)也是同樣的原理。將新的元素放到elementData 數組之后。同時改變當前List 對象的 size 屬性。類似的 List 中的其他的方法也都是基于數組進行操作的。大家有興趣可以看看源碼中的更多的實

54、現方式。最后我們再看看如何判斷在集合中是否已經存在某一個對象的：由源碼中我們可以看到，public boolean contains(Object elem)方法是通過調用public int indexOf(Object elem)方法來判斷是否在集合中存在某個對象elem。我們看看 indexOf 方法的具體實現。 首先我們判斷一下elem對象是否為 null，如果為 null 的話，那么遍歷數組elementData把第一個出現 null 的位置返回。 如果 elem 不為 null 的話，我們也是遍歷數組elementData，并通過調用 elem 對象的 equals()方法來得到第

55、一個相等的元素的位置。這里我們可以發現， ArrayList 中用來判斷是否包含一個對象，調用的是各個對象自己實現的equals()方法。在前面的高級特性里面，我們可以知道：如果要判斷一個類的一個實例對象是否等于另外一個對象，那么我們就需要自己覆寫Object 類的 public boolean equals(Object obj) 方法。如果不覆寫該方法的話，那么就會調用Object 的 equals()方法來進行判斷。這就相當于比較兩個對象的內存應用地址是否相等了。在集合框架中，不僅僅是List，所有的集合類，如果需要判斷里面是否存放了的某個對象，都是調用該對象的equals()方法來進行

56、處理的。1.4 Map 1.4.1 概概述述數學中的映射關系在Java 中就是通過 Map 來實現的。它表示，里面存儲的元素是一個對（pair）,我們通過一個對象，可以在這個映射關系中找到另外一個和這個對象相關的東西。前面提到的我們對于根據帳號名得到對應的人員的信息，就屬于這種情況的應用。我們講一個人員的帳戶名和這人員的信息作了一個映射關系，也就是說，我們把帳戶名和人員信息當成了一個“鍵值對 ” ， “鍵”就是帳戶名，“值”就是人員信息。下面我們先看看Map 接口的常用方法。1.4.2 常常用用方方法法Map 接口不是 Collection 接口的繼承 。而是從自己的用于維護鍵-值關聯的接口層

57、次結構入手。按定義，該接口描述了從不重復的鍵到值的映射。我們可以把這個接口方法分成三組操作：改變、查詢和提供可選視圖。改變操作允許您從映射中添加和除去鍵-值對。鍵和值都可以為 null。但是，您不能把 Map 作為一個鍵或值添加給自身。 Object put(Object key,Object value)：用來存放一個鍵 -值對 Map 中 Object remove(Object key)：根據 key(鍵)，移除一個鍵-值對，并將值返回 void putAll(Map mapping) ：將另外一個 Map 中的元素存入當前的 Map 中 void clear() ：清空當前 Map 中

58、的元素查詢操作允許您檢查映射內容： Object get(Object key) ：根據 key(鍵)取得對應的值 boolean containsKey(Object key) ：判斷 Map 中是否存在某鍵（ key） boolean containsValue(Object value):判斷 Map中是否存在某值 (value) int size():返回 Map 中 鍵-值對的個數 boolean isEmpty() ：判斷當前 Map 是否為空最后一組方法允許您把鍵或值的組作為集合來處理。 public Set keySet() ：返回所有的鍵（ key） ，并使用Set 容器存放

59、 public Collection values() ：返回所有的值（ Value） ，并使用 Collection 存放 public Set entrySet() ：返回一個實現 Map.Entry 接口的元素 Set因為映射中鍵的集合必須是唯一的，就使用 Set 來支持。因為映射中值的集合可能不唯一，就使用 Collection 來支持。最后一個方法返回一個實現 Map.Entry 接口的元素 Set。我們看看 Map 的常用實現類的比較，如下表： 簡述簡述 實現實現 操作特性操作特性 成員要求成員要求 HashMap能滿足用戶對能滿足用戶對 Map 的的通用需求通用需求 鍵成員可為任

60、意鍵成員可為任意Object 子類的對象，子類的對象，但如果覆蓋了但如果覆蓋了 equals方法，同時注意修改方法，同時注意修改hashCode 方法。方法。 TreeMap支持對鍵有序地遍歷，支持對鍵有序地遍歷，使用時建議先用使用時建議先用HashMap 增加和刪除增加和刪除成員，最后從成員，最后從HashMap 生成生成TreeMap； 附加實現附加實現了了 SortedMap 接口，接口，支持子支持子 Map 等要求順等要求順序的操作序的操作 鍵成員要求實現鍵成員要求實現Comparable接口，或接口，或者使用者使用 Comparator 構構造造 TreeMap 鍵成員一鍵成員一般為