集合的類型

V e c t o r

崩潰 Java
Java 標(biāo)準(zhǔn)集合里包含了 toString()方法，所以它們能生成自己的 String 表達(dá)方式，包括它們?nèi)菁{的對象。
例如在 Vector 中， toString()會在 Vector 的各個元素中步進(jìn)和遍歷，并為每個元素調(diào)用 toString()。假定我們現(xiàn)在想打印出自己類的地址。看起來似乎簡單地引用 this 即可（特別是 C++程序員有這樣做的傾向）：

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);} }

此時發(fā)生的是字串的自動類型轉(zhuǎn)換。當(dāng)我們使用下述語句時：
“CrashJava address: ” + this
編譯器就在一個字串后面發(fā)現(xiàn)了一個“ +”以及好象并非字串的其他東西，所以它會試圖將 this 轉(zhuǎn)換成一個字串。轉(zhuǎn)換時調(diào)用的是 toString()，后者會產(chǎn)生一個遞歸調(diào)用。若在一個 Vector 內(nèi)出現(xiàn)這種事情，看起來堆棧就會溢出，同時違例控制機(jī)制根本沒有機(jī)會作出響應(yīng)。
若確實(shí)想在這種情況下打印出對象的地址，解決方案就是調(diào)用 Object 的 toString 方法。此時就不必加入this，只需使用 super.toString()。當(dāng)然，采取這種做法也有一個前提：我們必須從 Object 直接繼承，或者沒有一個父類覆蓋了 toString 方法。

B i t S e t

BitSet 實(shí)際是由“ 二進(jìn)制位”構(gòu)成的一個 Vector。如果希望高效率地保存大量“開－關(guān)”信息，就應(yīng)使用BitSet。它只有從尺寸的角度看才有意義；如果希望的高效率的訪問，那么它的速度會比使用一些固有類型的數(shù)組慢一些。
BitSet 的最小長度是一個長整數(shù)（ Long）的長度： 64 位。這意味著假如我們準(zhǔn)備保存比這更小的數(shù)據(jù)，如 8 位數(shù)據(jù)，那么 BitSet 就顯得浪費(fèi)了。所以最好創(chuàng)建自己的類，用它容納自己的標(biāo)志位。

S t a c k

Stack 有時也可以稱為“后入先出”（ LIFO）集合。換言之，我們在堆棧里最后“壓入”的東西將是以后第
一個“彈出”的。和其他所有 Java 集合一樣，我們壓入和彈出的都是“對象”，所以必須對自己彈出的東西
進(jìn)行“造型”。
下面是一個簡單的堆棧示例，它能讀入數(shù)組的每一行，同時將其作為字串壓入堆棧。

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 數(shù)組的每一行都通過 push()繼承進(jìn)入堆棧，稍后用 pop()從堆棧的頂部將其取出。要聲明的一點(diǎn)是，Vector 操作亦可針對 Stack 對象進(jìn)行。這可能是由繼承的特質(zhì)決定的—— Stack“屬于”一種 Vector。因此，能對 Vector 進(jìn)行的操作亦可針對 Stack 進(jìn)行，例如 elementAt()方法

H a s h t a b l e

Vector 允許我們用一個數(shù)字從一系列對象中作出選擇，所以它實(shí)際是將數(shù)字同對象關(guān)聯(lián)起來了。
但假如我們想根據(jù)其他標(biāo)準(zhǔn)選擇一系列對象呢？堆棧就是這樣的一個例子：它的選擇標(biāo)準(zhǔn)是“最后壓入堆棧的東西”。
這種“從一系列對象中選擇”的概念亦可叫作一個“映射”、“字典”或者“關(guān)聯(lián)數(shù)組”。從概念上講，它看起來象一個 Vector，但卻不是通過數(shù)字來查找對象，而是用另一個對象來查找它們！這通常都屬于一個程序中的重要進(jìn)程。
在 Java 中，這個概念具體反映到抽象類 Dictionary 身上。該類的接口是非常直觀的 size()告訴我們其中包含了多少元素； isEmpty()判斷是否包含了元素（是則為 true）； put(Object key, Object value)添加一個值（我們希望的東西），并將其同一個鍵關(guān)聯(lián)起來（想用于搜索它的東西）； get(Object key)獲得與某個鍵對應(yīng)的值；而 remove(Object Key)用于從列表中刪除“鍵－值”對。還可以使用枚舉技術(shù)： keys()產(chǎn)生對鍵的一個枚舉（ Enumeration）；而 elements()產(chǎn)生對所有值的一個枚舉。這便是一個 Dict ionary（字典）的全部。

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 的定義中，我們注意到的第一個問題是它“擴(kuò)展”了字典。這意味著 AssocArray 屬于Dictionary 的一種類型，所以可對其發(fā)出與 Dictionary 一樣的請求。如果想生成自己的 Dictionary，而且就在這里進(jìn)行，那么要做的全部事情只是填充位于 Dictionary 內(nèi)的所有方法（而且必須覆蓋所有方法，因?yàn)?
它們—— 除構(gòu)建器外—— 都是抽象的）。
標(biāo)準(zhǔn) Java 庫只包含 Dictionary 的一個變種，名為 Hashtable（散列表，注釋③）。 Java 的散列表具有與AssocArray 相同的接口（因?yàn)閮烧叨际菑?Dictionary 繼承來的）。但有一個方面卻反映出了差別：執(zhí)行效率。若仔細(xì)想想必須為一個 get()做的事情，就會發(fā)現(xiàn)在一個 Vector 里搜索鍵的速度要慢得多。但此時用散列表卻可以加快不少速度。不必用冗長的線性搜索技術(shù)來查找一個鍵，而是用一個特殊的值，名為“散列碼”。散列碼可以獲取對象中的信息，然后將其轉(zhuǎn)換成那個對象“相對唯一”的整數(shù)（ int）。所有對象都有一個散列碼，而 hashCode()是根類 Object 的一個方法。 Hashtable 獲取對象的 hashCode()，然后用它快速查找鍵。

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++;elseht.put(r, new Counter());}System.out.println(ht);} }

• 創(chuàng)建“關(guān)鍵”類
  但在使用散列表的時候，一旦我們創(chuàng)建自己的類作為鍵使
  用，就會遇到一個很常見的問題。例如，假設(shè)一套天氣預(yù)報(bào)系統(tǒng)將Groundhog（土拔鼠）對象匹配成Prediction（預(yù)報(bào)） 。這看起來非常直觀：我們創(chuàng)建兩個類，然后將Groundhog 作為鍵使用，而將Prediction 作為值使用。如下所示：

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!";elsereturn "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 是從通用的 Object 根類繼承的（若當(dāng)初未指
定基礎(chǔ)類，則所有類最終都是從 Object 繼承的）。事實(shí)上是用 Object 的 hashCode()方法生成每個對象的散列碼，而且默認(rèn)情況下只使用它的對象的地址。所以， Groundhog(3)的第一個實(shí)例并不會產(chǎn)生與Groundhog(3)第二個實(shí)例相等的散列碼，而我們用第二個實(shí)例進(jìn)行檢索
或許認(rèn)為此時要做的全部事情就是正確地覆蓋 hashCode()。但這樣做依然行不能，除非再做另一件事情：覆蓋也屬于 Object 一部分的 equals()。當(dāng)散列表試圖判斷我們的鍵是否等于表內(nèi)的某個鍵時，就會用到這個方法。同樣地，默認(rèn)的 Object.equals()只是簡單地比較對象地址，所以一個 Groundhog(3)并不等于
另一個 Groundhog(3)。
因此，為了在散列表中將自己的類作為鍵使用，必須同時覆蓋 hashCode()和 equals()，就象下面展示的那樣：

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!";elsereturn "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));} }

Groundhog2.hashCode()將土拔鼠號碼作為一個標(biāo)識符返回（在這個例子中，程序員需要保證沒有兩個土拔鼠用同樣的 ID 號碼并存）。為了返回一個獨(dú)一無二的標(biāo)識符，并不需要 hashCode()， equals()方法必須能夠嚴(yán)格判斷兩個對象是否相等。
equals()方法要進(jìn)行兩種檢查：檢查對象是否為 null；若不為 null ，則繼續(xù)檢查是否為 Groundhog2 的一個實(shí)例（要用到 instanceof 關(guān)鍵字）。即使為了繼續(xù)執(zhí)行 equals()，它也應(yīng)該是一個Groundhog2。正如大家看到的那樣，這種比較建立在實(shí)際 ghNumber 的基礎(chǔ)上。這一次一旦我們運(yùn)行程序，就會看到它終于產(chǎn)生了正確的輸出（許多 Java 庫的類都覆蓋了 hashcode() 和 equals()方法，以便與自己提供的內(nèi)容適應(yīng)）。

再論枚舉器

將穿越一個序列的操作與那個序列的基礎(chǔ)結(jié)構(gòu)分隔開。在下面的例子里， PrintData 類用一個 Enumeration 在一個序列中移動，并為每個對象都調(diào)用toString()方法。此時創(chuàng)建了兩個不同類型的集合：一個 Vector 和一個 Hashtable。并且在它們里面分別填
充 Mouse 和 Hamster 對象，由于 Enumeration 隱藏了基層集合的結(jié)構(gòu)，所以PrintData 不知道或者不關(guān)心 Enumeration 來自于什么類型的集合：

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 類這一事實(shí)，所以它調(diào)用了 toString()。但在
解決自己的實(shí)際問題時，經(jīng)常都要保證自己的 Enumeration 穿越某種特定類型的集合。例如，可能要求集合
中的所有元素都是一個 Shape（幾何形狀），并含有 draw()方法。若出現(xiàn)這種情況，必須從
Enumeration.nextElement()返回的 Object 進(jìn)行下溯造型，以便產(chǎn)生一個 Shape。

排序

編寫通用的排序代碼時，面臨的一個問題是必須根據(jù)對象的實(shí)際類型來執(zhí)行比較運(yùn)算，從而實(shí)現(xiàn)正確的排序。當(dāng)然，一個辦法是為每種不同的類型都寫一個不同的排序方法。然而，應(yīng)認(rèn)識到假若這樣做，以后增加新類型時便不易實(shí)現(xiàn)代碼的重復(fù)利用。
程序設(shè)計(jì)一個主要的目標(biāo)就是“將發(fā)生變化的東西同保持不變的東西分隔開”。在這里，保持不變的代碼是通用的排序算法，而每次使用時都要變化的是對象的實(shí)際比較方法。因此，我們不可將比較代碼“硬編碼”到多個不同的排序例程內(nèi)，而是采用“回調(diào)”技術(shù)。
利用回調(diào)，經(jīng)常發(fā)生變化的那部分代碼會封裝到它自己的類內(nèi)，而總是保持相同的代碼則“回調(diào)”發(fā)生變化的代碼。這樣一來，不同的對象就可以表達(dá)不同的比較方式，同時向它們傳遞相同的排序代碼。
下面這個“接口”（ Interface）展示了如何比較兩個對象，它將那些“要發(fā)生變化的東西”封裝在內(nèi)：

interface Compare { boolean lessThan(Object lhs, Object rhs); boolean lessThanOrEqual(Object lhs, Object rhs); }

對這兩種方法來說， lhs 代表本次比較中的“左手”對象，而 rhs 代表“右手”對象。
可創(chuàng)建 Vector 的一個子類，通過 Compare 實(shí)現(xiàn)“快速排序”。對于這種算法，包括它的速度以及原理等等

public class SortVector extends Vector {private Compare compare; // To hold the callbackpublic SortVector(Compare comp) {compare = comp;}public void sort() {quickSort(0, size() - 1);}private void quickSort(int left, int right) {if (right > left) {Object o1 = elementAt(right);int i = left - 1;int j = right;while (true) {while (compare.lessThan(elementAt(++i), o1));while (j > 0)if (compare.lessThanOrEqual(elementAt(--j), o1))break; // out of whileif (i >= j)break;swap(i, j);}swap(i, right);quickSort(left, i - 1);quickSort(i + 1, right);}}private void swap(int loc1, int loc2) {Object tmp = elementAt(loc1);setElementAt(elementAt(loc2), loc1);setElementAt(tmp, loc2);} }

為使用 SortVector，必須創(chuàng)建一個類，令其為我們準(zhǔn)備排序的對象實(shí)現(xiàn) Compare。此時內(nèi)部類并不顯得特別重要，但對于代碼的組織卻是有益的。下面是針對 String 對象的一個例子

public class StringSortTest {static class StringCompare implements Compare {public boolean lessThan(Object l, Object r) {return ((String) l).toLowerCase().compareTo(((String) r).toLowerCase()) < 0;}public boolean lessThanOrEqual(Object l, Object r) {return ((String) l).toLowerCase().compareTo(((String) r).toLowerCase()) <= 0;}}public static void main(String[] args) {SortVector sv = new SortVector(new StringCompare());sv.addElement("d");sv.addElement("A");sv.addElement("C");sv.addElement("c");sv.addElement("b");sv.addElement("B");sv.addElement("D");sv.addElement("a");sv.sort();Enumeration e = sv.elements();while (e.hasMoreElements())System.out.println(e.nextElement());} }

一旦設(shè)置好框架，就可以非常方便地重復(fù)使用象這樣的一個設(shè)計(jì)—— 只需簡單地寫一個類，將“需要發(fā)生變化”的東西封裝進(jìn)去，然后將一個對象傳給SortVector 即可
繼承（ extends）在這兒用于創(chuàng)建一種新類型的 Vector—— 也就是說， SortVector 屬于一種 Vector，并帶有一些附加的功能。繼承在這里可發(fā)揮很大的作用，但了帶來了問題。它使一些方法具有了final 屬性，所以不能覆蓋它們。如果想創(chuàng)建一個排好序的 Vector，令其只接收和生成 String 對象，就會遇到麻煩。因?yàn)?addElement()和 elementAt()都具有 final 屬性，而且它們都是我們必須覆蓋的方法，否則便無法實(shí)現(xiàn)只能接收和產(chǎn)生 String 對象。
但在另一方面，請考慮采用“合成”方法：將一個對象置入一個新類的內(nèi)部。此時，不是改寫上述代碼來達(dá)到這個目的，而是在新類里簡單地使用一個 SortVector。在這種情況下，用于實(shí)現(xiàn) Compare 接口的內(nèi)部類就可以“匿名”地創(chuàng)建

import java.util.*;public class StrSortVector {private SortVector v = new SortVector(// Anonymous inner class:new Compare() {public boolean lessThan(Object l, Object r) {return ((String) l).toLowerCase().compareTo(((String) r).toLowerCase()) < 0;}public boolean lessThanOrEqual(Object l, Object r) {return ((String) l).toLowerCase().compareTo(((String) r).toLowerCase()) <= 0;}});private boolean sorted = false;public void addElement(String s) {v.addElement(s);sorted = false;}public String elementAt(int index) { if(!sorted) { v.sort();232 sorted = true; } return (String)v.elementAt(index); }public Enumeration elements() {if (!sorted) {v.sort();sorted = true;}return v.elements();}// Test it:public static void main(String[] args) {StrSortVector sv = new StrSortVector();sv.addElement("d");sv.addElement("A");sv.addElement("C");sv.addElement("c");sv.addElement("b");sv.addElement("B");sv.addElement("D");sv.addElement("a");Enumeration e = sv.elements();while (e.hasMoreElements())System.out.println(e.nextElement());} }

總結(jié)

以上是生活随笔為你收集整理的java基础系列：集合基础（2）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。