HashMap、Map等是很多公司面試、筆試的時(shí)候常考的題目，也是實(shí)際開(kāi)發(fā)中經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)，必須好好掌握。因此我從《J2EE開(kāi)發(fā)全程實(shí)錄》中摘取了下面的片段，希望對(duì)同學(xué)們有幫助。學(xué)習(xí)時(shí)請(qǐng)對(duì)照著《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課中“散列”相關(guān)的章節(jié)復(fù)習(xí)。
在實(shí)際問(wèn)題中，按照給定的值進(jìn)行數(shù)據(jù)查詢(xún)是經(jīng)常遇到的，比如，在電話號(hào)碼簿中查詢(xún)某個(gè)人的電話號(hào)碼；在圖書(shū)館中按照ISBN 編號(hào)查找某本書(shū)的位置；在地圖中按照坐標(biāo)查找某個(gè)地點(diǎn)的地名等等。為此，人們創(chuàng)造了一種能夠根據(jù)記錄的關(guān)鍵碼 ( 也就是用以標(biāo)識(shí)數(shù)據(jù)在記錄中的存放位置的數(shù)據(jù)項(xiàng) ) 方便的檢索到對(duì)應(yīng)的記錄信息的數(shù)據(jù)結(jié)構(gòu)，這就是字典 ( Dictionary ) 。
2.2.1字典的定義
我們都使用過(guò)字典，如英漢字典、成語(yǔ)字典，圖書(shū)的檢索目錄、電話簿等也可以看作廣義上的字典。在計(jì)算機(jī)科學(xué)中，把字典也當(dāng)成一種數(shù)據(jù)結(jié)構(gòu)。
我們把字典定義為“鍵- 值對(duì)” (Key-Value Pair) 的集合。根據(jù)不同的問(wèn)題，我們?yōu)槊趾椭蒂x予不同的含義，比如，在英漢字典中，英文單詞是名字，此單詞的中文解釋條目是值；在電話簿中，人名是名字，此人名對(duì)應(yīng)的電話號(hào)碼是值。
字典最基本的操作包括：find( 查找 ) 、 add( 插入 ) 、 remove( 刪除 ) ，分別用來(lái)從字典中檢索數(shù)據(jù)、插入數(shù)據(jù)和刪除數(shù)據(jù)。在實(shí)際存儲(chǔ)中，我們將“鍵 - 值對(duì)”存儲(chǔ)于記錄中，通過(guò)鍵 ( 也就是“鍵 - 值對(duì)”中的名字 ) 來(lái)標(biāo)識(shí)該“鍵 - 值對(duì)”。“鍵 - 值對(duì)”的存放位置和其鍵之間的對(duì)應(yīng)關(guān)系用一個(gè)二元組表示： ( 鍵 , 值的位置 ) 。
從字典中查找“鍵- 值對(duì)”的最簡(jiǎn)單方法就是使用數(shù)組存儲(chǔ)，然后在查找的時(shí)候遍歷此數(shù)組，當(dāng)遍歷到和被查找的“鍵 - 值對(duì)”的名字相同項(xiàng)的時(shí)候，這個(gè)“鍵 - 值對(duì)”就被找到了。這種最樸實(shí)的方式肯定是不能滿(mǎn)足實(shí)際要求的，因此人們發(fā)明了一種檢索效率非常高的組織字典數(shù)據(jù)的方法 ，即哈希表結(jié)構(gòu)。
2.2.2哈希表與哈希方法
哈希方法在“鍵- 值對(duì)”的存儲(chǔ)位置與它的鍵之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系 hash() ，使得每一個(gè)鍵與結(jié)構(gòu)中的一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)：
存儲(chǔ)位置=hash( 鍵 )
在搜索時(shí)，首先對(duì)鍵進(jìn)行hash 運(yùn)算，把求得的值當(dāng)做“鍵 - 值對(duì)”的存儲(chǔ)位置，在結(jié)構(gòu)中按照此位置取“鍵 - 值對(duì)”進(jìn)行比較，若鍵相等，則表示搜索成功。在存儲(chǔ)“鍵 - 值對(duì)”的時(shí)候，依照相同的 hash 函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放，這種方法就叫做哈希方法，也叫做散列方法。在哈希方法中使用的轉(zhuǎn)換函數(shù) hash 被稱(chēng)作哈希函數(shù) ( 或者散列函數(shù) ) 。按照此中算法構(gòu)造出來(lái)的表叫做哈希表 ( 或者散列表 ) 。
哈希函數(shù)建立了從“鍵- 值對(duì)”到哈希表地址集合的一個(gè)映射，有了哈希函數(shù)，我們就可以根據(jù)鍵來(lái)確定“鍵 - 值對(duì)”在哈希表中的位置的地址。使用這種方法由于不必進(jìn)行多次鍵的比較，所以其搜索速度非?？?，很多系統(tǒng)都使用這種方法進(jìn)行數(shù)據(jù)的組織和檢索。
舉一個(gè)例子，有一組“鍵值對(duì)”：<5, ” tom ” >、 <8, ” Jane ” >、 <12, ” Bit ” >、 <17, ” Lily ” >、 <20, ” sunny ” >，我們按照如下哈希函數(shù)對(duì)鍵進(jìn)行計(jì)算 :hash(x)=x%17+3 ，得出如下結(jié)果： hash(5)=8 、 hash(8)=11 、 hash(12)=15 、 hash(17)=3 、 hash(20)=6 。我們把 <5, ” tom ” >、 <8, ” Jane ” >、 <12, ” Bit ” >、 <17, ” Lily ” >、 <20, ” sunny ” >分別放到地址為 8 、 11 、 15 、 3 、 6 的位置上。當(dāng)要檢索 17 對(duì)應(yīng)的值的時(shí)候，只要首先計(jì)算 17 的哈希值為 3 ，然后到地址為 3 的地方去取數(shù)據(jù)就可以找到 17 對(duì)應(yīng)的數(shù)據(jù)是“ Lily ”了，可見(jiàn)檢索速度是非常快的。
2.2.3沖突與沖突的解決
通常鍵的取值范圍比哈希表地址集合大很多，因此有可能經(jīng)過(guò)同一哈希函數(shù)的計(jì)算，把不同的鍵映射到了同一個(gè)地址上面，這就叫沖突。比如，有一組“鍵- 值對(duì)”，其鍵分別為 12361 、 7251 、 3309 、 30976 ，采用的哈希函數(shù)是：
public static int hash(int key)
{
return key%73+13420;
}
則將會(huì)得到hash(12361)=hash(7251)=hash(3309)=hash(30976)=13444 ，即不同的鍵通過(guò)哈希函數(shù)對(duì)應(yīng)到了同一個(gè)地址，我們稱(chēng)這種哈希計(jì)算結(jié)果相同的不同鍵為同義詞。
如果“鍵- 值 對(duì)”在加入哈希表的時(shí)候產(chǎn)生了沖突，就必須找另外一個(gè)地方來(lái)存放它，沖突太多會(huì)降低數(shù)據(jù)插入和搜索的效率，因此希望能找到一個(gè)不容易產(chǎn)生沖突的函數(shù)，即構(gòu) 造一個(gè)地址分布比較均勻的哈希函數(shù)。常用的哈希函數(shù)包括：直接定址法、數(shù)字分析法、除留余數(shù)法、乘留余數(shù)法、平方取中法、折疊法等。應(yīng)該根據(jù)實(shí)際工作中關(guān) 鍵碼的特點(diǎn)選用適當(dāng)?shù)姆椒ā?/span>
雖然采用合適的哈希方法能夠降低沖突的概率，但是沖突仍然是不可避免的，處理沖突的最常用方法就是“桶”算法：假設(shè)哈希表有m 個(gè)地址，就將其改為 m 個(gè)“桶”，其桶號(hào)與哈希地址一一對(duì)應(yīng)，每個(gè)桶都用來(lái)存放互為同義詞的鍵，也就是如果兩個(gè)不同的鍵用哈希函數(shù)計(jì)算得到了同一個(gè)哈希地址，就將它們放到同一個(gè)桶中，檢索的時(shí)候在桶內(nèi)進(jìn)行順序檢索。
2.2.4Java中的 Map 接口
字典數(shù)據(jù)結(jié)構(gòu)如此重要，以至于實(shí)際開(kāi)發(fā)中經(jīng)常需要使用它們。JDK 中提供了相關(guān)的類(lèi)供我們使用，從而避免了自己開(kāi)發(fā)字典類(lèi)的麻煩。
在以前版本的JDK 中，最常使用的字典類(lèi)就是 Dictionary 抽象類(lèi)及其實(shí)現(xiàn)類(lèi) Hashtable ，不過(guò)在新版本的JDK 中不推薦讀者使用 Dictionary 抽象類(lèi)而是使用Map 接口，并且由于 Dictionary 的實(shí)現(xiàn)類(lèi) Hashtable 也實(shí)現(xiàn)了Map 接口，所以我們沒(méi)有理由不使用 Map 接口。
Map接口有很多實(shí)現(xiàn)類(lèi)，比如 HashMap 、 TreeMap 、 Hashtable 、 SortedMap 等，在第三方開(kāi)源包中也有提供了更多功能的實(shí)現(xiàn)類(lèi)，比如Apache-Commons 項(xiàng)目中的 LRUMap 。最常用的就是 HashMap 和 Hashtable ，它們最大的區(qū)別就是 Hashtable 是線程安全的，而 HashMap 則不是線程安全的，在使用的時(shí)候必須進(jìn)行同步。由于JDK 中的工具類(lèi) java.util . Collections 提供了一個(gè) synchronizedMap 方法，可以將非線程安全的Map 接口變量采用裝飾者模式改造成線程安全的，因此使用 HashMap 的場(chǎng)合更多一些，后邊的論述也將以 HashMap 為主。
2.3HashMap
HashMap是 Map 接口的實(shí)現(xiàn)類(lèi)中最常用的一個(gè)，熟練的掌握這個(gè)類(lèi)的使用將會(huì)提高解決問(wèn)題的速度 。
HashMap的主要方法
int size() ：得到Map中“鍵-值對(duì)”的數(shù)量
boolean isEmpty() ：Map是否是空的，也就是是否不含有任何“鍵-值對(duì)”
boolean containsKey(Object key) ：Map中是否含有以key為鍵的“鍵-值對(duì)”
boolean containsValue(Object value) ：Map中是否含有以 value 為值的“鍵-值對(duì)”
Object get(Object key) ：從Map中得到以key為鍵的值，如果Map中不含有以key為鍵的“鍵-值對(duì)”則返回null
Object put(Object key, Object value) ：向Map中存儲(chǔ)以key為鍵、value為值的“鍵-值對(duì)”
Object remove(Object key) :從Map中移除以key為鍵的“鍵-值對(duì)”
void putAll(Map t) ：將另一個(gè)Map中的所有“鍵-值對(duì)”導(dǎo)入到此Map中
void clear() ：清除所有“鍵-值對(duì)”
Set keySet() ：得到所有的鍵
Collection values() ：得到所有的值
Set entrySet() ：得到所有的“鍵-值對(duì)”，Set中的類(lèi)型是Map.Entry
