8.7 新集合 · Java 編程思想

# 8.7 新集合對我來說，集合類屬于最強大的一種工具，特別適合在原創編程中使用。大家可能已感覺到我對Java 1.1提供的集合多少有點兒失望。因此，看到Java 1.2對集合重新引起了正確的注意后，確實令人非常愉快。這個版本的集合也得到了完全的重新設計（由Sun公司的Joshua Bloch）。我認為新設計的集合是Java 1.2中兩項最主要的特性之一（另一項是Swing庫，將在第13章敘述），因為它們極大方便了我們的編程，也使Java變成一種更成熟的編程系統。有些設計使得元素間的結合變得更緊密，也更容易讓人理解。例如，許多名字都變得更短、更明確了，而且更易使用；類型同樣如此。有些名字進行了修改，更接近于通俗：我感覺特別好的一個是用“迭代器”（`Inerator`）代替了“枚舉”（`Enumeration`）。此次重新設計也加強了集合庫的功能。現在新增的行為包括鏈接列表、隊列以及撤消組隊（即“雙終點隊列”）。集合庫的設計是相當困難的（會遇到大量庫設計問題）。在C++中，STL用多個不同的類來覆蓋基礎。這種做法比起STL以前是個很大的進步，那時根本沒做這方面的考慮。但仍然沒有很好地轉換到Java里面。結果就是一大堆特別容易混淆的類。在另一個極端，我曾發現一個集合庫由單個類構成：`collection`，它同時作為`Vector`和`Hashtable`使用。新集合庫的設計者則希望達到一種新的平衡：實現人們希望從一個成熟集合庫上獲得的完整功能，同時又要比STL和其他類似的集合庫更易學習和使用。這樣得到的結果在某些場合顯得有些古怪。但和早期Java庫的一些決策不同，這些古怪之處并非偶然出現的，而是以復雜性作為代價，在進行仔細權衡之后得到的結果。這樣做也許會延長人們掌握一些庫概念的時間，但很快就會發現自己很樂于使用那些新工具，而且變得越來越離不了它。新的集合庫考慮到了“容納自己對象”的問題，并將其分割成兩個明確的概念： (1) 集合（`Collection`）：一組單獨的元素，通常應用了某種規則。在這里，一個`List`（列表）必須按特定的順序容納元素，而一個`Set`（集）不可包含任何重復的元素。相反，“包”（`Bag`）的概念未在新的集合庫中實現，因為“列表”已提供了類似的功能。 (2) 映射（`Map`）：一系列“鍵－值”對（這已在散列表身上得到了充分的體現）。從表面看，這似乎應該成為一個“鍵－值”對的“集合”，但假若試圖按那種方式實現它，就會發現實現過程相當笨拙。這進一步證明了應該分離成單獨的概念。另一方面，可以方便地查看Map的某個部分。只需創建一個集合，然后用它表示那一部分即可。這樣一來，`Map`就可以返回自己鍵的一個`Set`、一個包含自己值的`List`或者包含自己“鍵－值”對的一個`List`。和數組相似，`Map`可方便擴充到多個“維”，毋需涉及任何新概念。只需簡單地在一個`Map`里包含其他`Map`（后者又可以包含更多的`Map`，以此類推）。 `Collection`和`Map`可通過多種形式實現，具體由編程要求決定。下面列出的是一個幫助大家理解的新集合示意圖： ![](https://box.kancloud.cn/6d0d122649e487fd0aa7d71e7fb3e9c3_480x435.gif) 這張圖剛開始的時候可能讓人有點兒摸不著頭腦，但在通讀了本章以后，相信大家會真正理解它實際只有三個集合組件：`Map`，`List`和`Set`。而且每個組件實際只有兩、三種實現方式（注釋⑥），而且通常都只有一種特別好的方式。只要看出了這一點，集合就不會再令人生畏。 ⑥：寫作本章時，Java 1.2尚處于β測試階段，所以這張示意圖沒有包括以后會加入的`TreeSet`。虛線框代表“接口”，點線框代表“抽象”類，而實線框代表普通（實際）類。點線箭頭表示一個特定的類準備實現一個接口（在抽象類的情況下，則是“部分”實現一個接口）。雙線箭頭表示一個類可生成箭頭指向的那個類的對象。例如，任何集合都可以生成一個迭代器（`Iterator`），而一個列表可以生成一個`ListIterator`（以及原始的迭代器，因為列表是從集合繼承的）。致力于容納對象的接口是`Collection`，`List`，`Set`和`Map`。在傳統情況下，我們需要寫大量代碼才能同這些接口打交道。而且為了指定自己想使用的準確類型，必須在創建之初進行設置。所以可能創建下面這樣的一個`List`： ``` List x = new LinkedList(); ``` 當然，也可以決定將x作為一個`LinkedList`使用（而不是一個普通的`List`），并用`x`負載準確的類型信息。使用接口的好處就是一旦決定改變自己的實現細節，要做的全部事情就是在創建的時候改變它，就象下面這樣： ``` List x = new ArrayList(); ``` 其余代碼可以保持原封不動。在類的分級結構中，可看到大量以`Abstract`（抽象）開頭的類，這剛開始可能會使人感覺迷惑。它們實際上是一些工具，用于“部分”實現一個特定的接口。舉個例子來說，假如想生成自己的Set，就不是從`Set`接口開始，然后自行實現所有方法。相反，我們可以從`AbstractSet`繼承，只需極少的工作即可得到自己的新類。盡管如此，新集合庫仍然包含了足夠的功能，可滿足我們的幾乎所有需求。所以考慮到我們的目的，可忽略所有以`Abstract`開頭的類。因此，在觀看這張示意圖時，真正需要關心的只有位于最頂部的“接口”以及普通（實際）類——均用實線方框包圍。通常需要生成實際類的一個對象，將其向上轉換為對應的接口。以后即可在代碼的任何地方使用那個接口。下面是一個簡單的例子，它用`String`對象填充一個集合，然后打印出集合內的每一個元素： ``` //: SimpleCollection.java // A simple example using the new Collections package c08.newcollections; import java.util.*; public class SimpleCollection { public static void main(String[] args) { Collection c = new ArrayList(); for(int i = 0; i < 10; i++) c.add(Integer.toString(i)); Iterator it = c.iterator(); while(it.hasNext()) System.out.println(it.next()); } } ///:~ ``` 新集合庫的所有代碼示例都置于子目錄`newcollections`下，這樣便可提醒自己這些工作只對于Java 1.2有效。這樣一來，我們必須用下述代碼來調用程序： ``` java c08.newcollections.SimpleCollection ``` 采用的語法與其他程序是差不多的。大家可以看到新集合屬于`java.util`庫的一部分，所以在使用時不需要再添加任何額外的`import`語句。 `main()`的第一行創建了一個`ArrayList`對象，然后將其向上轉換成為一個集合。由于這個例子只使用了`Collection`方法，所以從`Collection`繼承的一個類的任何對象都可以正常工作。但`ArrayList`是一個典型的`Collection`，它代替了`Vector`的位置。顯然，`add()`方法的作用是將一個新元素置入集合里。然而，用戶文檔謹慎地指出`add()`“保證這個集合包含了指定的元素”。這一點是為`Set`作鋪墊的，后者只有在元素不存在的前提下才會真的加入那個元素。對于`ArrayList`以及其他任何形式的`List`，`add()`肯定意味著“直接加入”。利用`iterator()`方法，所有集合都能生成一個“迭代器”（`Iterator`）。迭代器其實就象一個“枚舉”（`Enumeration`），是后者的一個替代物，只是： (1) 它采用了一個歷史上默認、而且早在OOP中得到廣泛采納的名字（迭代器）。 (2) 采用了比`Enumeration`更短的名字：`hasNext()`代替了`hasMoreElement()`，而`next()`代替了`nextElement()`。 (3) 添加了一個名為`remove()`的新方法，可刪除由`Iterator`生成的上一個元素。所以每次調用`next()`的時候，只需調用`remove()`一次。在`SimpleCollection.java`中，大家可看到創建了一個迭代器，并用它在集合里遍歷，打印出每個元素。 ## 8.7.1 使用`Collections` 下面這張表格總結了用一個集合能做的所有事情（亦可對`Set`和`List`做同樣的事情，盡管`List`還提供了一些額外的功能）。`Map`不是從`Collection`繼承的，所以要單獨對待。 ``` Boolean add(Object) *Ensures that the Collection contains the argument. Returns false if it doesn’t add the argument. Boolean addAll(Collection) *Adds all the elements in the argument. Returns true if any elements were added. void clear( ) *Removes all the elements in the Collection. Boolean contains(Object) True if the Collection contains the argument. Boolean containsAll(Collection) True if the Collection contains all the elements in the argument. Boolean isEmpty( ) True if the Collection has no elements. Iterator iterator( ) Returns an Iterator that you can use to move through the elements in the Collection. Boolean remove(Object) *If the argument is in the Collection, one instance of that element is removed. Returns true if a removal occurred. Boolean removeAll(Collection) *Removes all the elements that are contained in the argument. Returns true if any removals occurred. Boolean retainAll(Collection) *Retains only elements that are contained in the argument (an “intersection” from set theory). Returns true if any changes occurred. int size( ) Returns the number of elements in the Collection. Object[] toArray( ) Returns an array containing all the elements in the Collection. Object[] toArray(Object[] a) Returns an array containing all the elements in the Collection, whose type is that of the array a rather than plain Object (you must cast the array to the right type). *This is an “optional” method, which means it might not be implemented by a particular Collection. If not, that method throws an UnsupportedOperationException. Exceptions will be covered in Chapter 9. ``` + `boolean add(Object)` ＊保證集合內包含了參數。如果它沒有添加參數，就返回`false`（假） + `boolean addAll(Collection)` ＊添加參數內的所有元素。如果沒有添加元素，則返回`true`（真） + `void clear()` ＊刪除集合內的所有元素 + `boolean contains(Object)` 若集合包含參數，就返回“真” + `boolean containsAll(Collection)` 若集合包含了參數內的所有元素，就返回“真” + `boolean isEmpty()` 若集合內沒有元素，就返回“真” + `Iterator iterator()` 返回一個迭代器，以用它遍歷集合的各元素 + `boolean remove(Object)` ＊如參數在集合里，就刪除那個元素的一個實例。如果已進行了刪除，就返回“真” + `boolean removeAll(Collection)` ＊刪除參數里的所有元素。如果已進行了任何刪除，就返回“真” + `boolean retainAll(Collection)` ＊只保留包含在一個參數里的元素（一個理論的“交集”）。如果已進行了任何改變，就返回“真” + `int size()` 返回集合內的元素數量 + `Object[] toArray()` 返回包含了集合內所有元素的一個數組＊這是一個“可選的”方法，有的集合可能并未實現它。若確實如此，該方法就會遇到一個`UnsupportedOperatiionException`，即一個“操作不支持”異常，詳見第9章。下面這個例子向大家演示了所有方法。同樣地，它們只對從集合繼承的東西有效，一個`ArrayList`作為一種“不常用的分母”使用： ``` //: Collection1.java // Things you can do with all Collections package c08.newcollections; import java.util.*; public class Collection1 { // Fill with 'size' elements, start // counting at 'start': public static Collection fill(Collection c, int start, int size) { for(int i = start; i < start + size; i++) c.add(Integer.toString(i)); return c; } // Default to a "start" of 0: public static Collection fill(Collection c, int size) { return fill(c, 0, size); } // Default to 10 elements: public static Collection fill(Collection c) { return fill(c, 0, 10); } // Create & upcast to Collection: public static Collection newCollection() { return fill(new ArrayList()); // ArrayList is used for simplicity, but it's // only seen as a generic Collection // everywhere else in the program. } // Fill a Collection with a range of values: public static Collection newCollection(int start, int size) { return fill(new ArrayList(), start, size); } // Moving through a List with an iterator: public static void print(Collection c) { for(Iterator x = c.iterator(); x.hasNext();) System.out.print(x.next() + " "); System.out.println(); } public static void main(String[] args) { Collection c = newCollection(); c.add("ten"); c.add("eleven"); print(c); // Make an array from the List: Object[] array = c.toArray(); // Make a String array from the List: String[] str = (String[])c.toArray(new String[1]); // Find max and min elements; this means // different things depending on the way // the Comparable interface is implemented: System.out.println("Collections.max(c) = " + Collections.max(c)); System.out.println("Collections.min(c) = " + Collections.min(c)); // Add a Collection to another Collection c.addAll(newCollection()); print(c); c.remove("3"); // Removes the first one print(c); c.remove("3"); // Removes the second one print(c); // Remove all components that are in the // argument collection: c.removeAll(newCollection()); print(c); c.addAll(newCollection()); print(c); // Is an element in this Collection? System.out.println( "c.contains(\"4\") = " + c.contains("4")); // Is a Collection in this Collection? System.out.println( "c.containsAll(newCollection()) = " + c.containsAll(newCollection())); Collection c2 = newCollection(5, 3); // Keep all the elements that are in both // c and c2 (an intersection of sets): c.retainAll(c2); print(c); // Throw away all the elements in c that // also appear in c2: c.removeAll(c2); System.out.println("c.isEmpty() = " + c.isEmpty()); c = newCollection(); print(c); c.clear(); // Remove all elements System.out.println("after c.clear():"); print(c); } } ///:~ ``` 通過第一個方法，我們可用測試數據填充任何集合。在當前這種情況下，只是將`int`轉換成`String`。第二個方法將在本章其余的部分經常采用。 `newCollection()`的兩個版本都創建了`ArrayList`，用于包含不同的數據集，并將它們作為集合對象返回。所以很明顯，除了`Collection`接口之外，不會再用到其他什么。 `print()`方法也會在本節經常用到。由于它用一個迭代器（`Iterator`）在一個集合內遍歷，而任何集合都可以產生這樣的一個迭代器，所以它適用于`List`和`Set`，也適用于由一個`Map`生成的`Collection`。 `main()`用簡單的手段顯示出了集合內的所有方法。在后續的小節里，我們將比較`List`，`Set`和`Map`的不同實現方案，同時指出在各種情況下哪一種方案應成為首選（帶有星號的那個）。大家會發現這里并未包括一些傳統的類，如`Vector`，`Stack`以及`Hashtable`等。因為不管在什么情況下，新集合內都有自己首選的類。 ## 8.7.2 使用`Lists` ``` List (interface) Order is the most important feature of a List; it promises to maintain elements in a particular sequence. List adds a number of methods to Collection that allow insertion and removal of elements in the middle of a List. (This is recommended only for a LinkedList.) A List will produce a ListIterator, and using this you can traverse the List in both directions, as well as insert and remove elements in the middle of the list (again, recommended only for a LinkedList). ArrayList* A List backed by an array. Use instead of Vector as a general-purpose object holder. Allows rapid random access to elements, but is slow when inserting and removing elements from the middle of a list. ListIterator should be used only for back-and-forth traversal of an ArrayList, but not for inserting and removing elements, which is expensive compared to LinkedList. LinkedList Provides optimal sequential access, with inexpensive insertions and deletions from the middle of the list. Relatively slow for random access. (Use ArrayList instead.) Also has addFirst( ), addLast( ), getFirst( ), getLast( ), removeFirst( ), and removeLast( ) (which are not defined in any interfaces or base classes) to allow it to be used as a stack, a queue, and a dequeue. ``` + `List`（接口）順序是`List`最重要的特性；它可保證元素按照規定的順序排列。`List`為`Collection`添加了大量方法，以便我們在`List`中部插入和刪除元素（只推薦對`LinkedList`這樣做）。`List`也會生成一個`ListIterator`（列表迭代器），利用它可在一個列表里朝兩個方向遍歷，同時插入和刪除位于列表中部的元素（同樣地，只建議對`LinkedList`這樣做） + `ArrayList`＊由一個數組后推得到的`List`。作為一個常規用途的對象容器使用，用于替換原先的`Vector`。允許我們快速訪問元素，但在從列表中部插入和刪除元素時，速度卻嫌稍慢。一般只應該用`ListIterator`對一個`ArrayList`進行向前和向后遍歷，不要用它刪除和插入元素；與`LinkedList`相比，它的效率要低許多 + `LinkedList `提供優化的順序訪問性能，同時可以高效率地在列表中部進行插入和刪除操作。但在進行隨機訪問時，速度卻相當慢，此時應換用`ArrayList`。也提供了`addFirst()`，`addLast()`，`getFirst()`，`getLast()`，`removeFirst()`以及`removeLast()`（未在任何接口或基類中定義），以便將其作為一個規格、隊列以及一個雙向隊列使用下面這個例子中的方法每個都覆蓋了一組不同的行為：每個列表都能做的事情（`basicTest()`），通過一個迭代器遍歷（`iterMotion()`）、用一個迭代器改變某些東西（`iterManipulation()`）、體驗列表處理的效果（`testVisual()`）以及只有`LinkedList`才能做的事情等： ``` //: List1.java // Things you can do with Lists package c08.newcollections; import java.util.*; public class List1 { // Wrap Collection1.fill() for convenience: public static List fill(List a) { return (List)Collection1.fill(a); } // You can use an Iterator, just as with a // Collection, but you can also use random // access with get(): public static void print(List a) { for(int i = 0; i < a.size(); i++) System.out.print(a.get(i) + " "); System.out.println(); } static boolean b; static Object o; static int i; static Iterator it; static ListIterator lit; public static void basicTest(List a) { a.add(1, "x"); // Add at location 1 a.add("x"); // Add at end // Add a collection: a.addAll(fill(new ArrayList())); // Add a collection starting at location 3: a.addAll(3, fill(new ArrayList())); b = a.contains("1"); // Is it in there? // Is the entire collection in there? b = a.containsAll(fill(new ArrayList())); // Lists allow random access, which is cheap // for ArrayList, expensive for LinkedList: o = a.get(1); // Get object at location 1 i = a.indexOf("1"); // Tell index of object // indexOf, starting search at location 2: i = a.indexOf("1", 2); b = a.isEmpty(); // Any elements inside? it = a.iterator(); // Ordinary Iterator lit = a.listIterator(); // ListIterator lit = a.listIterator(3); // Start at loc 3 i = a.lastIndexOf("1"); // Last match i = a.lastIndexOf("1", 2); // ...after loc 2 a.remove(1); // Remove location 1 a.remove("3"); // Remove this object a.set(1, "y"); // Set location 1 to "y" // Keep everything that's in the argument // (the intersection of the two sets): a.retainAll(fill(new ArrayList())); // Remove elements in this range: a.removeRange(0, 2); // Remove everything that's in the argument: a.removeAll(fill(new ArrayList())); i = a.size(); // How big is it? a.clear(); // Remove all elements } public static void iterMotion(List a) { ListIterator it = a.listIterator(); b = it.hasNext(); b = it.hasPrevious(); o = it.next(); i = it.nextIndex(); o = it.previous(); i = it.previousIndex(); } public static void iterManipulation(List a) { ListIterator it = a.listIterator(); it.add("47"); // Must move to an element after add(): it.next(); // Remove the element that was just produced: it.remove(); // Must move to an element after remove(): it.next(); // Change the element that was just produced: it.set("47"); } public static void testVisual(List a) { print(a); List b = new ArrayList(); fill(b); System.out.print("b = "); print(b); a.addAll(b); a.addAll(fill(new ArrayList())); print(a); // Shrink the list by removing all the // elements beyond the first 1/2 of the list System.out.println(a.size()); System.out.println(a.size()/2); a.removeRange(a.size()/2, a.size()/2 + 2); print(a); // Insert, remove, and replace elements // using a ListIterator: ListIterator x = a.listIterator(a.size()/2); x.add("one"); print(a); System.out.println(x.next()); x.remove(); System.out.println(x.next()); x.set("47"); print(a); // Traverse the list backwards: x = a.listIterator(a.size()); while(x.hasPrevious()) System.out.print(x.previous() + " "); System.out.println(); System.out.println("testVisual finished"); } // There are some things that only // LinkedLists can do: public static void testLinkedList() { LinkedList ll = new LinkedList(); Collection1.fill(ll, 5); print(ll); // Treat it like a stack, pushing: ll.addFirst("one"); ll.addFirst("two"); print(ll); // Like "peeking" at the top of a stack: System.out.println(ll.getFirst()); // Like popping a stack: System.out.println(ll.removeFirst()); System.out.println(ll.removeFirst()); // Treat it like a queue, pulling elements // off the tail end: System.out.println(ll.removeLast()); // With the above operations, it's a dequeue! print(ll); } public static void main(String args[]) { // Make and fill a new list each time: basicTest(fill(new LinkedList())); basicTest(fill(new ArrayList())); iterMotion(fill(new LinkedList())); iterMotion(fill(new ArrayList())); iterManipulation(fill(new LinkedList())); iterManipulation(fill(new ArrayList())); testVisual(fill(new LinkedList())); testLinkedList(); } } ///:~ ``` 在`basicTest()`和`iterMotiion()`中，只是簡單地發出調用，以便揭示出正確的語法。而且盡管捕獲了返回值，但是并未使用它。在某些情況下，之所以不捕獲返回值，是由于它們沒有什么特別的用處。在正式使用它們前，應仔細研究一下自己的聯機文檔，掌握這些方法完整、正確的用法。 ## 8.7.3 使用`Sets` `Set`擁有與`Collection`完全相同的接口，所以和兩種不同的`List`不同，它沒有什么額外的功能。相反，`Set`完全就是一個`Collection`，只是具有不同的行為（這是實例和多態性最理想的應用：用于表達不同的行為）。在這里，一個`Set`只允許每個對象存在一個實例（正如大家以后會看到的那樣，一個對象的“值”的構成是相當復雜的）。 ``` Set (interface) Each element that you add to the Set must be unique; otherwise the Set doesn’t add the duplicate element. Objects added to a Set must define equals( ) to establish object uniqueness. Set has exactly the same interface as Collection. The Set interface does not guarantee it will maintain its elements in any particular order. HashSet* For Sets where fast lookup time is important. Objects must also define hashCode( ). TreeSet An ordered Set backed by a red-black tree. This way, you can extract an ordered sequence from a Set. ``` + `Set`（接口）添加到`Set`的每個元素都必須是獨一無二的；否則`Set`就不會添加重復的元素。添加到`Set`里的對象必須定義`equals()`，從而建立對象的唯一性。`Set`擁有與`Collection`完全相同的接口。一個`Set`不能保證自己可按任何特定的順序維持自己的元素 + `HashSet`＊用于除非常小的以外的所有`Set`。對象也必須定義`hashCode()` + `ArraySet` 由一個數組后推得到的`Set`。面向非常小的`Set`設計，特別是那些需要頻繁創建和刪除的。對于小`Set`，與`HashSet`相比，`ArraySet`創建和迭代所需付出的代價都要小得多。但隨著`Set`的增大，它的性能也會大打折扣。不需要`HashCode()` + `TreeSet `由一個“紅黑樹”后推得到的順序`Set`（注釋⑦）。這樣一來，我們就可以從一個`Set`里提到一個順序集合 ⑦：直至本書寫作的時候，`TreeSet`仍然只是宣布，尚未正式實現。所以這里沒有提供使用`TreeSet`的例子。下面這個例子并沒有列出用一個`Set`能夠做的全部事情，因為接口與`Collection`是相同的，前例已經練習過了。相反，我們要例示的重點在于使一個`Set`獨一無二的行為： ``` //: Set1.java // Things you can do with Sets package c08.newcollections; import java.util.*; public class Set1 { public static void testVisual(Set a) { Collection1.fill(a); Collection1.fill(a); Collection1.fill(a); Collection1.print(a); // No duplicates! // Add another set to this one: a.addAll(a); a.add("one"); a.add("one"); a.add("one"); Collection1.print(a); // Look something up: System.out.println("a.contains(\"one\"): " + a.contains("one")); } public static void main(String[] args) { testVisual(new HashSet()); testVisual(new TreeSet()); } } ///:~ ``` 重復的值被添加到`Set`，但在打印的時候，我們會發現`Set`只接受每個值的一個實例。運行這個程序時，會注意到由`HashSet`維持的順序與`ArraySet`是不同的。這是由于它們采用了不同的方法來保存元素，以便它們以后的定位。`ArraySet`保持著它們的順序狀態，而`HashSet`使用一個散列函數，這是特別為快速檢索設計的）。創建自己的類型時，一定要注意`Set`需要通過一種方式來維持一種存儲順序，就象本章早些時候展示的“groundhog”（土拔鼠）例子那樣。下面是一個例子： ``` //: Set2.java // Putting your own type in a Set package c08.newcollections; import java.util.*; class MyType implements Comparable { private int i; public MyType(int n) { i = n; } public boolean equals(Object o) { return (o instanceof MyType) && (i == ((MyType)o).i); } public int hashCode() { return i; } public String toString() { return i + " "; } public int compareTo(Object o) { int i2 = ((MyType) o).i; return (i2 < i ? -1 : (i2 == i ? 0 : 1)); } } public class Set2 { public static Set fill(Set a, int size) { for(int i = 0; i < size; i++) a.add(new MyType(i)); return a; } public static Set fill(Set a) { return fill(a, 10); } public static void test(Set a) { fill(a); fill(a); // Try to add duplicates fill(a); a.addAll(fill(new TreeSet())); System.out.println(a); } public static void main(String[] args) { test(new HashSet()); test(new TreeSet()); } } ///:~ ``` 對`equals()`及`hashCode()`的定義遵照“groundhog”例子已經給出的形式。在兩種情況下都必須定義一個`equals()`。但只有要把類置入一個`HashSet`的前提下，才有必要使用`hashCode()`——這種情況是完全有可能的，因為通常應先選擇作為一個`Set`實現。 ## 8.7.4 使用`Maps` ``` Map (interface) Maintains key-value associations (pairs), so you can look up a value using a key. HashMap* Implementation based on a hash table. (Use this instead of Hashtable.) Provides constant-time performance for inserting and locating pairs. Performance can be adjusted via constructors that allow you to set the capacity and load factor of the hash table. TreeMap Implementation based on a red-black tree. When you view the keys or the pairs, they will be in sorted order (determined by Comparable or Comparator, discussed later). The point of a TreeMap is that you get the results in sorted order. TreeMap is the only Map with the subMap( ) method, which allows you to return a portion of the tree. ``` + `Map`（接口）維持“鍵－值”對應關系（對），以便通過一個鍵查找相應的值 + `HashMap`＊基于一個散列表實現（用它代替`Hashtable`）。針對“鍵－值”對的插入和檢索，這種形式具有最穩定的性能。可通過構造器對這一性能進行調整，以便設置散列表的“能力”和“裝載因子” + `ArrayMap` 由一個`ArrayList`后推得到的`Map`。對迭代的順序提供了精確的控制。面向非常小的`Map`設計，特別是那些需要經常創建和刪除的。對于非常小的`Map`，創建和迭代所付出的代價要比`HashMap`低得多。但在`Map`變大以后，性能也會相應地大幅度降低 + `TreeMap` 在一個“紅－黑”樹的基礎上實現。查看鍵或者“鍵－值”對時，它們會按固定的順序排列（取決于`Comparable`或 + `Comparator`，稍后即會講到）。`TreeMap`最大的好處就是我們得到的是已排好序的結果。`TreeMap`是含有`subMap()`方法的唯一一種`Map`，利用它可以返回樹的一部分下例包含了兩套測試數據以及一個`fill()`方法，利用該方法可以用任何兩維數組（由`Object`構成）填充任何`Map`。這些工具也會在其他`Map`例子中用到。 ``` //: Map1.java // Things you can do with Maps package c08.newcollections; import java.util.*; public class Map1 { public final static String[][] testData1 = { { "Happy", "Cheerful disposition" }, { "Sleepy", "Prefers dark, quiet places" }, { "Grumpy", "Needs to work on attitude" }, { "Doc", "Fantasizes about advanced degree"}, { "Dopey", "'A' for effort" }, { "Sneezy", "Struggles with allergies" }, { "Bashful", "Needs self-esteem workshop"}, }; public final static String[][] testData2 = { { "Belligerent", "Disruptive influence" }, { "Lazy", "Motivational problems" }, { "Comatose", "Excellent behavior" } }; public static Map fill(Map m, Object[][] o) { for(int i = 0; i < o.length; i++) m.put(o[i][0], o[i][1]); return m; } // Producing a Set of the keys: public static void printKeys(Map m) { System.out.print("Size = " + m.size() +", "); System.out.print("Keys: "); Collection1.print(m.keySet()); } // Producing a Collection of the values: public static void printValues(Map m) { System.out.print("Values: "); Collection1.print(m.values()); } // Iterating through Map.Entry objects (pairs): public static void print(Map m) { Collection entries = m.entries(); Iterator it = entries.iterator(); while(it.hasNext()) { Map.Entry e = (Map.Entry)it.next(); System.out.println("Key = " + e.getKey() + ", Value = " + e.getValue()); } } public static void test(Map m) { fill(m, testData1); // Map has 'Set' behavior for keys: fill(m, testData1); printKeys(m); printValues(m); print(m); String key = testData1[4][0]; String value = testData1[4][1]; System.out.println("m.containsKey(\"" + key + "\"): " + m.containsKey(key)); System.out.println("m.get(\"" + key + "\"): " + m.get(key)); System.out.println("m.containsValue(\"" + value + "\"): " + m.containsValue(value)); Map m2 = fill(new TreeMap(), testData2); m.putAll(m2); printKeys(m); m.remove(testData2[0][0]); printKeys(m); m.clear(); System.out.println("m.isEmpty(): " + m.isEmpty()); fill(m, testData1); // Operations on the Set change the Map: m.keySet().removeAll(m.keySet()); System.out.println("m.isEmpty(): " + m.isEmpty()); } public static void main(String args[]) { System.out.println("Testing HashMap"); test(new HashMap()); System.out.println("Testing TreeMap"); test(new TreeMap()); } } ///:~ ``` `printKeys()`，`printValues()`以及`print()`方法并不只是有用的工具，它們也清楚地揭示了一個`Map`的`Collection`“景象”的產生過程。`keySet()`方法會產生一個`Set`，它由`Map`中的鍵后推得來。在這兒，它只被當作一個`Collection`對待。`values()`也得到了類似的對待，它的作用是產生一個`List`，其中包含了`Map`中的所有值（注意鍵必須是獨一無二的，而值可以有重復）。由于這些`Collection`是由`Map`后推得到的，所以一個`Collection`中的任何改變都會在相應的`Map`中反映出來。 `print()`方法的作用是收集由`entries`產生的`Iterator`（迭代器），并用它同時打印出每個“鍵－值”對的鍵和值。程序剩余的部分提供了每種`Map`操作的簡單示例，并對每種類型的`Map`進行了測試。當創建自己的類，將其作為`Map`中的一個鍵使用時，必須注意到和以前的Set相同的問題。 ## 8.7.5 決定實現方案從早些時候的那幅示意圖可以看出，實際上只有三個集合組件：`Map`，`List`和`Set`。而且每個接口只有兩種或三種實現方案。若需使用由一個特定的接口提供的功能，如何才能決定到底采取哪一種方案呢？為理解這個問題，必須認識到每種不同的實現方案都有自己的特點、優點和缺點。比如在那張示意圖中，可以看到`Hashtable`，`Vector`和`Stack`的“特點”是它們都屬于“傳統”類，所以不會干擾原有的代碼。但在另一方面，應盡量避免為新的（Java 1.2）代碼使用它們。其他集合間的差異通常都可歸納為它們具體是由什么“后推”的。換言之，取決于物理意義上用于實現目標接口的數據結構是什么。例如，`ArrayList`，`LinkedList`以及`Vector`（大致等價于`ArrayList`）都實現了`List`接口，所以無論選用哪一個，我們的程序都會得到類似的結果。然而，`ArrayList`（以及`Vector`）是由一個數組后推得到的；而`LinkedList`是根據常規的雙重鏈接列表方式實現的，因為每個單獨的對象都包含了數據以及指向列表內前后元素的引用。正是由于這個原因，假如想在一個列表中部進行大量插入和刪除操作，那么`LinkedList`無疑是最恰當的選擇（`LinkedList`還有一些額外的功能，建立于`AbstractSequentialList`中）。若非如此，就情愿選擇`ArrayList`，它的速度可能要快一些。作為另一個例子，`Set`既可作為一個`ArraySet`實現，亦可作為`HashSet`實現。`ArraySet`是由一個`ArrayList`后推得到的，設計成只支持少量元素，特別適合要求創建和刪除大量`Set`對象的場合使用。然而，一旦需要在自己的`Set`中容納大量元素，`ArraySet`的性能就會大打折扣。寫一個需要`Set`的程序時，應默認選擇`HashSet`。而且只有在某些特殊情況下（對性能的提升有迫切的需求），才應切換到`ArraySet`。 (1) 決定使用何種`List` 為體會各種`List`實現方案間的差異，最簡便的方法就是進行一次性能測驗。下述代碼的作用是建立一個內部基類，將其作為一個測試床使用。然后為每次測驗都創建一個匿名內部類。每個這樣的內部類都由一個`test()`方法調用。利用這種方法，可以方便添加和刪除測試項目。 ``` //: ListPerformance.java // Demonstrates performance differences in Lists package c08.newcollections; import java.util.*; public class ListPerformance { private static final int REPS = 100; private abstract static class Tester { String name; int size; // Test quantity Tester(String name, int size) { this.name = name; this.size = size; } abstract void test(List a); } private static Tester[] tests = { new Tester("get", 300) { void test(List a) { for(int i = 0; i < REPS; i++) { for(int j = 0; j < a.size(); j++) a.get(j); } } }, new Tester("iteration", 300) { void test(List a) { for(int i = 0; i < REPS; i++) { Iterator it = a.iterator(); while(it.hasNext()) it.next(); } } }, new Tester("insert", 1000) { void test(List a) { int half = a.size()/2; String s = "test"; ListIterator it = a.listIterator(half); for(int i = 0; i < size * 10; i++) it.add(s); } }, new Tester("remove", 5000) { void test(List a) { ListIterator it = a.listIterator(3); while(it.hasNext()) { it.next(); it.remove(); } } }, }; public static void test(List a) { // A trick to print out the class name: System.out.println("Testing " + a.getClass().getName()); for(int i = 0; i < tests.length; i++) { Collection1.fill(a, tests[i].size); System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(a); long t2 = System.currentTimeMillis(); System.out.println(": " + (t2 - t1)); } } public static void main(String[] args) { test(new ArrayList()); test(new LinkedList()); } } ///:~ ``` 內部類`Tester`是一個抽象類，用于為特定的測試提供一個基類。它包含了一個要在測試開始時打印的字符串、一個用于計算測試次數或元素數量的`size`參數、用于初始化字段的一個構造器以及一個抽象方法`test()`。`test()`做的是最實際的測試工作。各種類型的測試都集中到一個地方：`tests`數組。我們用繼承于`Tester`的不同匿名內部類來初始化該數組。為添加或刪除一個測試項目，只需在數組里簡單地添加或移去一個內部類定義即可，其他所有工作都是自動進行的。首先用元素填充傳遞給`test()`的`List`，然后對`tests`數組中的測試計時。由于測試用機器的不同，結果當然也會有所區別。這個程序的宗旨是揭示出不同集合類型的相對性能比較。下面是某一次運行得到的結果： | 類型 | 獲取 | 迭代 | 插入 | 刪除 | | --- | --- | --- | --- | --- | | `ArrayList` | 110 | 270 | 1920 | 4780 | | `LinkedList` | 1870 | 7580 | 170 | 110 | 可以看出，在`ArrayList`中進行隨機訪問（即`get()`）以及循環迭代是最劃得來的；但對于`LinkedList`卻是一個不小的開銷。但另一方面，在列表中部進行插入和刪除操作對于`LinkedList`來說卻比`ArrayList`劃算得多。我們最好的做法也許是先選擇一個`ArrayList`作為自己的默認起點。以后若發現由于大量的插入和刪除造成了性能的降低，再考慮換成`LinkedList`不遲。 (2) 決定使用何種`Set` 可在`ArraySet`以及`HashSet`間作出選擇，具體取決于`Set`的大小（如果需要從一個`Set`中獲得一個順序列表，請用`TreeSet`；注釋⑧）。下面這個測試程序將有助于大家作出這方面的抉擇： ``` //: SetPerformance.java package c08.newcollections; import java.util.*; public class SetPerformance { private static final int REPS = 200; private abstract static class Tester { String name; Tester(String name) { this.name = name; } abstract void test(Set s, int size); } private static Tester[] tests = { new Tester("add") { void test(Set s, int size) { for(int i = 0; i < REPS; i++) { s.clear(); Collection1.fill(s, size); } } }, new Tester("contains") { void test(Set s, int size) { for(int i = 0; i < REPS; i++) for(int j = 0; j < size; j++) s.contains(Integer.toString(j)); } }, new Tester("iteration") { void test(Set s, int size) { for(int i = 0; i < REPS * 10; i++) { Iterator it = s.iterator(); while(it.hasNext()) it.next(); } } }, }; public static void test(Set s, int size) { // A trick to print out the class name: System.out.println("Testing " + s.getClass().getName() + " size " + size); Collection1.fill(s, size); for(int i = 0; i < tests.length; i++) { System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(s, size); long t2 = System.currentTimeMillis(); System.out.println(": " + ((double)(t2 - t1)/(double)size)); } } public static void main(String[] args) { // Small: test(new TreeSet(), 10); test(new HashSet(), 10); // Medium: test(new TreeSet(), 100); test(new HashSet(), 100); // Large: test(new HashSet(), 1000); test(new TreeSet(), 1000); } } ///:~ ``` ⑧：`TreeSet`在本書寫作時尚未成為一個正式的特性，但在這個例子中可以很輕松地為其添加一個測試。最后對`ArraySet`的測試只有500個元素，而不是1000個，因為它太慢了。 | 類型 | 測試大小 | 添加 | 包含 | 迭代 | | --- | --- | --- | --- | --- | | TreeSet | 10 | 22.0 | 11.0 | 16.0 | | | 100 | 22.5 | 13.2 | 12.1 | | | 1000 | 31.1 | 18.7 | 11.8 | | HashSet | 10 | 5.0 | 6.0 | 27.0 | | | 100 | 6.6 | 6.6 | 10.9 | | | 1000 | 7.4 | 6.6 | 9.5 | 進行`add()`以及`contains()`操作時，`HashSet`顯然要比`ArraySet`出色得多，而且性能明顯與元素的多寡關系不大。一般編寫程序的時候，幾乎永遠用不著使用`ArraySet`。 (3) 決定使用何種`Map` 選擇不同的`Map`實現方案時，注意`Map`的大小對于性能的影響是最大的，下面這個測試程序清楚地闡示了這一點： ``` //: MapPerformance.java // Demonstrates performance differences in Maps package c08.newcollections; import java.util.*; public class MapPerformance { private static final int REPS = 200; public static Map fill(Map m, int size) { for(int i = 0; i < size; i++) { String x = Integer.toString(i); m.put(x, x); } return m; } private abstract static class Tester { String name; Tester(String name) { this.name = name; } abstract void test(Map m, int size); } private static Tester[] tests = { new Tester("put") { void test(Map m, int size) { for(int i = 0; i < REPS; i++) { m.clear(); fill(m, size); } } }, new Tester("get") { void test(Map m, int size) { for(int i = 0; i < REPS; i++) for(int j = 0; j < size; j++) m.get(Integer.toString(j)); } }, new Tester("iteration") { void test(Map m, int size) { for(int i = 0; i < REPS * 10; i++) { Iterator it = m.entries().iterator(); while(it.hasNext()) it.next(); } } }, }; public static void test(Map m, int size) { // A trick to print out the class name: System.out.println("Testing " + m.getClass().getName() + " size " + size); fill(m, size); for(int i = 0; i < tests.length; i++) { System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(m, size); long t2 = System.currentTimeMillis(); System.out.println(": " + ((double)(t2 - t1)/(double)size)); } } public static void main(String[] args) { // Small: test(new Hashtable(), 10); test(new HashMap(), 10); test(new TreeMap(), 10); // Medium: test(new Hashtable(), 100); test(new HashMap(), 100); test(new TreeMap(), 100); // Large: test(new HashMap(), 1000); test(new Hashtable(), 1000); test(new TreeMap(), 1000); } } ///:~ ``` 由于`Map`的大小是最嚴重的問題，所以程序的計時測試按`Map`的大小（或容量）來分割時間，以便得到令人信服的測試結果。下面列出一系列結果（在你的機器上可能不同）： | 類型 | 測試大小 | 置入 | 取出 | 迭代 | | --- | --- | --- | --- | --- | | Hashtable | 10 | 11.0 | 5.0 | 44.0 | | | 100 | 7.7 | 7.7 | 16.5 | | | 1000 | 8.0 | 8.0 | 14.4 | | TreeMap | 10 | 16.0 | 11.0 | 22.0 | | | 100 | 25.8 | 15.4 | 13.2 | | | 1000 | 33.8 | 20.9 | 13.6 | | HashMap | 10 | 11.0 | 6.0 | 33.0 | | | 100 | 8.2 | 7.7 | 13.7 | | | 1000 | 8.0 | 7.8 | 11.9 | 即使大小為10，`ArrayMap`的性能也要比`HashMap`差——除迭代循環時以外。而在使用`Map`時，迭代的作用通常并不重要（`get()`通常是我們時間花得最多的地方）。`TreeMap`提供了出色的`put()`以及迭代時間，但`get()`的性能并不佳。但是，我們為什么仍然需要使用`TreeMap`呢？這樣一來，我們可以不把它作為`Map`使用，而作為創建順序列表的一種途徑。樹的本質在于它總是順序排列的，不必特別進行排序（它的排序方式馬上就要講到）。一旦填充了一個`TreeMap`，就可以調用`keySet()`來獲得鍵的一個`Set`“景象”。然后用`toArray()`產生包含了那些鍵的一個數組。隨后，可用`static`方法`Array.binarySearch()`快速查找排好序的數組中的內容。當然，也許只有在`HashMap`的行為不可接受的時候，才需要采用這種做法。因為`HashMap`的設計宗旨就是進行快速的檢索操作。最后，當我們使用`Map`時，首要的選擇應該是`HashMap`。只有在極少數情況下才需要考慮其他方法。此外，在上面那張表里，有另一個性能問題沒有反映出來。下述程序用于測試不同類型`Map`的創建速度： ``` //: MapCreation.java // Demonstrates time differences in Map creation package c08.newcollections; import java.util.*; public class MapCreation { public static void main(String[] args) { final long REPS = 100000; long t1 = System.currentTimeMillis(); System.out.print("Hashtable"); for(long i = 0; i < REPS; i++) new Hashtable(); long t2 = System.currentTimeMillis(); System.out.println(": " + (t2 - t1)); t1 = System.currentTimeMillis(); System.out.print("TreeMap"); for(long i = 0; i < REPS; i++) new TreeMap(); t2 = System.currentTimeMillis(); System.out.println(": " + (t2 - t1)); t1 = System.currentTimeMillis(); System.out.print("HashMap"); for(long i = 0; i < REPS; i++) new HashMap(); t2 = System.currentTimeMillis(); System.out.println(": " + (t2 - t1)); } } ///:~ ``` 在寫這個程序期間，`TreeMap`的創建速度比其他兩種類型明顯快得多（但你應親自嘗試一下，因為據說新版本可能會改善`ArrayMap`的性能）。考慮到這方面的原因，同時由于前述`TreeMap`出色的`put()`性能，所以如果需要創建大量`Map`，而且只有在以后才需要涉及大量檢索操作，那么最佳的策略就是：創建和填充`TreeMap`；以后檢索量增大的時候，再將重要的`TreeMap`轉換成`HashMap`——使用`HashMap(Map)`構造器。同樣地，只有在事實證明確實存在性能瓶頸后，才應關心這些方面的問題——先用起來，再根據需要加快速度。 ## 8.7.6 未支持的操作利用`static`（靜態）數組`Arrays.toList()`，也許能將一個數組轉換成`List`，如下所示： ``` //: Unsupported.java // Sometimes methods defined in the Collection // interfaces don't work! package c08.newcollections; import java.util.*; public class Unsupported { private static String[] s = { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", }; static List a = Arrays.toList(s); static List a2 = Arrays.toList( new String[] { s[3], s[4], s[5] }); public static void main(String[] args) { Collection1.print(a); // Iteration System.out.println( "a.contains(" + s[0] + ") = " + a.contains(s[0])); System.out.println( "a.containsAll(a2) = " + a.containsAll(a2)); System.out.println("a.isEmpty() = " + a.isEmpty()); System.out.println( "a.indexOf(" + s[5] + ") = " + a.indexOf(s[5])); // Traverse backwards: ListIterator lit = a.listIterator(a.size()); while(lit.hasPrevious()) System.out.print(lit.previous()); System.out.println(); // Set the elements to different values: for(int i = 0; i < a.size(); i++) a.set(i, "47"); Collection1.print(a); // Compiles, but won't run: lit.add("X"); // Unsupported operation a.clear(); // Unsupported a.add("eleven"); // Unsupported a.addAll(a2); // Unsupported a.retainAll(a2); // Unsupported a.remove(s[0]); // Unsupported a.removeAll(a2); // Unsupported } } ///:~ ``` 從中可以看出，實際只實現了`Collection`和`List`接口的一部分。剩余的方法導致了不受歡迎的一種情況，名為`UnsupportedOperationException`。在下一章里，我們會講述異常的詳細情況，但在這里有必要進行一下簡單說明。這里的關鍵在于“集合接口”，以及新集合庫內的另一些接口，它們都包含了“可選的”方法。在實現那些接口的集合類中，或者提供、或者沒有提供對那些方法的支持。若調用一個未獲支持的方法，就會導致一個`UnsupportedOperationException`（操作未支持異常），這表明出現了一個編程錯誤。大家或許會覺得奇怪，不是說“接口”和基類最大的“賣點”就是它們許諾這些方法能產生一些有意義的行為嗎？上述異常破壞了那個許諾——它調用的一部分方法不僅不能產生有意義的行為，而且還會中止程序的運行。在這些情況下，類型的所謂安全保證似乎顯得一錢不值！但是，情況并沒有想象的那么壞。通過`Collection`，`List`，`Set`或者`Map`，編譯器仍然限制我們只能調用那個接口中的方法，所以它和Smalltalk還是存在一些區別的（在Smalltalk中，可為任何對象調用任何方法，而且只有在運行程序時才知道這些調用是否可行）。除此以外，以`Collection`作為參數的大多數方法只能從那個集合中讀取數據——`Collection`的所有`read`方法都不是可選的。這樣一來，系統就可避免在設計期間出現接口的沖突。而在集合庫的其他設計模式中，最終經常都會得到數量過多的接口，用它們描述基本方案的每一種變化形式，所以學習和掌握顯得非常困難。有些時候，甚至難于捕捉接口中的所有特殊情況，因為人們可能設計出任何新接口。但Java的“不支持的操作”方法卻達到了新集合庫的一個重要設計目標：易于學習和使用。但是，為了使這一方法真正有效，卻需滿足下述條件： (1) `UnsupportedOperationException`必須屬于一種“非常”事件。也就是說，對于大多數類來說，所有操作都應是可行的。只有在一些特殊情況下，一、兩個操作才可能未獲支持。新集合庫滿足了這一條件，因為絕大多數時候用到的類——`ArrayList`，`LinkedList`，`HashList`和`HashMap`，以及其他集合方案——都提供了對所有操作的支持。但是，如果想新建一個集合，同時不想為集合接口中的所有方法都提供有意義的定義，同時令其仍與現有庫配合，這種設計方法也確實提供了一個“后門”可以利用。 (2) 若一個操作未獲支持，那么`UnsupportedOperationException`（未支持的操作異常）極有可能在實現期間出現，則不是在產品已交付給客戶以后才會出現。它畢竟指出的是一個編程錯誤——不正確地使用了一個類。這一點不能十分確定，通過也可以看出這種方案的“試驗”特征——只有經過多次試驗，才能找出最理想的工作方式。在上面的例子中，`Arrays.toList()`產生了一個`List`（列表），該列表是由一個固定長度的數組后推出來的。因此唯一能夠支持的就是那些不改變數組長度的操作。在另一方面，若請求一個新接口表達不同種類的行為（可能叫作`FixedSizeList`——固定長度列表），就有遭遇更大的復雜程度的危險。這樣一來，以后試圖使用庫的時候，很快就會發現自己不知從何處下手。對那些采用`Collection`，`List`，`Set`或者`Map`作為參數的方法，它們的文檔應當指出哪些可選的方法是必須實現的。舉個例子來說，排序要求實現`set()`和`Iterator.set()`方法，但不包括`add()`和`remove()`。 ## 8.7.7 排序和搜索 Java 1.2添加了自己的一套實用工具，可用來對數組或列表進行排列和搜索。這些工具都屬于兩個新類的“靜態”方法。這兩個類分別是用于排序和搜索數組的`Arrays`，以及用于排序和搜索列表的`Collections`。 (1) 數組 `Arrays`類為所有基本數據類型的數組提供了一個重載的`sort()`和`binarySearch()`，它們亦可用于`String`和`Object`。下面這個例子顯示出如何排序和搜索一個字節數組（其他所有基本數據類型都是類似的）以及一個`String`數組： ``` //: Array1.java // Testing the sorting & searching in Arrays package c08.newcollections; import java.util.*; public class Array1 { static Random r = new Random(); static String ssource = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "abcdefghijklmnopqrstuvwxyz"; static char[] src = ssource.toCharArray(); // Create a random String public static String randString(int length) { char[] buf = new char[length]; int rnd; for(int i = 0; i < length; i++) { rnd = Math.abs(r.nextInt()) % src.length; buf[i] = src[rnd]; } return new String(buf); } // Create a random array of Strings: public static String[] randStrings(int length, int size) { String[] s = new String[size]; for(int i = 0; i < size; i++) s[i] = randString(length); return s; } public static void print(byte[] b) { for(int i = 0; i < b.length; i++) System.out.print(b[i] + " "); System.out.println(); } public static void print(String[] s) { for(int i = 0; i < s.length; i++) System.out.print(s[i] + " "); System.out.println(); } public static void main(String[] args) { byte[] b = new byte[15]; r.nextBytes(b); // Fill with random bytes print(b); Arrays.sort(b); print(b); int loc = Arrays.binarySearch(b, b[10]); System.out.println("Location of " + b[10] + " = " + loc); // Test String sort & search: String[] s = randStrings(4, 10); print(s); Arrays.sort(s); print(s); loc = Arrays.binarySearch(s, s[4]); System.out.println("Location of " + s[4] + " = " + loc); } } ///:~ ``` 類的第一部分包含了用于產生隨機字符串對象的實用工具，可供選擇的隨機字母保存在一個字符數組中。`randString()`返回一個任意長度的字符串；而`readStrings()`創建隨機字符串的一個數組，同時給定每個字符串的長度以及希望的數組大小。兩個`print()`方法簡化了對示范數組的顯示。在`main()`中，`Random.nextBytes()`用隨機選擇的字節填充數組參數（沒有對應的`Random`方法用于創建其他基本數據類型的數組）。獲得一個數組后，便可發現為了執行`sort()`或者`binarySearch()`，只需發出一次方法調用即可。與`binarySearch()`有關的還有一個重要的警告：若在執行一次`binarySearch()`之前不調用`sort()`，便會發生不可預測的行為，其中甚至包括無限循環。對`String`的排序以及搜索是相似的，但在運行程序的時候，我們會注意到一個有趣的現象：排序遵守的是字典順序，亦即大寫字母在字符集中位于小寫字母的前面。因此，所有大寫字母都位于列表的最前面，后面再跟上小寫字母——Z居然位于a的前面。似乎連電話簿也是這樣排序的。 (2) 可比較與比較器但假若我們不滿足這一排序方式，又該如何處理呢？例如本書后面的索引，如果必須對以`A`或`a`開頭的詞條分別到兩處地方查看，那么肯定會使讀者頗不耐煩。若想對一個`Object`數組進行排序，那么必須解決一個問題。根據什么來判定兩個`Object`的順序呢？不幸的是，最初的Java設計者并不認為這是一個重要的問題，否則就已經在根類`Object`里定義它了。這樣造成的一個后果便是：必須從外部進行`Object`的排序，而且新的集合庫提供了實現這一操作的標準方式（最理想的是在`Object`里定義它）。針對`Object`數組（以及`String`，它當然屬于`Object`的一種），可使用一個`sort()`，并令其接納另一個參數：實現了`Comparator`接口（即“比較器”接口，新集合庫的一部分）的一個對象，并用它的單個`compare()`方法進行比較。這個方法將兩個準備比較的對象作為自己的參數使用——若第一個參數小于第二個，返回一個負整數；若相等，返回零；若第一個參數大于第二個，則返回正整數。基于這一規則，上述例子的`String`部分便可重新寫過，令其進行真正按字母順序的排序： ``` //: AlphaComp.java // Using Comparator to perform an alphabetic sort package c08.newcollections; import java.util.*; public class AlphaComp implements Comparator { public int compare(Object o1, Object o2) { // Assume it's used only for Strings... String s1 = ((String)o1).toLowerCase(); String s2 = ((String)o2).toLowerCase(); return s1.compareTo(s2); } public static void main(String[] args) { String[] s = Array1.randStrings(4, 10); Array1.print(s); AlphaComp ac = new AlphaComp(); Arrays.sort(s, ac); Array1.print(s); // Must use the Comparator to search, also: int loc = Arrays.binarySearch(s, s[3], ac); System.out.println("Location of " + s[3] + " = " + loc); } } ///:~ ``` 通過轉換為`String`，`compare()`方法會進行“暗示”性的測試，保證自己操作的只能是`String`對象——運行期系統會捕獲任何差錯。將兩個字符串都強迫換成小寫形式后，`String.compareTo()`方法會產生預期的結果。若用自己的`Comparator`來進行一次`sort()`，那么在使用`binarySearch()`時必須使用那個相同的`Comparator`。 `Arrays`類提供了另一個`sort()`方法，它會采用單個參數：一個`Object`數組，但沒有`Comparator`。這個`sort()`方法也必須用同樣的方式來比較兩個`Object`。通過實現`Comparable`接口，它采用了賦予一個類的“自然比較方法”。這個接口含有單獨一個方法——`compareTo()`，能分別根據它小于、等于或者大于參數而返回負數、零或者正數，從而實現對象的比較。下面這個例子簡單地闡示了這一點： ``` //: CompClass.java // A class that implements Comparable package c08.newcollections; import java.util.*; public class CompClass implements Comparable { private int i; public CompClass(int ii) { i = ii; } public int compareTo(Object o) { // Implicitly tests for correct type: int argi = ((CompClass)o).i; if(i == argi) return 0; if(i < argi) return -1; return 1; } public static void print(Object[] a) { for(int i = 0; i < a.length; i++) System.out.print(a[i] + " "); System.out.println(); } public String toString() { return i + ""; } public static void main(String[] args) { CompClass[] a = new CompClass[20]; for(int i = 0; i < a.length; i++) a[i] = new CompClass( (int)(Math.random() *100)); print(a); Arrays.sort(a); print(a); int loc = Arrays.binarySearch(a, a[3]); System.out.println("Location of " + a[3] + " = " + loc); } } ///:~ ``` 當然，我們的`compareTo()`方法亦可根據實際情況增大復雜程度。 (3) 列表可用與數組相同的形式排序和搜索一個列表（`List`）。用于排序和搜索列表的靜態方法包含在類`Collections`中，但它們擁有與`Arrays`中差不多的簽名：`sort(List)`用于對一個實現了`Comparable`的對象列表進行排序；`binarySearch(List,Object)`用于查找列表中的某個對象；`sort(List,Comparator)`利用一個“比較器”對一個列表進行排序；而`binarySearch`(`List`,`Object`,`Comparator`)則用于查找那個列表中的一個對象（注釋⑨）。下面這個例子利用了預先定義好的`CompClass`和`AlphaComp`來示范`Collections`中的各種排序工具： ``` //: ListSort.java // Sorting and searching Lists with 'Collections' package c08.newcollections; import java.util.*; public class ListSort { public static void main(String[] args) { final int SZ = 20; // Using "natural comparison method": List a = new ArrayList(); for(int i = 0; i < SZ; i++) a.add(new CompClass( (int)(Math.random() *100))); Collection1.print(a); Collections.sort(a); Collection1.print(a); Object find = a.get(SZ/2); int loc = Collections.binarySearch(a, find); System.out.println("Location of " + find + " = " + loc); // Using a Comparator: List b = new ArrayList(); for(int i = 0; i < SZ; i++) b.add(Array1.randString(4)); Collection1.print(b); AlphaComp ac = new AlphaComp(); Collections.sort(b, ac); Collection1.print(b); find = b.get(SZ/2); // Must use the Comparator to search, also: loc = Collections.binarySearch(b, find, ac); System.out.println("Location of " + find + " = " + loc); } } ///:~ ``` ⑨：在本書寫作時，已宣布了一個新的`Collections.stableSort()`，可用它進行合并式排序，但還沒有它的測試版問世。這些方法的用法與在`Arrays`中的用法是完全一致的，只是用一個列表代替了數組。 `TreeMap`也必須根據`Comparable`或者`Comparator`對自己的對象進行排序。 ## 8.7.8 實用工具 `Collections`類中含有其他大量有用的實用工具： ``` enumeration(Collection) Produces an old-style Enumeration for the argument. max(Collection) min(Collection) Produces the maximum or minimum element in the argument using the natural comparison method of the objects in the Collection. max(Collection, Comparator) min(Collection, Comparator) Produces the maximum or minimum element in the Collection using the Comparator. nCopies(int n, Object o) Returns an immutable List of size n whose handles all point to o. subList(List, int min, int max) Returns a new List backed by the specified argument List that is a window into that argument with indexes starting at min and stopping just before max. ``` + `enumeration(Collection)` 為參數產生原始風格的`Enumeration`（枚舉） + `max(Collection)`，`min(Collection)` 在參數中用集合內對象的自然比較方法產生最大或最小元素 + `max(Collection,Comparator)`，`min(Collection,Comparator)` 在集合內用比較器產生最大或最小元素 + `nCopies(int n, Object o)` 返回長度為`n`的一個不可變列表，它的所有引用均指向`o` + `subList(List,int min,int max) `返回由指定參數列表后推得到的一個新列表。可將這個列表想象成一個“窗口”，它自索引為`min`的地方開始，正好結束于`max`的前面注意`min()`和`max()`都是隨同`Collection`對象工作的，而非隨同`List`，所以不必擔心`Collection`是否需要排序（就象早先指出的那樣，在執行一次`binarySearch()`——即二進制搜索——之前，必須對一個`List`或者一個數組執行`sort()`）。 (1) 使`Collection`或`Map`不可修改通常，創建`Collection`或`Map`的一個“只讀”版本顯得更有利一些。`Collections`類允許我們達到這個目標，方法是將原始容器傳遞進入一個方法，并令其傳回一個只讀版本。這個方法共有四種變化形式，分別用于`Collection`（如果不想把集合當作一種更特殊的類型對待）、`List`、`Set`以及`Map`。下面這個例子演示了為它們分別構建只讀版本的正確方法： ``` //: ReadOnly.java // Using the Collections.unmodifiable methods package c08.newcollections; import java.util.*; public class ReadOnly { public static void main(String[] args) { Collection c = new ArrayList(); Collection1.fill(c); // Insert useful data c = Collections.unmodifiableCollection(c); Collection1.print(c); // Reading is OK //! c.add("one"); // Can't change it List a = new ArrayList(); Collection1.fill(a); a = Collections.unmodifiableList(a); ListIterator lit = a.listIterator(); System.out.println(lit.next()); // Reading OK //! lit.add("one"); // Can't change it Set s = new HashSet(); Collection1.fill(s); s = Collections.unmodifiableSet(s); Collection1.print(s); // Reading OK //! s.add("one"); // Can't change it Map m = new HashMap(); Map1.fill(m, Map1.testData1); m = Collections.unmodifiableMap(m); Map1.print(m); // Reading OK //! m.put("Ralph", "Howdy!"); } } ///:~ ``` 對于每種情況，在將其正式變為只讀以前，都必須用有有效的數據填充容器。一旦載入成功，最佳的做法就是用“不可修改”調用產生的引用替換現有的引用。這樣做可有效避免將其變成不可修改后不慎改變其中的內容。在另一方面，該工具也允許我們在一個類中將能夠修改的容器保持為`private`狀態，并可從一個方法調用中返回指向那個容器的一個只讀引用。這樣一來，雖然我們可在類里修改它，但其他任何人都只能讀。為特定類型調用“不可修改”的方法不會造成編譯期間的檢查，但一旦發生任何變化，對修改特定容器的方法的調用便會產生一個`UnsupportedOperationException`異常。 (2) `Collection`或`Map`的同步 `synchronized`關鍵字是“多線程”機制一個非常重要的部分。我們到第14章才會對這一機制作深入的探討。在這兒，大家只需注意到`Collections`類提供了對整個容器進行自動同步的一種途徑。它的語法與“不可修改”的方法是類似的： ``` //: Synchronization.java // Using the Collections.synchronized methods package c08.newcollections; import java.util.*; public class Synchronization { public static void main(String[] args) { Collection c = Collections.synchronizedCollection( new ArrayList()); List list = Collections.synchronizedList( new ArrayList()); Set s = Collections.synchronizedSet( new HashSet()); Map m = Collections.synchronizedMap( new HashMap()); } } ///:~ ``` 在這種情況下，我們通過適當的“同步”方法直接傳遞新容器；這樣做可避免不慎暴露出未同步的版本。新集合也提供了能防止多個進程同時修改一個容器內容的機制。若在一個容器里迭代，同時另一些進程介入，并在那個容器中插入、刪除或修改一個對象，便會面臨發生沖突的危險。我們可能已傳遞了那個對象，可能它位位于我們前面，可能容器的大小在我們調用`size()`后已發生了收縮——我們面臨各種各樣可能的危險。針對這個問題，新的集合庫集成了一套解決的機制，能查出除我們的進程自己需要負責的之外的、對容器的其他任何修改。若探測到有其他方面也準備修改容器，便會立即產生一個`ConcurrentModificationException`（并發修改異常）。我們將這一機制稱為“立即失敗”——它并不用更復雜的算法在“以后”偵測問題，而是“立即”產生異常。