樹(shù)的結(jié)構(gòu)說(shuō)得差不多了，現(xiàn)在我們來(lái)說(shuō)說(shuō)一種數(shù)據(jù)結(jié)構(gòu)叫做哈希表（hash table），哈希表有是干什么用的呢？我們知道樹(shù)的操作的時(shí)間復(fù)雜度通常為O（logN），那有沒(méi)有更快的數(shù)據(jù)結(jié)構(gòu)？當(dāng)然有，那就是哈希表；

1.哈希表簡(jiǎn)介

哈希表（hash table）是一種數(shù)據(jù)結(jié)構(gòu)，提供很快速的插入和查找操作（有的時(shí)候甚至刪除操作也是），時(shí)間復(fù)雜度為O(1)，對(duì)比時(shí)間復(fù)雜度就可以知道哈希表比樹(shù)的效率快得多，并且哈希表的實(shí)現(xiàn)也相對(duì)容易，然而沒(méi)有任何一種數(shù)據(jù)結(jié)構(gòu)是完美的，哈希表也是；哈希表最大的缺陷就是基于數(shù)組，因?yàn)閿?shù)組初始化的時(shí)候大小是確定的，數(shù)組創(chuàng)建后擴(kuò)展起來(lái)比較困難；

當(dāng)哈希表裝滿了之后，就要把數(shù)據(jù)轉(zhuǎn)移到一個(gè)更大的哈希表中，這會(huì)很費(fèi)時(shí)間，而且哈希表不支持有順序的遍歷，因?yàn)閺墓１碇斜闅v數(shù)據(jù)是隨機(jī)的；所以我們使用哈希表的前提是：不需要有序的遍歷數(shù)據(jù)，可以大概知道數(shù)據(jù)量的多少；滿足這兩點(diǎn)就可以用哈希表；

那有人就要問(wèn)了，說(shuō)得這么厲害，哈希表到底是什么樣子的??？下面就隨便說(shuō)兩個(gè)吧。。。

很經(jīng)典的例子就是英語(yǔ)字典，我們查字典的時(shí)候可以根據(jù)這個(gè)單詞就可以找到第xxx頁(yè)，在這里該單詞和頁(yè)數(shù)就對(duì)應(yīng)起來(lái)了，這可以說(shuō)是一個(gè)哈希表；

再舉個(gè)現(xiàn)實(shí)中的例子，在上學(xué)的時(shí)候每個(gè)人在學(xué)校里都會(huì)有一個(gè)學(xué)號(hào)，你這個(gè)人在學(xué)校中就對(duì)應(yīng)這個(gè)學(xué)號(hào)，假如校長(zhǎng)手上有一個(gè)記錄全校學(xué)生的表，然后根據(jù)學(xué)號(hào)找一個(gè)學(xué)生時(shí)，就能很快鎖定這個(gè)學(xué)生的姓名，性別，班級(jí)等信息；有沒(méi)有想過(guò)假如沒(méi)有學(xué)號(hào)的話，校長(zhǎng)想找一個(gè)學(xué)生就只能根據(jù)姓名去找，可是同名同姓的人這么多，想找到目標(biāo)學(xué)生不是一件容易的事。。。。。

ok，在這里哈希表可以看作是校長(zhǎng)手上的那個(gè)表（其實(shí)就是一個(gè)數(shù)組），我們根據(jù)我們要存的信息生成一個(gè)表中的位置的號(hào)碼（在這里這個(gè)號(hào)碼就是數(shù)組的下標(biāo)），根據(jù)這個(gè)號(hào)碼我們就知道該數(shù)據(jù)存在數(shù)組的哪個(gè)位置，然后將數(shù)據(jù)保存進(jìn)去就可以了；假如有個(gè)大小為20的數(shù)組，我要存“aaa”,我們可以想個(gè)很厲害的辦法將這個(gè)字符串變成一個(gè)比較小的數(shù)字，比如是10，那么就把這個(gè)字符串存到數(shù)組的第10個(gè)位置，這樣做的好處就是下次如果要從哈希表中查詢（或刪除）“aaa”這個(gè)字符串時(shí)，只需要將“aaa”字符串算出那個(gè)號(hào)碼10，然后直接去數(shù)組中第10個(gè)位置找一個(gè)看有沒(méi)有這個(gè)字符串，是不是很簡(jiǎn)單??！

所以現(xiàn)在我們需要解決的就是想個(gè)很厲害的辦法可以將字符串變成一個(gè)比較小的數(shù)字（這個(gè)過(guò)程叫做哈?；?，還要保證這個(gè)數(shù)字不能超過(guò)數(shù)組的最大邊界！

2 哈希化

哈?；褪窍朕k法將我們要保存的數(shù)據(jù)對(duì)應(yīng)一個(gè)數(shù)組下標(biāo)，在數(shù)組的該位置下保存數(shù)據(jù)；我們可以把這個(gè)過(guò)程專業(yè)一點(diǎn)的說(shuō)一下：把要保存的數(shù)據(jù)，通過(guò)哈希函數(shù)轉(zhuǎn)化為對(duì)應(yīng)的數(shù)組下標(biāo)；現(xiàn)在我們的目標(biāo)就是怎么編寫一個(gè)哈希函數(shù)可以使得字符串變成數(shù)組下標(biāo)；

這里我們可以假設(shè)一個(gè)字符串t數(shù)組的大小為30，String[] str = new String[30];   要存“cats”這個(gè)單詞，最容易想到的辦法就是用ASCII碼，但是由于ASCII碼太多了不好記，于是我們可以自己設(shè)置一套規(guī)則，我就假設(shè)a到z分別對(duì)應(yīng)1到26，外加空格對(duì)應(yīng)0，現(xiàn)在一套最簡(jiǎn)陋的規(guī)則就出來(lái)了,我那么“cats”這個(gè)單詞：c = 3,a = 1,t = 20,s = 19，現(xiàn)在“cats”有兩種辦法變成數(shù)組的下標(biāo)；

額外補(bǔ)充一下：假如我們要保存的字符串有50個(gè)，那么我們new的數(shù)組大小一定要是它的兩倍大，即 new String[100];，后面會(huì)說(shuō)到這個(gè)原因

2.1哈希函數(shù)實(shí)現(xiàn)一

怎么實(shí)現(xiàn)比較好呢？別想那么多，直接相加就好，3+1+20+19 = 43，這個(gè)時(shí)候就有個(gè)小問(wèn)題，我們的數(shù)組的大小為30，也就是說(shuō)數(shù)組下標(biāo)最大值是29，而這里我們的數(shù)字為43，怎么將43變成29以內(nèi)的數(shù)（包括29）呢？因?yàn)槿魏螖?shù)除以30的余數(shù)只都在0-29之間，于是我們用43除以30拿到余數(shù)13，那么我們就把”cats“放到數(shù)組下標(biāo)為13的位置,str[13] = "cats";

這種哈希函數(shù)的實(shí)現(xiàn)很容易，但是往往越容易的東西缺點(diǎn)就越大，最大的缺陷就是有很多單詞變成數(shù)字是相同的，比如was，tin，give等100多個(gè)單詞變成數(shù)字后都是43，然后我們恰巧添加單詞的時(shí)候就是這些單詞，現(xiàn)在問(wèn)題來(lái)了，多個(gè)單詞最后算出來(lái)的數(shù)組下標(biāo)很大概率上是一樣的，也就是數(shù)組一個(gè)位置要放多個(gè)數(shù)據(jù)，怎么解決這個(gè)問(wèn)題呢？我們可以換一種哈希函數(shù)的實(shí)現(xiàn)來(lái)降低這個(gè)概率

2.2 哈希函數(shù)實(shí)現(xiàn)二

由2.1可以知道太多的單詞變成數(shù)字的結(jié)果是一樣的，那么我們就要想辦法為每一個(gè)單詞都對(duì)應(yīng)一個(gè)獨(dú)一無(wú)二的整數(shù)，然后用這個(gè)整數(shù)除以數(shù)組的大小取余數(shù)，就可以知道該單詞在數(shù)組中的存放位置；

于是啊，我們可以利用冪的連乘來(lái)得到這個(gè)獨(dú)一無(wú)二的整數(shù)，比如“cats”用這種計(jì)算方法：3*273+1*272+20*271+19*270，有點(diǎn)類似二進(jìn)制變成十進(jìn)制，通過(guò)這個(gè)算法，可以得到一個(gè)獨(dú)一無(wú)二的整數(shù)，其他的任何單詞通過(guò)這種方法算出來(lái)的結(jié)果幾乎是不可能相等的，有興趣的可以試試；然后將這個(gè)計(jì)算結(jié)果除以30取余數(shù)，就可以得到一個(gè)數(shù)組的位置，然后將該字符串丟到里面即可；

不知道大家有沒(méi)有發(fā)現(xiàn)這種方法的一個(gè)問(wèn)題，因?yàn)閿?shù)組的大小是一定的，而且我們是通過(guò)取余數(shù)來(lái)得到數(shù)組的位置，那么問(wèn)題來(lái)了，即使是兩個(gè)不相同的整數(shù)分別除以30，最后的余數(shù)是相等的；

就比如有兩個(gè)字符串通過(guò)冪的連乘最后得到32和62（當(dāng)然我們這里肯定不會(huì)得到這兩個(gè)整數(shù)，為了好理解隨便拿兩個(gè)數(shù)），雖然這兩個(gè)數(shù)是獨(dú)一無(wú)二的，但是除以30余數(shù)都為2，那么兩個(gè)數(shù)據(jù)要保存到哈希表中肯定會(huì)有沖突，下后面我們來(lái)解決一下這個(gè)沖突；

有個(gè)簡(jiǎn)單的哈希函數(shù)實(shí)現(xiàn)看一下（雖然還可以進(jìn)行修改一下，但是這個(gè)已經(jīng)差不多了）；

3.沖突

沖突的原因就是兩個(gè)獨(dú)一無(wú)二的整數(shù)除以數(shù)組的大小，取余數(shù)是相等的，而數(shù)組中一個(gè)位置只能存一個(gè)數(shù)據(jù)，這就導(dǎo)致了沖突，解決沖突的辦法有兩種；

3.1 解決方法一（開(kāi)放地址法）

還記得前面說(shuō)過(guò)數(shù)組的大小要為實(shí)際數(shù)量的兩倍嗎？就是為了這個(gè)時(shí)候用的，假如一個(gè)單詞已經(jīng)放在了數(shù)組的第15個(gè)位置那里，另外一個(gè)單詞本來(lái)也要放在第15的位置，由于這個(gè)位置已經(jīng)被別人占了。那就放在數(shù)組的另外一個(gè)位置上，反正還有很多數(shù)組比較大，這種方式叫做------開(kāi)放地址法

3.2 解決方法二（鏈地址法 ）

既然有兩個(gè)數(shù)據(jù)都要放在數(shù)組的一個(gè)位置上，那就想辦法把第二個(gè)數(shù)據(jù)連在第一個(gè)數(shù)據(jù)后面，通過(guò)第一個(gè)數(shù)據(jù)可以找到第二個(gè)數(shù)據(jù)，而數(shù)組中只保存第一個(gè)數(shù)據(jù)的地址；其實(shí)就是一句話，數(shù)組中每個(gè)位置放一個(gè)鏈表；

這種方法的好處很明顯，完美解決上述沖突，不需要用什么花里胡哨的操作；缺陷就是當(dāng)鏈表太長(zhǎng)了，我們要查詢這個(gè)鏈表的最后面的數(shù)據(jù)，只能慢慢遍歷這個(gè)鏈表，而我們知道，鏈表的優(yōu)勢(shì)是插入和刪除，而對(duì)于查詢這種操作是比較坑爹的，而我們前面用了紅黑樹(shù)這樣的結(jié)構(gòu)來(lái)完美解決鏈表的缺點(diǎn)；最后，我們就差不多想到了一個(gè)比較實(shí)用的方法：數(shù)組的每個(gè)位置都存放一個(gè)鏈表，當(dāng)鏈表的節(jié)點(diǎn)很少的時(shí)候，那就用鏈表吧！但是當(dāng)鏈表慢慢的變長(zhǎng)，當(dāng)節(jié)點(diǎn)數(shù)目到達(dá)一個(gè)界限的時(shí)候，我們就把這個(gè)鏈表變成一個(gè)紅黑樹(shù)，比較完美的方案，這也叫做------鏈地址法 

順便一提，jdk7的HashMap就是數(shù)組中放鏈表，即使鏈表很長(zhǎng)也不會(huì)變紅黑樹(shù)；jdk8中的HashMap才增加了變紅黑樹(shù)這個(gè)操作

4.開(kāi)放地址法

所謂的開(kāi)放地址法就是：根據(jù)我們要保存的數(shù)據(jù)計(jì)算出來(lái)的數(shù)組下標(biāo)的那個(gè)位置已經(jīng)存放了數(shù)據(jù)，這個(gè)時(shí)候我們就要再找一個(gè)空位置，然后將要保存的數(shù)據(jù)丟進(jìn)去即可，那么怎么找比較好呢？這里提供三種方式，線性探測(cè)，二次探測(cè)和再哈希法，下面就看看這三種方式到底是怎么工作的；

4.1 線程探測(cè)

看名字線性就知道是從前往后尋找空的位置，舉個(gè)很簡(jiǎn)單的例子，當(dāng)一個(gè)字符串經(jīng)過(guò)運(yùn)算對(duì)應(yīng)于數(shù)組下標(biāo)為52，然而此時(shí)52這個(gè)位置上已經(jīng)有了數(shù)據(jù)，那么就嘗試放到53的位置，假如53的位置也已經(jīng)放了數(shù)據(jù)，那就放到54位置，就這樣一直往后慢慢找，直到找到一個(gè)空的位置就把數(shù)據(jù)放進(jìn)去；而此時(shí)找的次數(shù)越多，假如已經(jīng)找到56的位置，那么從53到56這么多位置叫做填充序列，當(dāng)填充序列很長(zhǎng)的時(shí)候，我們就稱為原始聚集，下圖所示：

這里填充序列的中有5個(gè)填充單元，我們也可以說(shuō)步數(shù)為1，每次探測(cè)都是前進(jìn)一步；我們可以知道當(dāng)探測(cè)的次數(shù)越多的時(shí)候，說(shuō)明聚集越嚴(yán)重，下一次再想添加到這個(gè)位置的數(shù)據(jù)的效率就越低；

還有就是當(dāng)哈希表填充得越滿，效率也就越低，所以當(dāng)哈希表快滿了之后就要擴(kuò)展，而java中數(shù)組是不能直接進(jìn)行擴(kuò)展的，需要再新建一個(gè)數(shù)組，然后想辦法將這個(gè)哈希表中的數(shù)據(jù)復(fù)制到新的數(shù)組中，注意，這里不能直接復(fù)制，因?yàn)樾碌臄?shù)組的容量和原來(lái)的數(shù)組不一樣，那么原來(lái)哈希表中所有的數(shù)據(jù)必須要重新哈?；?，然后放入到新的數(shù)組中，非常耗時(shí)....

4.2 二次探測(cè)

根據(jù)前面我們的線性探測(cè)可以知道，假如經(jīng)過(guò)哈希函數(shù)計(jì)算出來(lái)的原始數(shù)組下標(biāo)為x，那么線性探測(cè)的位置是x+1，x+2，x+3，x+4.....,；那么 進(jìn)行二次探測(cè)找的位置就是x+12，x+22，x+32，x+42.....其實(shí)就是按照步數(shù)的平方進(jìn)行探測(cè)看里面有沒(méi)有數(shù)據(jù)，沒(méi)有的話才放進(jìn)去新的數(shù)據(jù)，二次探測(cè)可以防止聚集太長(zhǎng)所導(dǎo)致的效率下降問(wèn)題；

對(duì)于二次探測(cè)來(lái)說(shuō)，如果當(dāng)前計(jì)算出來(lái)的位置為x，首先會(huì)探測(cè)x后面一個(gè)位置，如果這個(gè)位置有數(shù)據(jù)，那就多往后4個(gè)位置看有沒(méi)有數(shù)據(jù)，假如還是有數(shù)據(jù)，那么二次探測(cè)可能會(huì)覺(jué)得你這個(gè)聚集特別長(zhǎng)，于是這次跳得更遠(yuǎn)的位置，當(dāng)前位置后面的16的位置等等，直到最后跳過(guò)整個(gè)數(shù)組， 這樣可以避免一個(gè)一個(gè)的位置慢慢探測(cè)的底下效率，二次探測(cè)下圖所示：

二次探測(cè)也有點(diǎn)問(wèn)題，會(huì)導(dǎo)致二次聚集，那什么又是二次聚集呢？其實(shí)跟原始聚集差不多吧！比如184，302，420，544這幾個(gè)整數(shù)都要放到哈希表中，而且這幾個(gè)數(shù)經(jīng)過(guò)哈希算法算出來(lái)的數(shù)組下標(biāo)都為7，302需要以1步長(zhǎng)進(jìn)行探測(cè)，而420要先以1為步長(zhǎng)，然后以4步長(zhǎng)進(jìn)行探測(cè)，而544要先以1為步長(zhǎng)，然后以4為步長(zhǎng)，最后以16步長(zhǎng)進(jìn)行探測(cè)，假如后面還有數(shù)據(jù)對(duì)應(yīng)的數(shù)組下標(biāo)為7，那么還是要重復(fù)這個(gè)步驟，而且是越來(lái)越長(zhǎng)....這也是一種聚集，個(gè)人感覺(jué)從某種意義來(lái)說(shuō)和原始聚集性質(zhì)差不多吧！

二次探測(cè)不常用，因?yàn)橛懈玫霓k法解決，就是再哈希法；

4.3 再哈希法

用再哈希法可以消除原始聚集和二次聚集，那么什么是再哈希法呢？我們可以知道產(chǎn)生原始聚集和二次聚集的原因其實(shí)差不多，都是由于多個(gè)數(shù)據(jù)添加到哈希表中的同一個(gè)位置，然后根據(jù)步長(zhǎng)一個(gè)一個(gè)位置的探測(cè)，直到找到一個(gè)空的位置，如果需要找的位置特別多，那么這就是聚集，添加的效率的就會(huì)大幅度降低； 

那么我們就要想一種方法即使多個(gè)數(shù)據(jù)要放在哈希表的同一個(gè)位置，但是不需要從頭開(kāi)始一個(gè)一個(gè)位置的探測(cè)，如果每個(gè)數(shù)據(jù)都可以產(chǎn)生一個(gè)獨(dú)一無(wú)二的步長(zhǎng)那不就好了么！然后直接根據(jù)這個(gè)步長(zhǎng)探測(cè)該位置將數(shù)據(jù)丟進(jìn)去就ok了；

于是我們準(zhǔn)備了兩個(gè)哈希函數(shù)，一個(gè)哈希函數(shù)就是我們上面說(shuō)到的可以產(chǎn)生對(duì)應(yīng)的數(shù)組下標(biāo)，另外一個(gè)哈希函數(shù)可以產(chǎn)生步長(zhǎng)，其實(shí)就是多個(gè)數(shù)據(jù)放在同一個(gè)位置產(chǎn)發(fā)生沖突，就用這個(gè)哈希函數(shù)再次哈?；a(chǎn)生一個(gè)步長(zhǎng)，根據(jù)這個(gè)步長(zhǎng)進(jìn)行探測(cè)就可以了，而不用每次都從第一個(gè)步長(zhǎng)開(kāi)始；比如下面就有一個(gè)產(chǎn)生步長(zhǎng)的哈希函數(shù)，我們可以知道步長(zhǎng)的范圍是1-constant，注意步長(zhǎng)不能為0，否則就原地踏步了。。。

上圖中，假如我們往哈希表中添加的數(shù)據(jù)是數(shù)字，那就直接將數(shù)據(jù)和數(shù)組大小取余得到數(shù)組下標(biāo)，這里的key就是我們的數(shù)據(jù)，constant只要是小于數(shù)組容量的一個(gè)質(zhì)數(shù)，隨便什么都可以

順便一提：再哈希法使用的前提必須保證數(shù)組的容量為一個(gè)質(zhì)數(shù)，因?yàn)檫@樣才能使得所有位置都被探測(cè)到；可以試試假如數(shù)組容量為15，步長(zhǎng)為5，一個(gè)數(shù)據(jù)經(jīng)過(guò)計(jì)算得到額數(shù)組下標(biāo)為0，那么探測(cè)的位置應(yīng)該為：（0+5）%15 = 5,、（5+5）%15 = 10，（10+5）%15 = 0，只會(huì)探測(cè)0、5、10這三個(gè)位置；但是如果數(shù)組容量為質(zhì)數(shù)13，步長(zhǎng)為5，第一個(gè)數(shù)據(jù)下標(biāo)還是0，那么探測(cè)位置為：（0+5）%13 = 5,、（5+5）%13 = 10，（10+5）%13 = 2、（2+5）%13 = 7，（7+5）%13 = 12，（12+5）%13 = 4，（4+5）%13 = 9等等，可以看到每次探測(cè)的位置都不一樣，可以探測(cè)到數(shù)組中所有位置只要有空的就把數(shù)據(jù)當(dāng)進(jìn)去即可；

假如使用的是開(kāi)放地址法，那么探測(cè)序列就用這個(gè)再哈希法生成，其實(shí)很容易！

5.鏈地址法 

可以看到上面的開(kāi)放地址法有點(diǎn)麻煩，需要找到探測(cè)序列真的是日了狗了，麻煩的我都不想看了，如果可以不用這么麻煩那該多好呀，ok，那就用鏈地址法吧！就類似下面這樣的結(jié)構(gòu)，原始的數(shù)組中不直接保存數(shù)據(jù)，每個(gè)位置只是保存第一個(gè)數(shù)據(jù)的引用，通過(guò)該位置第一個(gè)引用就可以取到后面所有的數(shù)據(jù)！如果鏈表太長(zhǎng)遍歷起來(lái)就比較費(fèi)勁，可以轉(zhuǎn)為紅黑樹(shù)效率就高了很多；

這里其實(shí)沒(méi)什么好說(shuō)的，因?yàn)閿?shù)組和鏈表的使用很熟悉了，沒(méi)什么特別難的東西，基本邏輯：只需要新建一個(gè)MyHashTable的類，這個(gè)類中有幾個(gè)屬性：一個(gè)數(shù)組，一個(gè)int類型的屬性標(biāo)識(shí)數(shù)組真實(shí)容量的大??；最好有個(gè)節(jié)點(diǎn)類為靜態(tài)內(nèi)部類，這個(gè)靜態(tài)內(nèi)部類中實(shí)現(xiàn)了對(duì)鏈表的增刪改查的操作；然后在MyHashTable類中寫一個(gè)哈希函數(shù)的方法，根據(jù)這個(gè)哈希函數(shù)得出來(lái)的數(shù)組下標(biāo)，最后對(duì)數(shù)組的增刪改查了！

6.總結(jié)

哈希表其實(shí)還可以用在外部存儲(chǔ)中，也就是硬盤中，有興趣的可以看看，不過(guò)我感覺(jué)到這里就差不多了！其實(shí)哈希表的內(nèi)容沒(méi)多少吧，最主要的就是哈希函數(shù)的選取，選擇一個(gè)好的哈希函數(shù)可以使得我們的哈希表的效率更高！然后就是數(shù)組中存數(shù)據(jù)的方式，可以直接在數(shù)組中存數(shù)據(jù)，也可以在數(shù)組中存節(jié)點(diǎn)的引用，其實(shí)吧，知不知道二維數(shù)組？在我們這個(gè)數(shù)組中每個(gè)位置存的是另外一個(gè)數(shù)組的引用，這樣其實(shí)也行，由于擴(kuò)展起來(lái)很困難，使用鏈表比使用二維數(shù)組好。。。

最新評(píng)論