Hash表

　    　Hash表

　　Hash表也稱散清單，也有直接譯作哈希表，Hash表是一種特殊的資料結構，它同數組、連結清單以及二叉排序樹等相比較有很明顯的差別，它能夠快速定位到想要查找的記錄，而不是與表中存在的記錄的關鍵字進行比較來進行查找。這個源于Hash表設計的特殊性，它采用了函數映射的思想将記錄的存儲位置與記錄的關鍵字關聯起來，進而能夠很快速地進行查找。

1.Hash表的設計思想

　　對于一般的線性表，比如連結清單，如果要存儲聯系人資訊：　

　　那麼可能會設計一個結構體包含姓名，手機号碼這些資訊，然後把4個聯系人的資訊存到一張連結清單中。當要查找”李四 15828662334“這條記錄是否在這張連結清單中或者想要得到李四的手機号碼時，可能會從連結清單的頭結點開始周遊，依次将每個結點中的姓名同”李四“進行比較，直到查找成功或者失敗為止，這種做法的時間複雜度為O(n)。即使采用二叉排序樹進行存儲，也最多為O(logn)。假設能夠通過”李四“這個資訊直接擷取到該記錄在表中的存儲位置，就能省掉中間關鍵字比較的這個環節，複雜度直接降到O(1)。Hash表就能夠達到這樣的效果。

　　Hash表采用一個映射函數 f : key —> address 将關鍵字映射到該記錄在表中的存儲位置，進而在想要查找該記錄時，可以直接根據關鍵字和映射關系計算出該記錄在表中的存儲位置，通常情況下，這種映射關系稱作為Hash函數，而通過Hash函數和關鍵字計算出來的存儲位置(注意這裡的存儲位置隻是表中的存儲位置，并不是實際的實體位址)稱作為Hash位址。比如上述例子中，假如聯系人資訊采用Hash表存儲，則當想要找到“李四”的資訊時，直接根據“李四”和Hash函數計算出Hash位址即可。下面讨論一下Hash表設計中的幾個關鍵問題。

1. Hash函數的設計

　　Hash函數設計的好壞直接影響到對Hash表的操作效率。下面舉例說明：

　　假如對上述的聯系人資訊進行存儲時，采用的Hash函數為：姓名的每個字的拼音開頭大寫字母的ASCII碼之和。

　　是以address(張三)=ASCII(Z)+ASCII(S)=90+83=173;

　　　　address(李四)=ASCII(L)+ASCII(S)=76+83=159;

　　　　address(王五)=ASCII(W)+ASCII(W)=87+87=174;

　　　　address(張帥)=ASCII(Z)+ASCII(S)=90+83=173;

　　假如隻有這4個聯系人資訊需要進行存儲，這個Hash函數設計的很糟糕。首先，它浪費了大量的存儲空間，假如采用char型數組存儲聯系人資訊的話，則至少需要開辟174*12位元組的空間，空間使用率隻有4/174，不到5%；另外，根據Hash函數計算結果之後，address(張三)和address(李四)具有相同的位址，這種現象稱作沖突，對于174個存儲空間中隻需要存儲4條記錄就發生了沖突，這樣的Hash函數設計是很不合理的。是以在構造Hash函數時應盡量考慮關鍵字的分布特點來設計函數使得Hash位址随機均勻地分布在整個位址空間當中。通常有以下幾種構造Hash函數的方法：

　　1)直接定址法

　　取關鍵字或者關鍵字的某個線性函數為Hash位址，即address(key)=a*key+b;如知道學生的學号從2000開始，最大為4000，則可以将address(key)=key-2000作為Hash位址。

　　2)平方取中法

　　對關鍵字進行平方運算，然後取結果的中間幾位作為Hash位址。假如有以下關鍵字序列{421，423，436}，平方之後的結果為{177241，178929，190096}，那麼可以取{72，89，00}作為Hash位址。

　　3)折疊法

　　将關鍵字拆分成幾部分，然後将這幾部分組合在一起，以特定的方式進行轉化形成Hash位址。假如知道圖書的ISBN号為8903-241-23，可以将address(key)=89+03+24+12+3作為Hash位址。

　　4)除留取餘法

　　如果知道Hash表的最大長度為m，可以取不大于m的最大質數p，然後對關鍵字進行取餘運算，address(key)=key%p。

　　在這裡p的選取非常關鍵，p選擇的好的話，能夠最大程度地減少沖突，p一般取不大于m的最大質數。

2.Hash表大小的确定

　　Hash表大小的确定也非常關鍵，如果Hash表的空間遠遠大于最後實際存儲的記錄個數，則造成了很大的空間浪費，如果選取小了的話，則容易造成沖突。在實際情況中，一般需要根據最終記錄存儲個數和關鍵字的分布特點來确定Hash表的大小。還有一種情況時可能事先不知道最終需要存儲的記錄個數，則需要動态維護Hash表的容量，此時可能需要重新計算Hash位址。

3.沖突的解決

　　在上述例子中，發生了沖突現象，是以需要辦法來解決，否則記錄無法進行正确的存儲。通常情況下有2種解決辦法：

　　1)開放定址法

　　即當一個關鍵字和另一個關鍵字發生沖突時，使用某種探測技術在Hash表中形成一個探測序列，然後沿着這個探測序列依次查找下去，當碰到一個空的單元時，則插入其中。比較常用的探測方法有線性探測法，比如有一組關鍵字{12，13，25，23，38，34，6，84，91}，Hash表長為14，Hash函數為address(key)=key%11，當插入12，13，25時可以直接插入，而當插入23時，位址1被占用了，是以沿着位址1依次往下探測(探測步長可以根據情況而定)，直到探測到位址4，發現為空，則将23插入其中。

　　2)鍊位址法

 　　采用數組和連結清單相結合的辦法，将Hash位址相同的記錄存儲在一張線性表中，而每張表的表頭的序号即為計算得到的Hash位址。如上述例子中，采用鍊位址法形成的Hash表存儲表示為：   

 　　雖然能夠采用一些辦法去減少沖突，但是沖突是無法完全避免的。是以需要根據實際情況選取解決沖突的辦法。

4.Hash表的平均查找長度

　　Hash表的平均查找長度包括查找成功時的平均查找長度和查找失敗時的平均查找長度。

　　查找成功時的平均查找長度=表中每個元素查找成功時的比較次數之和/表中元素個數；

　　查找不成功時的平均查找長度相當于在表中查找元素不成功時的平均比較次數，可以了解為向表中插入某個元素，該元素在每個位置都有可能，然後計算出在每個位置能夠插入時需要比較的次數，再除以表長即為查找不成功時的平均查找長度。

　　下面舉個例子：

　　有一組關鍵字{23，12，14，2，3，5}，表長為14，Hash函數為key%11，則關鍵字在表中的存儲如下：

　　位址     0     1     2     3      4     5    6   7   8    9  10   11   12    13

　　關鍵字        23    12   14     2     3    5

　比較次數         1      2    1     3     3     2

　　是以查找成功時的平均查找長度為(1+2+1+3+3+2)/6=11/6；

　　查找失敗時的平均查找長度為(1+7+6+5+4+3+2+1+1+1+1+1+1+1)/14=38/14；

　　這裡有一個概念裝填因子=表中的記錄數/哈希表的長度，如果裝填因子越小，表明表中還有很多的空單元，則發生沖突的可能性越小；而裝填因子越大，則發生沖突的可能性就越大，在查找時所耗費的時間就越多。是以，Hash表的平均查找長度和裝填因子有關。有相關文獻證明當裝填因子在0.5左右的時候，Hash的性能能夠達到最優。是以，一般情況下，裝填因子取經驗值0.5。

5.Hash表的優缺點

　　Hash表存在的優點顯而易見，能夠在常數級的時間複雜度上進行查找，并且插入資料和删除資料比較容易。但是它也有某些缺點，比如不支援排序，一般比用線性表存儲需要更多的空間，并且記錄的關鍵字不能重複。

代碼實作：

<a></a>