Hashtables提供了一個很有用的方法可以使應用程序的性能達到最佳。

Hashtables（哈希表）在計算機領域中已不 是一個新概念了。它們是用來加快計算機的處理速度的，用當今的標準來處理，速度非常慢，而它們可以讓你在查詢許多數據條目時，很快地找到一個特殊的條目。 盡管現代的機器速度已快了幾千倍，但是為了得到應用程序的最佳性能，hashtables仍然是個很有用的方法。

設想一下，你有一個包含約一千條記錄的數據文件??比如一個小企業的客戶記錄還有一個程序，它把記錄讀到內存中進行處理。每個記錄包含一個唯一的五 位數的客戶ID號、客戶名字、地址、帳戶結余等等。假設記錄不是按客戶ID號順序分類的，所以，如果程序要將客戶號作為“key” 來查找一個特殊的客戶記錄，唯一的查找方法就是連續地搜索每個記錄。有時侯，它會很快找到你需要的記錄；但有時侯，在程序找到你需要的記錄前，它幾乎已搜 索到了最后一條記錄。如果要在1,000條記錄中搜索，那么查找任何一條記錄都需要程序平均查核500.5 ((1000 + 1 )/2)條記錄。如果你常需要查找數據，你應該需要一個更快的方法來找到一條記錄。

一種加快搜索的方法就是把記錄分成幾段，這樣，你就不用搜索一個很大的列表了，而是搜索幾個短的列表。對于我們數字式的客戶ID號，你可以建10個 列表??以0開頭的ID號組成一個列表，以1開頭的ID號組成一個列表，依此類推。那么要查找客戶ID號38016，你只需要搜索以3開頭的列表就行了。 如果有1,000條記錄，每個列表的平均長度為100 （1,000條記錄被分成10個列表），那么搜索一條記錄的平均比較次數就降到了約50（見圖1）。

當然，如果約十分之一的客戶號是以0開頭的，另外十分之一是以1開頭的，等等，那么這種方法會很適合。如果90%的客戶號以0開頭，那么那個列表就 會有900條記錄，每次查找平均需要進行 450次比較。另外，程序需要執行的搜索有90%都是針對以0開頭的號碼的。因此，平均比較數就大大超過簡單數學運算的范圍了。

如果我們可以按這樣一種方式在我們的列表中分配記錄，情況就會好一些，即每個列表約有相同條目的記錄，而不管鍵值中數字的分布。我們需要一種方法能 夠把客戶號碼混合到一起并更好地分布結果。例如，我們可以取號碼中的每位數，乘以某個大的數（隨著數字位置的不同而不同），然后將結果相加產生一個總數， 把這個數除以10，并將余數作為索引值（index）。當讀入記錄時，程序在客戶號碼上運行這個哈希（hash) 函數來確定記錄屬于哪個列表。當用戶需要查詢時，將同一個哈希函數作為一個“key”用于客戶號碼，這樣就可以搜索正確的列表了。像這樣的一個數據結構就 稱為一個哈希表（hashtable)。

Java中的Hashtables
Java包含兩個類，java.util.Hashtable 和java.util.HashMap，它們提供了一個多種用途的hashtable機制。這兩個類很相似，通常提供相同的公有接口。但它們的確有一些重要的不同點，我在后面會講到。

Hashtable和HashMap對象可以讓你把一個key和一個value結合起來，并用put() 方法把這對key/value輸入到表中。然后你可以通過調用get()方法，把key作為參數來得到這個value（值）。只要滿足兩個基本的要求， key和value可以是任何對象。注意，因為key和value必須是對象，所以原始類型（primitive types）必須通過運用諸如Integer(int)的方法轉換成對象。

為了將一個特定類的對象用做一個key，這個類必須提供兩個方法，equals() 和 hashCode()。這兩個方法在java.lang.Object中，所以所有的類都可以繼承這兩個方法；但是，這兩個方法在Object類中的實現一般沒什么用，所以你通常需要自己重載這兩個方法。

Equals ()方法把它的對象同另一個對象進行比較，如果這兩個對象代表相同的信息，則返回true。該方法也查看并確保這兩個對象屬于相同的類。如果兩個參照對象 是完全一樣的對象，Object.equals()返回true，這就說明了為什么這個方法通常不是很適合的原因。在大多數情況下，你需要一個方法來一個 字段一個字段地進行比較，所以我們認為代表相同數據的不同對象是相等的。

HashCode()方法通過運用對象的內容執行一個哈希函數來生成一個int值。Hashtable和HashMap用這個值來算出一對key/value位于哪個bucket（哈希元）（或列表）中。

作為例子，我們可以查看一下String 類，因為它有自己的方法來實現這兩個方法。String.equals()對兩個String對象一個字符一個字符地進行比較，如果字符串是相同的，則返回true：

例如，假設我要用一個hashtable來實現一個書的目錄，把書的ISBN號碼作為搜索鍵來進行搜索。我可以用String類來承載細節，并準備好了equals()和hashCode()方法（見列表1）。我們可以用put()方法添加成對的key/value到hashtable中（見列表2）。

Put()方法接受兩個參數，它們都屬于Object類型。第一個參數是key；第二個參數是value。Put()方法調用key的hashCode()方法，用表中的列表數來除這個結果。把余數作為索引值來確定該條記錄添加到哪個列表中。注意，key在表中是唯一的；如果你用一個已經存在的key來調用put()，匹配的條目就被修改了，因此它參照的是一個新的值，而舊的值被返回了（當key在表中不存在時，put()返回空值）。

要讀取表中的一個值，我們把搜索鍵用于get()方法。它返回一個轉換到正確類型的Object參照：

你自己的類
如果你想把一個原始類型用做一個key，你必須創建一個同等類型的對象。例如，如果你想用一個整數key，你應該用構造器 Integer(int)從整數中生成一個對象。所有的封裝類??如Integer、Float和Boolean都把原始值看做是對象，它們重載了 equals()和hashCode() 方法，因此，它們可以被用做key。JDK中提供的許多其它的類也是這樣的（甚至Hashtable和HashMap類都實現它們自己的equals() 和hashCode()方法），但你把任何類的對象用做hashtable keys前，應該查看文件。查看類的來源，看看equals()和hashCode()是如何實現的，也很有必要。例如，Byte、Character、 Short和Integer都返回所代表的整數值作為哈希碼。這可能適合，也可能不適合你的需求。

在Java中運用Hashtables
如果你想創建一個hashtable，這個hashtable運用你自己定義的一個類的對象作為key，那么你應該確信這個類的equals()和hashCode()方法提供有用的值。首先查看你擴展的類，確定它的實現是否滿足你的需求。如果沒有，你應該重載方法。

任何equals()方法的基本設計約束是，如果傳遞給它的對象屬于同一個類，而且它的數據字段設定為表示同樣數據的值，那么它就應該返回 true。你也應該確信，如果傳遞一個空的參數給該方法，那么你的代碼返回

在設計equals()和hashCode（）時，另一個要記住的因素是性能問題。每次調用put() 或get()，都包括調用hashCode()來查找正確的列表，當get()掃描列表來查找key時，它為列表中的每個元素調用equals()。實現 這些方法使它們盡可能快而有效地運行，尤其當你打算使你的類公開可用時，因為其它的用戶可能想在執行速度很重要的情況下，在高性能的應用程序中運用你的 類。

Hashtable性能
影響hashtable功效的主要因素就是表中列表的平均長度，因為平均搜索時間與這個平均長度直接相關。很顯然， 要減小平均長度，你必須增加hashtable中列表的數量；如果列表數量非常大，以至于大多數列表或所有列表只包含一條記錄，你就會獲得最佳的搜索效 率。然而，這樣做可能太過分了。如果你的hashtable的列表數遠遠多于數據條目，那你就沒有必要做這樣的內存花費了，而在一些情況下，人們也不可能 接受這樣的做法。

在我們前面的例子中，我們預先知道我們有多少條記錄1,000。知道這點后，我們就可以決定我們的hashtable 應該包含多少個列表，以便達成搜索速度和內存使用效率之間最好的折中方式。然而，在許多情況下，你預先不知道你要處理多少條記錄；數據被讀取的文件可能會 不斷擴大，或者記錄的數量可能一天一天地發生很大的變化。

隨著條目的增加，Hashtable和HashMap類通過動態地擴展表來處理這個問題。這兩個類都有接受表中列表最初數量的構造器，和一個作為參數的負載系數（load factor）：
public Hashtable(
int initialCapacity,
float loadFactor)

public HashMap(
int initialCapacity,
float loadFactor)

將這兩個數相乘計算出一個臨界值。每次給哈希表添加一個新的條目時，計數就被更新，當計數超過臨界值時，表被重新設置（rehash)。（列表數量 增加到以前數量的兩倍加1，所有的條目轉移到正確的列表中。）缺省的構造器設定最初的容量為11，負載系數是0.75，所以臨界值是8。當第九條記錄被添 加到表中時，就重新調整哈希表，使其有23個列表，新的臨界值將是17（23*0.75的整數部分）。你可以看到，負載系數是哈希表中平均列表數量的上 限，這就意味著，在缺省情況下，哈希表很少會有許多包含不只一條記錄的列表。比較我們最初的例子，在那個例子中，我們有1,000條記錄，分布在10個列 表中。如果我們用缺省值，這個表將會擴展到含有1,500多個列表。但你可以控制這點。如果用負載系數相乘的列表數量大于你處理的條目數，那么表永遠不會 重制，所以我們可以仿效下面的例子：

注意，雖然調用put()可以使表增大（列表數量增加），調用remove()不會有相反的結果。所以，如果你有一個大的表，而且從中刪除了大部分條目，結果你會有一個大的但是大部分是空的表。

Hashtable和HashMap
Hashtable和HashMap類有三個重要的不同之處。第一個不同主要是歷史原因。Hashtable是基于陳舊的Dictionary類的，HashMap是Java 1.2引進的Map接口的一個實現。

也許最重要的不同是Hashtable的方法是同步的，而HashMap的方法不是。這就意味著，雖然你可以不用采取任何特殊的行為就可以在一個多 線程的應用程序中用一個Hashtable，但你必須同樣地為一個HashMap提供外同步。一個方便的方法就是利用Collections類的靜態的 synchronizedMap()方法，它創建一個線程安全的Map對象，并把它作為一個封裝的對象來返回。這個對象的方法可以讓你同步訪問潛在的HashMap。這么做的結果就是當你不需要同步時，你不能切斷Hashtable中的同步（比如在一個單線程的應用程序中），而且同步增加了很多處理費用。

第三點不同是，只有HashMap可以讓你將空值作為一個表的條目的key或value。HashMap中只有一條記錄可以是一個空的key，但任 意數量的條目可以是空的value。這就是說，如果在表中沒有發現搜索鍵，或者如果發現了搜索鍵，但它是一個空的值，那么get()將返回null。如果 有必要，用containKey()方法來區別這兩種情況。

一些資料建議，當需要同步時，用Hashtable，反之用HashMap。但是，因為在需要時，HashMap可以被同步，HashMap的功能 比Hashtable的功能更多，而且它不是基于一個陳舊的類的，所以有人認為，在各種情況下，HashMap都優先于Hashtable。

關于Properties
有時侯，你可能想用一個hashtable來映射key 的字符串到value的字符串。DOS、Windows和Unix中的環境字符串就有一些例子，如key的字符串PATH被映射到value的字符串C: /WINDOWS;C:/WINDOWS/SYSTEM。Hashtables是表示這些的一個簡單的方法，但Java提供了另外一種方法。

Java.util.Properties類是Hashtable的一個子類，設計用于String keys和values。Properties對象的用法同Hashtable的用法相象，但是類增加了兩個節省時間的方法，你應該知道。

Store()方法把一個Properties對象的內容以一種可讀的形式保存到一個文件中。Load()方法正好相反，用來讀取文件，并設定Properties對象來包含keys和values。

注意，因為Properties擴展了Hashtable，你可以用超類的put()方法來添加不是String對象的keys和values。這是不可取的。另外，如果你將store()用于一個不包含String對象的Properties對象，store()將失敗。作為put()和get()的替代，你應該用setProperty()和getProperty()，它們用String參數。

好了，我希望你現在可以知道如何用hashtables來加速你的處理了