Hashtables提供了一個(gè)很有用的方法可以使應(yīng)用程序的性能達(dá)到最佳。

Hashtables（哈希表）在計(jì)算機(jī)領(lǐng)域中已不 是一個(gè)新概念了。它們是用來(lái)加快計(jì)算機(jī)的處理速度的，用當(dāng)今的標(biāo)準(zhǔn)來(lái)處理，速度非常慢，而它們可以讓你在查詢(xún)?cè)S多數(shù)據(jù)條目時(shí)，很快地找到一個(gè)特殊的條目。 盡管現(xiàn)代的機(jī)器速度已快了幾千倍，但是為了得到應(yīng)用程序的最佳性能，hashtables仍然是個(gè)很有用的方法。

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

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

當(dāng)然，如果約十分之一的客戶(hù)號(hào)是以0開(kāi)頭的，另外十分之一是以1開(kāi)頭的，等等，那么這種方法會(huì)很適合。如果90%的客戶(hù)號(hào)以0開(kāi)頭，那么那個(gè)列表就 會(huì)有900條記錄，每次查找平均需要進(jìn)行 450次比較。另外，程序需要執(zhí)行的搜索有90%都是針對(duì)以0開(kāi)頭的號(hào)碼的。因此，平均比較數(shù)就大大超過(guò)簡(jiǎn)單數(shù)學(xué)運(yùn)算的范圍了。

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

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

Hashtable和HashMap對(duì)象可以讓你把一個(gè)key和一個(gè)value結(jié)合起來(lái)，并用put() 方法把這對(duì)key/value輸入到表中。然后你可以通過(guò)調(diào)用get()方法，把key作為參數(shù)來(lái)得到這個(gè)value（值）。只要滿(mǎn)足兩個(gè)基本的要求， key和value可以是任何對(duì)象。注意，因?yàn)閗ey和value必須是對(duì)象，所以原始類(lèi)型（primitive types）必須通過(guò)運(yùn)用諸如Integer(int)的方法轉(zhuǎn)換成對(duì)象。

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

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

HashCode()方法通過(guò)運(yùn)用對(duì)象的內(nèi)容執(zhí)行一個(gè)哈希函數(shù)來(lái)生成一個(gè)int值。Hashtable和HashMap用這個(gè)值來(lái)算出一對(duì)key/value位于哪個(gè)bucket（哈希元）（或列表）中。

作為例子，我們可以查看一下String 類(lèi)，因?yàn)樗凶约旱姆椒▉?lái)實(shí)現(xiàn)這兩個(gè)方法。String.equals()對(duì)兩個(gè)String對(duì)象一個(gè)字符一個(gè)字符地進(jìn)行比較，如果字符串是相同的，則返回true：

String.hashCode ()在一個(gè)字符串上運(yùn)行哈希函數(shù)。字符串中每個(gè)字符的數(shù)字代碼都乘以31，結(jié)果取決于字符串中字符的位置。然后將這些計(jì)算的結(jié)果相加，得到一個(gè)總數(shù)。這個(gè) 過(guò)程似乎很復(fù)雜，但是它確保能夠更好地分布值。它也證明了你在開(kāi)發(fā)你自己的hashCode()方法時(shí)，能夠走多遠(yuǎn)，確信結(jié)果是唯一的。

例如，假設(shè)我要用一個(gè)hashtable來(lái)實(shí)現(xiàn)一個(gè)書(shū)的目錄，把書(shū)的ISBN號(hào)碼作為搜索鍵來(lái)進(jìn)行搜索。我可以用String類(lèi)來(lái)承載細(xì)節(jié)，并準(zhǔn)備好了equals()和hashCode()方法（見(jiàn)列表1）。我們可以用put()方法添加成對(duì)的key/value到hashtable中（見(jiàn)列表2）。

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

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

另一個(gè)有用的方法是remove()，其用法同get()幾乎一樣，它把條目從表中刪除，并返回給調(diào)用程序。

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

在Java中運(yùn)用Hashtables
如果你想創(chuàng)建一個(gè)hashtable，這個(gè)hashtable運(yùn)用你自己定義的一個(gè)類(lèi)的對(duì)象作為key，那么你應(yīng)該確信這個(gè)類(lèi)的equals()和hashCode()方法提供有用的值。首先查看你擴(kuò)展的類(lèi)，確定它的實(shí)現(xiàn)是否滿(mǎn)足你的需求。如果沒(méi)有，你應(yīng)該重載方法。

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

另外，在設(shè)計(jì)一個(gè)hashCode()方法時(shí)，應(yīng)該記住一些規(guī)則。首先，該方法必須為一個(gè)特定的對(duì)象返回相同的值，而不管這個(gè)方法被調(diào)用了多少次 （當(dāng)然，只要對(duì)象的內(nèi)容在調(diào)用之間沒(méi)有改變，在將一個(gè)對(duì)象用做一個(gè)hashtable的key時(shí)，應(yīng)該避免這一點(diǎn)）。第二，如果由你的equals()方 法定義的兩個(gè)對(duì)象是相等的，那么它們也必須生成相同的哈希碼。第三，這更像是一個(gè)方針，而不是一個(gè)原則，你應(yīng)該設(shè)法設(shè)計(jì)方法，使它為不同的對(duì)象內(nèi)容生成不 同的結(jié)果。如果偶爾不同的對(duì)象正好生成了相同的哈希碼，這也不要緊。但是，如果該方法只能返回范圍在1到10的值，那么只能用10個(gè)列表，而不管在 hashtable中有多少個(gè)列表。

在設(shè)計(jì)equals()和hashCode（）時(shí)，另一個(gè)要記住的因素是性能問(wèn)題。每次調(diào)用put() 或get()，都包括調(diào)用hashCode()來(lái)查找正確的列表，當(dāng)get()掃描列表來(lái)查找key時(shí)，它為列表中的每個(gè)元素調(diào)用equals()。實(shí)現(xiàn) 這些方法使它們盡可能快而有效地運(yùn)行，尤其當(dāng)你打算使你的類(lèi)公開(kāi)可用時(shí)，因?yàn)槠渌挠脩?hù)可能想在執(zhí)行速度很重要的情況下，在高性能的應(yīng)用程序中運(yùn)用你的 類(lèi)。

Hashtable性能
影響hashtable功效的主要因素就是表中列表的平均長(zhǎng)度，因?yàn)槠骄阉鲿r(shí)間與這個(gè)平均長(zhǎng)度直接相關(guān)。很顯然， 要減小平均長(zhǎng)度，你必須增加hashtable中列表的數(shù)量；如果列表數(shù)量非常大，以至于大多數(shù)列表或所有列表只包含一條記錄，你就會(huì)獲得最佳的搜索效 率。然而，這樣做可能太過(guò)分了。如果你的hashtable的列表數(shù)遠(yuǎn)遠(yuǎn)多于數(shù)據(jù)條目，那你就沒(méi)有必要做這樣的內(nèi)存花費(fèi)了，而在一些情況下，人們也不可能 接受這樣的做法。

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

隨著條目的增加，Hashtable和HashMap類(lèi)通過(guò)動(dòng)態(tài)地?cái)U(kuò)展表來(lái)處理這個(gè)問(wèn)題。這兩個(gè)類(lèi)都有接受表中列表最初數(shù)量的構(gòu)造器，和一個(gè)作為參數(shù)的負(fù)載系數(shù)（load factor）：
public Hashtable(
int initialCapacity,
float loadFactor)

public HashMap(
int initialCapacity,
float loadFactor)

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

你可能不想這么做，除非你沒(méi)有為空的列表節(jié)省內(nèi)存，而且不介意額外的搜索時(shí)間，這可能在嵌入系統(tǒng)中會(huì)出現(xiàn)這種情況。然而，這種方法可能很有用，因?yàn)橹匦略O(shè)置很占用計(jì)算時(shí)間，而這種方法可以保證永遠(yuǎn)不會(huì)發(fā)生重新設(shè)置這種情況。

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

Hashtable和HashMap
Hashtable和HashMap類(lèi)有三個(gè)重要的不同之處。第一個(gè)不同主要是歷史原因。Hashtable是基于陳舊的Dictionary類(lèi)的，HashMap是Java 1.2引進(jìn)的Map接口的一個(gè)實(shí)現(xiàn)。

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

第三點(diǎn)不同是，只有HashMap可以讓你將空值作為一個(gè)表的條目的key或value。HashMap中只有一條記錄可以是一個(gè)空的key，但任 意數(shù)量的條目可以是空的value。這就是說(shuō)，如果在表中沒(méi)有發(fā)現(xiàn)搜索鍵，或者如果發(fā)現(xiàn)了搜索鍵，但它是一個(gè)空的值，那么get()將返回null。如果 有必要，用containKey()方法來(lái)區(qū)別這兩種情況。

一些資料建議，當(dāng)需要同步時(shí)，用Hashtable，反之用HashMap。但是，因?yàn)樵谛枰獣r(shí)，HashMap可以被同步，HashMap的功能 比Hashtable的功能更多，而且它不是基于一個(gè)陳舊的類(lèi)的，所以有人認(rèn)為，在各種情況下，HashMap都優(yōu)先于Hashtable。

關(guān)于Properties
有時(shí)侯，你可能想用一個(gè)hashtable來(lái)映射key 的字符串到value的字符串。DOS、Windows和Unix中的環(huán)境字符串就有一些例子，如key的字符串PATH被映射到value的字符串C: \WINDOWS;C:\WINDOWS\SYSTEM。Hashtables是表示這些的一個(gè)簡(jiǎn)單的方法，但Java提供了另外一種方法。

Java.util.Properties類(lèi)是Hashtable的一個(gè)子類(lèi)，設(shè)計(jì)用于String keys和values。Properties對(duì)象的用法同Hashtable的用法相象，但是類(lèi)增加了兩個(gè)節(jié)省時(shí)間的方法，你應(yīng)該知道。

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

注意，因?yàn)镻roperties擴(kuò)展了Hashtable，你可以用超類(lèi)的put()方法來(lái)添加不是String對(duì)象的keys和values。這是不可取的。另外，如果你將store()用于一個(gè)不包含String對(duì)象的Properties對(duì)象，store()將失敗。作為put()和get()的替代，你應(yīng)該用setProperty()和getProperty()，它們用String參數(shù)。

好了，我希望你現(xiàn)在可以知道如何用hashtables來(lái)加速你的處理了

最新評(píng)論