談?wù)?Hash Table

在我們編程的世界里數(shù)據(jù)的基本組織可以說有三種形式。

1. 結(jié)構(gòu)體(或?qū)ο?
2. 數(shù)組
3. 鏈表

其他任何的數(shù)據(jù)組織形式都可以看作是這三種數(shù)據(jù)組織形式的組合變體。

結(jié)構(gòu)體(或?qū)ο?可以是基本數(shù)據(jù)類型或者其他結(jié)構(gòu)體(或?qū)ο?的組合。結(jié)構(gòu)體或?qū)ο笠话阌脕砻枋鲆粋€(gè)復(fù)雜數(shù)據(jù)實(shí)體。

數(shù)組一般是一組同類型的變量的集合，在內(nèi)存中表現(xiàn)為一片連續(xù)的空間，因?yàn)榭臻g是連續(xù)的，且每一個(gè)數(shù)據(jù)單元占的內(nèi)存空間的大小是相等的，所以可以根據(jù)地址的偏移對(duì)數(shù)據(jù)元素實(shí)現(xiàn)快速訪問，但是當(dāng)需要插入或者刪除一個(gè)元素的時(shí)候，則需要對(duì)目標(biāo)元素的之后的所有元素進(jìn)行移動(dòng)了。

鏈表的單個(gè)節(jié)點(diǎn)一般為結(jié)構(gòu)體或者對(duì)象，因?yàn)殒湵淼膯蝹€(gè)節(jié)點(diǎn)除了需要保存數(shù)據(jù)之外還需要維護(hù)它的相鄰節(jié)點(diǎn)的關(guān)系，如果想獲得鏈表中的某個(gè)節(jié)點(diǎn)的值，需要從鏈表的頭結(jié)點(diǎn)開始遍歷，直到找到需要的東西，而插入或者刪除某個(gè)節(jié)點(diǎn)的話，需要找到相應(yīng)的節(jié)點(diǎn)，修改其以及其相鄰節(jié)點(diǎn)的相關(guān)指針的引用即可。

像其他的數(shù)據(jù)結(jié)構(gòu)，比如 隊(duì)列，棧，樹，都可以通過數(shù)組或者鏈表來組織，并實(shí)現(xiàn)相應(yīng)的操作功能。

這個(gè)世界上沒有十全十美的東西，所以我們要學(xué)會(huì)取舍。任何技術(shù)的實(shí)現(xiàn)都沒有最好的只要最合適的，也就說實(shí)現(xiàn)的最佳方案是和應(yīng)用場(chǎng)景息息相關(guān)的。
很多時(shí)候，我們想對(duì)數(shù)據(jù)進(jìn)行快速的存取（比如緩存的實(shí)現(xiàn)），并用一個(gè)key來標(biāo)記自己存取的數(shù)據(jù)。我們可以把它叫做key-value的結(jié)構(gòu)。
說到“快速”我們很快想到數(shù)組，因?yàn)閿?shù)組可以在O(1)的時(shí)間復(fù)雜內(nèi)完成指定位置元素的讀寫操作。
所以在理想狀態(tài)，如果一個(gè)數(shù)組足夠長，且存在一個(gè)函數(shù)可以將每一個(gè)key映射到唯一的一個(gè)數(shù)組下標(biāo)，那么我們就可以很完美的解決問題。但往往資源都是有限的，我們沒有那么大的空間，也不能設(shè)計(jì)一個(gè)無比負(fù)責(zé)的映射算法保證每一個(gè)key對(duì)應(yīng)到一個(gè)唯一的數(shù)組下標(biāo)。所以我們會(huì)選擇一些折中的方案。

hash table便是為解決這類問題而存在的。

Hash或者你可以翻譯成散列或者雜湊，hash操作其本質(zhì)上就是將一個(gè)數(shù)據(jù)映射成另一個(gè)數(shù)據(jù)，通常情況下原數(shù)據(jù)的長度比hash后的數(shù)據(jù)容量大。
這種映射的關(guān)系我們叫做哈希函數(shù)。

一般情況下 哈希函數(shù)的輸入可能的總數(shù)要遠(yuǎn)遠(yuǎn)多于哈希值所能表示的總數(shù)，所以就有可能兩個(gè)不同的輸入對(duì)應(yīng)同一個(gè)哈希值，通常把具有不同關(guān)鍵碼而具有相同哈希值的記錄稱作“同義詞”。
在信息安全領(lǐng)域中也經(jīng)常使用到哈希函數(shù)，不過需要使用的是單向哈希函數(shù)，就是無法通過哈希的結(jié)果反推出輸入，所以經(jīng)常應(yīng)用于密碼的加密，傳輸內(nèi)容的完整性檢查，在安全領(lǐng)域常用的哈希算法有 MD5，SHA1等。
在哈希表的應(yīng)用中，哈希函數(shù)常用余數(shù)法進(jìn)行，也就是通過求模的方式算出哈希值。

哈希表是一種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)key-value的快速存取。之前說過數(shù)組可以實(shí)現(xiàn)快速存取，所以哈希表肯定會(huì)使用到數(shù)組。在這里，我們把每一個(gè)數(shù)組的單元叫做一個(gè)bucket（桶）。

這里哈希函數(shù)的作用就是將key映射到一個(gè)存儲(chǔ)地址。所以構(gòu)造一個(gè)哈希表我們得先構(gòu)造哈希函數(shù)。
如果一個(gè)key哈希后對(duì)應(yīng)地址中已經(jīng)存放了值了，這種情況我們叫做哈希沖突（Hash collisions）。
如果存在一個(gè)哈希函數(shù)，使得每一個(gè)輸入都能對(duì)應(yīng)到唯一的一個(gè)存儲(chǔ)單元中（沒有沖突），那么這樣的哈希函數(shù)我們可以叫它完美哈希函數(shù)（Perfect Hash Function，簡(jiǎn)稱PHF)。
但為了哈希函數(shù)簡(jiǎn)單，運(yùn)行速度快，往往不會(huì)使用完美哈希函數(shù)。所以沖突肯定會(huì)存在的，為了減少?zèng)_突，我們希望哈希函數(shù)的結(jié)果均勻的分布在地址單元的空間中。這樣可以有效的減少?zèng)_突。

裝填因子Load factor a=哈希表的實(shí)際元素?cái)?shù)目(n)/ 哈希表的容量(m) a越大，哈希表沖突的概率越大，但是a越接近0，那么哈希表的空間就越浪費(fèi)。
一般情況下建議Load factor的值為0-0.7，Java實(shí)現(xiàn)的HashMap默認(rèn)的Load factor的值為0.75，當(dāng)裝載因子大于這個(gè)值的時(shí)候，HashMap會(huì)對(duì)數(shù)組進(jìn)行擴(kuò)張至原來兩倍大。

既然沖突不可避免，那么我們就必須對(duì)沖突進(jìn)行解決(總不能把之前的內(nèi)容覆蓋掉把),
解決沖突的方式主要分兩類
開放定址法(Open addressing)這種方法就是在計(jì)算一個(gè)key的哈希的時(shí)候，發(fā)現(xiàn)目標(biāo)地址已經(jīng)有值了，即發(fā)生沖突了，這個(gè)時(shí)候通過相應(yīng)的函數(shù)在此地址后面的地址去找，直到?jīng)]有沖突為止。這個(gè)方法常用的有線性探測(cè)，二次探測(cè)，再哈希。
這種解決方法有個(gè)不好的地方就是，當(dāng)發(fā)生沖突之后，會(huì)在之后的地址空間中找一個(gè)放進(jìn)去，這樣就有可能后來出現(xiàn)一個(gè)key哈希出來的結(jié)果也正好是它放進(jìn)去的這個(gè)地址空間，這樣就會(huì)出現(xiàn)非同義詞的兩個(gè)key發(fā)生沖突。


鏈接法(Separate chaining)鏈接法是通過數(shù)組和鏈表組合而成的。當(dāng)發(fā)生沖突的時(shí)候只要將其加到對(duì)應(yīng)的鏈表中即可。

與開放定址法相比，鏈接法有如下幾個(gè)優(yōu)點(diǎn)：
①鏈接法處理沖突簡(jiǎn)單，且無堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長度較短；
②由于鏈接法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而鏈接法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；
④在用鏈接法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。而對(duì)開放地址法構(gòu)造的散列表，刪除結(jié)點(diǎn)不能簡(jiǎn)單地將被刪結(jié)點(diǎn)的空間置為空，否則將截?cái)嘣谒筇钊松⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。這是因?yàn)楦鞣N開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記，而不能真正刪除結(jié)點(diǎn)。

當(dāng)然鏈接法也有其缺點(diǎn)，拉鏈法的缺點(diǎn)是：指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴(kuò)大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

posted on 2010-10-25 12:57 葉子 閱讀(4177) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)