Java中的Hashtable

2019-11-18 13:22:22

字體：大中小

來源：轉載

供稿：網友

　　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，而且就在這里進行，那么要做的全部事情只是填充位于Dictionary內的所有方法（而且必須覆蓋所有方法，因為它們——除構建器外——都是抽象的）。
　　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.

上一篇：再論枚舉器

下一篇：使用Collections