8.4 集合的類型 · Java 編程思想

# 8.4 集合的類型標準Java 1.0和1.1庫配套提供了非常少的一系列集合類。但對于自己的大多數編程要求，它們基本上都能勝任。正如大家到本章末尾會看到的，Java 1.2提供的是一套重新設計過的大型集合庫。 ## 8.4.1 `Vector` `Vector`的用法很簡單，這已在前面的例子中得到了證明。盡管我們大多數時候只需用`addElement()`插入對象，用`elementAt()`一次提取一個對象，并用`elements()`獲得對序列的一個“枚舉”。但仍有其他一系列方法是非常有用的。同我們對于Java庫慣常的做法一樣，在這里并不使用或講述所有這些方法。但請務必閱讀相應的電子文檔，對它們的工作有一個大概的認識。 (1) 崩潰Java Java標準集合里包含了`toString()`方法，所以它們能生成自己的`String`表達方式，包括它們容納的對象。例如在`Vector`中，`toString()`會在`Vector`的各個元素中步進和遍歷，并為每個元素調用`toString()`。假定我們現在想打印出自己類的地址。看起來似乎簡單地引用`this`即可（特別是C++程序員有這樣做的傾向）： ``` //: CrashJava.java // One way to crash Java import java.util.*; public class CrashJava { public String toString() { return "CrashJava address: " + this + "\n"; } public static void main(String[] args) { Vector v = new Vector(); for(int i = 0; i < 10; i++) v.addElement(new CrashJava()); System.out.println(v); } } ///:~ ``` 若只是簡單地創建一個`CrashJava`對象，并將其打印出來，就會得到無窮無盡的一系列異常錯誤。然而，假如將`CrashJava`對象置入一個`Vector`，并象這里演示的那樣打印`Vector`，就不會出現什么錯誤提示，甚至連一個異常都不會出現。此時Java只是簡單地崩潰（但至少它沒有崩潰我的操作系統）。這已在Java 1.1中測試通過。此時發生的是字符串的自動類型轉換。當我們使用下述語句時： ``` "CrashJava address: " + this ``` 編譯器就在一個字符串后面發現了一個`+`以及好象并非字符串的其他東西，所以它會試圖將`this`轉換成一個字符串。轉換時調用的是`toString()`，后者會產生一個遞歸調用。若在一個`Vector`內出現這種事情，看起來棧就會溢出，同時異常控制機制根本沒有機會作出響應。若確實想在這種情況下打印出對象的地址，解決方案就是調用`Object`的`toString`方法。此時就不必加入`this`，只需使用`super.toString()`。當然，采取這種做法也有一個前提：我們必須從`Object`直接繼承，或者沒有一個父類覆蓋了`toString`方法。 ## 8.4.2 `BitSet` `BitSet`實際是由“二進制位”構成的一個`Vector`。如果希望高效率地保存大量“開－關”信息，就應使用`BitSet`。它只有從尺寸的角度看才有意義；如果希望的高效率的訪問，那么它的速度會比使用一些固有類型的數組慢一些。此外，`BitSet`的最小長度是一個長整數（`Long`）的長度：64位。這意味著假如我們準備保存比這更小的數據，如8位數據，那么`BitSet`就顯得浪費了。所以最好創建自己的類，用它容納自己的標志位。在一個普通的`Vector`中，隨我們加入越來越多的元素，集合也會自我膨脹。在某種程度上，`BitSet`也不例外。也就是說，它有時會自行擴展，有時則不然。而且Java的1.0版本似乎在這方面做得最糟，它的`BitSet`表現十分差強人意（Java1.1已改正了這個問題）。下面這個例子展示了`BitSet`是如何運作的，同時演示了1.0版本的錯誤： ``` //: Bits.java // Demonstration of BitSet import java.util.*; public class Bits { public static void main(String[] args) { Random rand = new Random(); // Take the LSB of nextInt(): byte bt = (byte)rand.nextInt(); BitSet bb = new BitSet(); for(int i = 7; i >=0; i--) if(((1 << i) & bt) != 0) bb.set(i); else bb.clear(i); System.out.println("byte value: " + bt); printBitSet(bb); short st = (short)rand.nextInt(); BitSet bs = new BitSet(); for(int i = 15; i >=0; i--) if(((1 << i) & st) != 0) bs.set(i); else bs.clear(i); System.out.println("short value: " + st); printBitSet(bs); int it = rand.nextInt(); BitSet bi = new BitSet(); for(int i = 31; i >=0; i--) if(((1 << i) & it) != 0) bi.set(i); else bi.clear(i); System.out.println("int value: " + it); printBitSet(bi); // Test bitsets >= 64 bits: BitSet b127 = new BitSet(); b127.set(127); System.out.println("set bit 127: " + b127); BitSet b255 = new BitSet(65); b255.set(255); System.out.println("set bit 255: " + b255); BitSet b1023 = new BitSet(512); // Without the following, an exception is thrown // in the Java 1.0 implementation of BitSet: // b1023.set(1023); b1023.set(1024); System.out.println("set bit 1023: " + b1023); } static void printBitSet(BitSet b) { System.out.println("bits: " + b); String bbits = new String(); for(int j = 0; j < b.size() ; j++) bbits += (b.get(j) ? "1" : "0"); System.out.println("bit pattern: " + bbits); } } ///:~ ``` 隨機數字生成器用于創建一個隨機的`byte`、`short`和`int`。每一個都會轉換成`BitSet`內相應的位模型。此時一切都很正常，因為`BitSet`是64位的，所以它們都不會造成最終尺寸的增大。但在Java 1.0中，一旦`BitSet`大于64位，就會出現一些令人迷惑不解的行為。假如我們設置一個只比`BitSet`當前分配存儲空間大出1的一個位，它能夠正常地擴展。但一旦試圖在更高的位置設置位，同時不先接觸邊界，就會得到一個惱人的異常。這正是由于`BitSet`在Java 1.0里不能正確擴展造成的。本例創建了一個512位的`BitSet`。構造器分配的存儲空間是位數的兩倍。所以假如設置位1024或更高的位，同時沒有先設置位1023，就會在Java 1.0里得到一個異常。但幸運的是，這個問題已在Java 1.1得到了改正。所以如果是為Java 1.0寫代碼，請盡量避免使用`BitSet`。 ## 8.4.3 `Stack` `Stack`有時也可以稱為“后入先出”（LIFO）集合。換言之，我們在棧里最后“壓入”的東西將是以后第一個“彈出”的。和其他所有Java集合一樣，我們壓入和彈出的都是“對象”，所以必須對自己彈出的東西進行“轉換”。一種很少見的做法是拒絕使用`Vector`作為一個`Stack`的基本構成元素，而是從`Vector`里“繼承”一個`Stack`。這樣一來，它就擁有了一個`Vector`的所有特征及行為，另外加上一些額外的`Stack`行為。很難判斷出設計者到底是明確想這樣做，還是屬于一種固有的設計。下面是一個簡單的棧示例，它能讀入數組的每一行，同時將其作為字符串壓入棧。 ``` //: Stacks.java // Demonstration of Stack Class import java.util.*; public class Stacks { static String[] months = { "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December" }; public static void main(String[] args) { Stack stk = new Stack(); for(int i = 0; i < months.length; i++) stk.push(months[i] + " "); System.out.println("stk = " + stk); // Treating a stack as a Vector: stk.addElement("The last line"); System.out.println( "element 5 = " + stk.elementAt(5)); System.out.println("popping elements:"); while(!stk.empty()) System.out.println(stk.pop()); } } ///:~ ``` `months`數組的每一行都通過`push()`繼承進入棧，稍后用`pop()`從棧的頂部將其取出。要聲明的一點是，`Vector`操作亦可針對Stack對象進行。這可能是由繼承的特質決定的——`Stack`“屬于”一種`Vector`。因此，能對`Vector`進行的操作亦可針對`Stack`進行，例如`elementAt()`方法。 ## 8.4.4 `Hashtable` `Vector`允許我們用一個數字從一系列對象中作出選擇，所以它實際是將數字同對象關聯起來了。但假如我們想根據其他標準選擇一系列對象呢？棧就是這樣的一個例子：它的選擇標準是“最后壓入棧的東西”。這種“從一系列對象中選擇”的概念亦可叫作一個“映射”、“字典”或者“關聯數組”。從概念上講，它看起來象一個`Vector`，但卻不是通過數字來查找對象，而是用另一個對象來查找它們！這通常都屬于一個程序中的重要進程。在Java中，這個概念具體反映到抽象類`Dictionary`身上。該類的接口是非常直觀的`size()`告訴我們其中包含了多少元素；`isEmpty()`判斷是否包含了元素（是則為`true`）；`put(Object key, Object value)`添加一個值（我們希望的東西），并將其同一個鍵關聯起來（想用于搜索它的東西）；`get(Object key)`獲得與某個鍵對應的值；而`remove(Object Key)`用于從列表中刪除“鍵－值”對。還可以使用枚舉技術：`keys()`產生對鍵的一個枚舉（`Enumeration`）；而`elements()`產生對所有值的一個枚舉。這便是一個`Dictionary`（字典）的全部。 `Dictionary`的實現過程并不麻煩。下面列出一種簡單的方法，它使用了兩個`Vector`，一個用于容納鍵，另一個用來容納值： ``` //: AssocArray.java // Simple version of a Dictionary import java.util.*; public class AssocArray extends Dictionary { private Vector keys = new Vector(); private Vector values = new Vector(); public int size() { return keys.size(); } public boolean isEmpty() { return keys.isEmpty(); } public Object put(Object key, Object value) { keys.addElement(key); values.addElement(value); return key; } public Object get(Object key) { int index = keys.indexOf(key); // indexOf() Returns -1 if key not found: if(index == -1) return null; return values.elementAt(index); } public Object remove(Object key) { int index = keys.indexOf(key); if(index == -1) return null; keys.removeElementAt(index); Object returnval = values.elementAt(index); values.removeElementAt(index); return returnval; } public Enumeration keys() { return keys.elements(); } public Enumeration elements() { return values.elements(); } // Test it: public static void main(String[] args) { AssocArray aa = new AssocArray(); for(char c = 'a'; c <= 'z'; c++) aa.put(String.valueOf(c), String.valueOf(c) .toUpperCase()); char[] ca = { 'a', 'e', 'i', 'o', 'u' }; for(int i = 0; i < ca.length; i++) System.out.println("Uppercase: " + aa.get(String.valueOf(ca[i]))); } } ///:~ ``` 在對`AssocArray`的定義中，我們注意到的第一個問題是它“擴展”了字典。這意味著`AssocArray`屬于`Dictionary`的一種類型，所以可對其發出與`Dictionary`一樣的請求。如果想生成自己的`Dictionary`，而且就在這里進行，那么要做的全部事情只是填充位于`Dictionar`y內的所有方法（而且必須覆蓋所有方法，因為它們——除構造器外——都是抽象的）。 `Vector key`和`value`通過一個標準索引編號鏈接起來。也就是說，如果用`roof`的一個鍵以及`blue`的一個值調用`put()`——假定我們準備將一個房子的各部分與它們的油漆顏色關聯起來，而且`AssocArray`里已有100個元素，那么`roof`就會有101個鍵元素，而`blue`有101個值元素。而且要注意一下`get()`，假如我們作為鍵傳遞`roof`，它就會產生與`keys.index.Of()`的索引編號，然后用那個索引編號生成相關的值向量內的值。 `main()`中進行的測試是非常簡單的；它只是將小寫字符轉換成大寫字符，這顯然可用更有效的方式進行。但它向我們揭示出了`AssocArray`的強大功能。標準Java庫只包含`Dictionary`的一個變種，名為`Hashtable`（散列表，注釋③）。Java的散列表具有與`AssocArray`相同的接口（因為兩者都是從`Dictionary`繼承來的）。但有一個方面卻反映出了差別：執行效率。若仔細想想必須為一個`get()`做的事情，就會發現在一個`Vector`里搜索鍵的速度要慢得多。但此時用散列表卻可以加快不少速度。不必用冗長的線性搜索技術來查找一個鍵，而是用一個特殊的值，名為“散列碼”。散列碼可以獲取對象中的信息，然后將其轉換成那個對象“相對唯一”的整數（`int`）。所有對象都有一個散列碼，而`hashCode()`是根類`Object`的一個方法。`Hashtable`獲取對象的`hashCode()`，然后用它快速查找鍵。這樣可使性能得到大幅度提升（④）。散列表的具體工作原理已超出了本書的范圍（⑤）——大家只需要知道散列表是一種快速的“字典”（`Dictionary`）即可，而字典是一種非常有用的工具。 ③：如計劃使用RMI（在第15章詳述），應注意將遠程對象置入散列表時會遇到一個問題（參閱《Core Java》，作者Conrell和Horstmann，Prentice-Hall 1997年出版） ④：如這種速度的提升仍然不能滿足你對性能的要求，甚至可以編寫自己的散列表例程，從而進一步加快表格的檢索過程。這樣做可避免在與`Object`之間進行轉換的時間延誤，也可以避開由Java類庫散列表例程內建的同步過程。 ⑤：我的知道的最佳參考讀物是《Practical Algorithms for Programmers》，作者為Andrew Binstock和John Rex，Addison-Wesley 1995年出版。作為應用散列表的一個例子，可考慮用一個程序來檢驗Java的`Math.random()`方法的隨機性到底如何。在理想情況下，它應該產生一系列完美的隨機分布數字。但為了驗證這一點，我們需要生成數量眾多的隨機數字，然后計算落在不同范圍內的數字多少。散列表可以極大簡化這一工作，因為它能將對象同對象關聯起來（此時是將`Math.random()`生成的值同那些值出現的次數關聯起來）。如下所示： ``` //: Statistics.java // Simple demonstration of Hashtable import java.util.*; class Counter { int i = 1; public String toString() { return Integer.toString(i); } } class Statistics { public static void main(String[] args) { Hashtable ht = new Hashtable(); for(int i = 0; i < 10000; i++) { // Produce a number between 0 and 20: Integer r = new Integer((int)(Math.random() * 20)); if(ht.containsKey(r)) ((Counter)ht.get(r)).i++; else ht.put(r, new Counter()); } System.out.println(ht); } } ///:~ ``` 在`main()`中，每次產生一個隨機數字，它都會封裝到一個`Integer`對象里，使引用能夠隨同散列表一起使用（不可對一個集合使用基本數據類型，只能使用對象引用）。`containKey()`方法檢查這個鍵是否已經在集合里（也就是說，那個數字以前發現過嗎？）若已在集合里，則`get()`方法獲得那個鍵關聯的值，此時是一個`Counter`（計數器）對象。計數器內的值`i`隨后會增加1，表明這個特定的隨機數字又出現了一次。假如鍵以前尚未發現過，那么方法`put()`仍然會在散列表內置入一個新的“鍵－值”對。在創建之初，`Counter`會自己的變量`i`自動初始化為1，它標志著該隨機數字的第一次出現。為顯示散列表，只需把它簡單地打印出來即可。`Hashtable toString()`方法能遍歷所有鍵－值對，并為每一對都調用`toString()`。`Integer toString()`是事先定義好的，可看到計數器使用的`toString`。一次運行的結果（添加了一些換行）如下： ``` {19=526, 18=533, 17=460, 16=513, 15=521, 14=495, 13=512, 12=483, 11=488, 10=487, 9=514, 8=523, 7=497, 6=487, 5=480, 4=489, 3=509, 2=503, 1=475, 0=505} ``` 大家或許會對`Counter`類是否必要感到疑惑，它看起來似乎根本沒有封裝類`Integer`的功能。為什么不用`int`或`Integer`呢？事實上，由于所有集合能容納的僅有對象引用，所以根本不可以使用整數。學過集合后，封裝類的概念對大家來說就可能更容易理解了，因為不可以將任何基本數據類型置入集合里。然而，我們對Java包裝器能做的唯一事情就是將其初始化成一個特定的值，然后讀取那個值。也就是說，一旦包裝器對象已經創建，就沒有辦法改變一個值。這使得`Integer`包裝器對解決我們的問題毫無意義，所以不得不創建一個新類，用它來滿足自己的要求。 (1) 創建“關鍵”類在前面的例子里，我們用一個標準庫的類（`Integer`）作為`Hashtable`的一個鍵使用。作為一個鍵，它能很好地工作，因為它已經具備正確運行的所有條件。但在使用散列表的時候，一旦我們創建自己的類作為鍵使用，就會遇到一個很常見的問題。例如，假設一套天氣預報系統將`Groundhog`（土拔鼠）對象匹配成`Prediction`（預報）。這看起來非常直觀：我們創建兩個類，然后將`Groundhog`作為鍵使用，而將`Prediction`作為值使用。如下所示： ``` //: SpringDetector.java // Looks plausible, but doesn't work right. import java.util.*; class Groundhog { int ghNumber; Groundhog(int n) { ghNumber = n; } } class Prediction { boolean shadow = Math.random() > 0.5; public String toString() { if(shadow) return "Six more weeks of Winter!"; else return "Early Spring!"; } } public class SpringDetector { public static void main(String[] args) { Hashtable ht = new Hashtable(); for(int i = 0; i < 10; i++) ht.put(new Groundhog(i), new Prediction()); System.out.println("ht = " + ht + "\n"); System.out.println( "Looking up prediction for groundhog #3:"); Groundhog gh = new Groundhog(3); if(ht.containsKey(gh)) System.out.println((Prediction)ht.get(gh)); } } ///:~ ``` 每個`Groundhog`都具有一個標識號碼，所以赤了在散列表中查找一個`Prediction`，只需指示它“告訴我與`Groundhog`號碼3相關的`Prediction`”。`Prediction`類包含了一個布爾值，用`Math.random()`進行初始化，以及一個`toString()`為我們解釋結果。在`main()`中，用`Groundhog`以及與它們相關的`Prediction`填充一個散列表。散列表被打印出來，以便我們看到它們確實已被填充。隨后，用標識號碼為3的一個`Groundhog`查找與`Groundhog #3`對應的預報。看起來似乎非常簡單，但實際是不可行的。問題在于`Groundhog`是從通用的`Object`根類繼承的（若當初未指定基類，則所有類最終都是從`Object`繼承的）。事實上是用`Object`的`hashCode()`方法生成每個對象的散列碼，而且默認情況下只使用它的對象的地址。所以，`Groundhog(3)`的第一個實例并不會產生與`Groundhog(3)`第二個實例相等的散列碼，而我們用第二個實例進行檢索。大家或許認為此時要做的全部事情就是正確地覆蓋`hashCode()`。但這樣做依然行不能，除非再做另一件事情：覆蓋也屬于`Object`一部分的`equals()`。當散列表試圖判斷我們的鍵是否等于表內的某個鍵時，就會用到這個方法。同樣地，默認的`Object.equals()`只是簡單地比較對象地址，所以一個`Groundhog(3)`并不等于另一個`Groundhog(3)`。因此，為了在散列表中將自己的類作為鍵使用，必須同時覆蓋`hashCode()`和`equals()`，就象下面展示的那樣： ``` //: SpringDetector2.java // If you create a class that's used as a key in // a Hashtable, you must override hashCode() // and equals(). import java.util.*; class Groundhog2 { int ghNumber; Groundhog2(int n) { ghNumber = n; } public int hashCode() { return ghNumber; } public boolean equals(Object o) { return (o instanceof Groundhog2) && (ghNumber == ((Groundhog2)o).ghNumber); } } public class SpringDetector2 { public static void main(String[] args) { Hashtable ht = new Hashtable(); for(int i = 0; i < 10; i++) ht.put(new Groundhog2(i),new Prediction()); System.out.println("ht = " + ht + "\n"); System.out.println( "Looking up prediction for groundhog #3:"); Groundhog2 gh = new Groundhog2(3); if(ht.containsKey(gh)) System.out.println((Prediction)ht.get(gh)); } } ///:~ ``` 注意這段代碼使用了來自前一個例子的`Prediction`，所以`SpringDetector.java`必須首先編譯，否則就會在試圖編譯`SpringDetector2.java`時得到一個編譯期錯誤。 `Groundhog2.hashCode()`將土拔鼠號碼作為一個標識符返回（在這個例子中，程序員需要保證沒有兩個土拔鼠用同樣的ID號碼并存）。為了返回一個獨一無二的標識符，并不需要`hashCode()`，`equals()`方法必須能夠嚴格判斷兩個對象是否相等。 `equals()`方法要進行兩種檢查：檢查對象是否為`null`；若不為`null`，則繼續檢查是否為`Groundhog2`的一個實例（要用到`instanceof`關鍵字，第11章會詳加論述）。即使為了繼續執行`equals()`，它也應該是一個`Groundhog2`。正如大家看到的那樣，這種比較建立在實際`ghNumber`的基礎上。這一次一旦我們運行程序，就會看到它終于產生了正確的輸出（許多Java庫的類都覆蓋了`hashcode()`和`equals()`方法，以便與自己提供的內容適應）。 (2) 屬性：`Hashtable`的一種類型在本書的第一個例子中，我們使用了一個名為`Properties`（屬性）的`Hashtable`類型。在那個例子中，下述程序行： ``` Properties p = System.getProperties(); p.list(System.out); ``` 調用了一個名為`getProperties()`的`static`方法，用于獲得一個特殊的`Properties`對象，對系統的某些特征進行描述。`list()`屬于`Properties`的一個方法，可將內容發給我們選擇的任何流式輸出。也有一個`save()`方法，可用它將屬性列表寫入一個文件，以便日后用`load()`方法讀取。盡管`Properties`類是從`Hashtable`繼承的，但它也包含了一個散列表，用于容納“默認”屬性的列表。所以假如沒有在主列表里找到一個屬性，就會自動搜索默認屬性。 `Properties`類亦可在我們的程序中使用（第17章的`ClassScanner.java`便是一例）。在Java庫的用戶文檔中，往往可以找到更多、更詳細的說明。 ## 8.4.5 再論枚舉器我們現在可以開始演示`Enumeration`（枚舉）的真正威力：將穿越一個序列的操作與那個序列的基礎結構分隔開。在下面的例子里，`PrintData`類用一個`Enumeration`在一個序列中移動，并為每個對象都調用`toString()`方法。此時創建了兩個不同類型的集合：一個`Vector`和一個`Hashtable`。并且在它們里面分別填充`Mouse`和`Hamster`對象（本章早些時候已定義了這些類；注意必須先編譯`HamsterMaze.java`和`WorksAnyway.java`，否則下面的程序不能編譯）。由于`Enumeration`隱藏了基層集合的結構，所以`PrintData`不知道或者不關心`Enumeration`來自于什么類型的集合： ``` //: Enumerators2.java // Revisiting Enumerations import java.util.*; class PrintData { static void print(Enumeration e) { while(e.hasMoreElements()) System.out.println( e.nextElement().toString()); } } class Enumerators2 { public static void main(String[] args) { Vector v = new Vector(); for(int i = 0; i < 5; i++) v.addElement(new Mouse(i)); Hashtable h = new Hashtable(); for(int i = 0; i < 5; i++) h.put(new Integer(i), new Hamster(i)); System.out.println("Vector"); PrintData.print(v.elements()); System.out.println("Hashtable"); PrintData.print(h.elements()); } } ///:~ ``` 注意`PrintData.print()`利用了這些集合中的對象屬于`Object`類這一事實，所以它調用了`toString()`。但在解決自己的實際問題時，經常都要保證自己的`Enumeration`穿越某種特定類型的集合。例如，可能要求集合中的所有元素都是一個Shape（幾何形狀），并含有`draw()`方法。若出現這種情況，必須從`Enumeration.nextElement()`返回的`Object`進行向下轉換，以便產生一個`Shape`。