![Hash[計算機算法概念]](/img/3/84b/nBnauM3XyYDNzUTN2ADM0cjM1QTMxMjMxkTNzQTNwAzMwIzLwAzLxYzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg "Hash[計算機算法概念]")
簡介
哈希函式對不同的關鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現象稱碰撞。具有相同函式值的關鍵字對該散列函式來說稱做同義詞。綜上所述，根據散列函式H(key)和處理衝突的方法將一組關鍵字映象到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。
若對於關鍵字集合中的任一個關鍵字，經散列函式映象到地址集合中任何一個地址的機率是相等的，則稱此類散列函式為均勻散列函式(UniformHashfunction)，這就是使關鍵字經過散列函式得到一個“隨機的地址”，從而減少衝突。
性質
所有散列函式都有如下一個基本特性：如果兩個散列值是不相同的（根據同一函式），那么這兩個散列值的原始輸入也是不相同的。這個特性是散列函式具有確定性的結果。但另一方面，散列函式的輸入和輸出不是一一對應的，如果兩個散列值相同，兩個輸入值很可能是相同的，但並不能絕對肯定二者一定相等。輸入一些數據計算出散列值，然後部分改變輸入值，一個具有強混淆特性的散列函式會產生一個完全不同的散列值。
典型的散列函式都有無限定義域，比如任意長度的位元組字元串，和有限的值域，比如固定長度的比特串。在某些情況下，散列函式可以設計成具有相同大小的定義域和值域間的一一對應。一一對應的散列函式也稱為排列。可逆性可以通過使用一系列的對於輸入值的可逆“混合”運算而得到。
HASH函式
·直接取余法：f(x):=xmodmaxM;maxM一般是不太接近2^t的一個質數。
·乘法取整法：f(x):=trunc((x/maxX)*maxlongit)modmaxM，主要用於實數。
·平方取中法：f(x):=(x*xdiv1000)mod1000000);平方後取中間的，每位包含信息比較多。
構造方法
散列函式能使對一個數據序列的訪問過程更加迅速有效，通過散列函式，數據元素將被更快地定位。
1．直接定址法：取關鍵字或關鍵字的某個線性函式值為散列地址。即H(key)=key或H(key)=a·key+b，其中a和b為常數（這種散列函式叫做自身函式）
2．數字分析法
3．平方取中法
4．摺疊法
5．隨機數法
6．除留餘數法：取關鍵字被某個不大於散列表表長m的數p除後所得的餘數為散列地址。即H(key)=keyMODp,p<=m。不僅可以對關鍵字直接取模，也可在摺疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞。
處理衝突
1、開放定址法；Hi=(H(key)+di)MODm,i=1,2,…，k(k<=m-1)，其中H(key)為散列函式，m為散列表長，di為增量序列，可有下列三種取法：
1)di=1,2,3,…，m-1，稱線性探測再散列；
2)di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)稱二次探測再散列；
3)di=偽隨機數序列，稱偽隨機探測再散列。
2、再散列法：Hi=RHi(key),i=1,2,…，kRHi均是不同的散列函式，即在同義詞產生地址衝突時計算另一個散列函式地址，直到衝突不再發生，這種方法不易產生“聚集”，但增加了計算時間。
3、鏈地址法(拉鏈法)
4、建立一個公共溢出區
查找性能
散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函式轉換的地址直接找到，另一些關鍵碼在散列函式得到的地址上產生了衝突，需要按處理衝突的方法進行查找。在介紹的三種處理衝突的方法中，產生衝突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。
查找過程中，關鍵碼的比較次數，取決於產生衝突的多少，產生的衝突少，查找效率就高，產生的衝突多，查找效率就低。因此，影響產生衝突多少的因素，也就是影響查找效率的因素。影響產生衝突多少有以下三個因素：
1．散列函式是否均勻；
2.處理衝突的方法；
3．散列表的裝填因子。
散列表的裝填因子定義為：α=填入表中的元素個數/散列表的長度
α是散列表裝滿程度的標誌因子。由於表長是定值，α與“填入表中的元素個數”成正比，所以，α越大，填入表中的元素較多，產生衝突的可能性就越大；α越小，填入表中的元素較少，產生衝突的可能性就越小。
實際上，散列表的平均查找長度是裝填因子α的函式，只是不同處理衝突的方法有不同的函式。
了解了hash基本定義，就不能不提到一些著名的hash算法，MD5和SHA-1可以說是目前套用最廣泛的Hash算法，而它們都是以MD4為基礎設計的。
hash算法
（1)MD4
MD4(RFC1320)是MIT的RonaldL.Rivest在1990年設計的，MD是MessageDigest（訊息摘要）的縮寫。它適用在32位字長的處理器上用高速軟體實現——它是基於32位運算元的位操作來實現的。
（2)MD5
MD5(RFC1321)是Rivest於1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與MD4相同。MD5比MD4來得複雜，並且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好。
（3)SHA-1及其他
SHA1是由NISTNSA設計為同DSA一起使用的，它對長度小於264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1設計時基於和MD4相同原理,並且模仿了該算法。
散列函式套用
由於散列函式的套用的多樣性，它們經常是專為某一套用而設計的。例如，加密散列函式假設存在一個要找到具有相同散列值的原始輸入的敵人。一個設計優秀的加密散列函式是一個“單向”操作：對於給定的散列值，沒有實用的方法可以計算出一個原始輸入，也就是說很難偽造。為加密散列為目的設計的函式，如MD5，被廣泛的用作檢驗散列函式。這樣軟體下載的時候，就會對照驗證代碼之後才下載正確的檔案部分。此代碼有可能因為環境因素的變化，如機器配置或者IP位址的改變而有變動。以保證源檔案的安全性。
錯誤監測和修複函數主要用於辨別數據被隨機的過程所擾亂的事例。當散列函式被用於校驗和的時候，可以用相對較短的散列值來驗證任意長度的數據是否被更改過。
錯誤校正
使用一個散列函式可以很直觀的檢測出數據在傳輸時發生的錯誤。在數據的傳送方，對將要傳送的數據套用散列函式，並將計算的結果同原始數據一同傳送。在數據的接收方，同樣的散列函式被再一次套用到接收到的數據上，如果兩次散列函式計算出來的結果不一致，那么就說明數據在傳輸的過程中某些地方有錯誤了。這就叫做冗餘校驗。
對於錯誤校正，假設相似擾動的分布接近最小(adistributionoflikelyperturbationsisassumedatleastapproximately)。對於一個信息串的微擾可以被分為兩類，大的（不可能的）錯誤和小的（可能的）錯誤。我們對於第二類錯誤重新定義如下，假如給定H(x)和x+s，那么只要s足夠小，我們就能有效的計算出x。那樣的散列函式被稱作錯誤校正編碼。這些錯誤校正編碼有兩個重要的分類：循環冗餘校驗和里德所羅門碼。
語音識別
對於像從一個已知列表中匹配一個MP3檔案這樣的套用，一種可能的方案是使用傳統的散列函式——例如MD5，但是這種方案會對時間平移、CD讀取錯誤、不同的音頻壓縮算法或者音量調整的實現機制等情況非常敏感。使用一些類似於MD5的方法有利於迅速找到那些嚴格相同（從音頻檔案的二進制數據來看）的音頻檔案，但是要找到全部相同（從音頻檔案的內容來看）的音頻檔案就需要使用其他更高級的算法了。
那些並不緊隨IT工業潮流的人往往能反其道而行之，對於那些微小差異足夠魯棒的散列函式確實存在。現存的絕大多數散列算法都是不夠魯棒的，但是有少數散列算法能夠達到辨別從嘈雜房間裡的揚聲器里播放出來的音樂的魯棒性。有一個實際的例子是Shazam服務。用戶可以用電話機撥打一個特定的號碼，並將電話機的話筒靠近用於播放音樂的揚聲器。該項服務會分析正在播放的音樂，並將它於存儲在資料庫中的已知的散列值進行比較。用戶就能夠收到被識別的音樂的曲名。
信息安全
Hash算法在信息安全方面的套用主要體現在以下的3個方面：
（1)檔案校驗
我們比較熟悉的校驗算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗數據篡改的能力，它們一定程度上能檢測並糾正數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。
MD5Hash算法的"數字指紋"特性，使它成為目前套用最廣泛的一種檔案完整性校驗和(Checksum)算法，不少Unix系統有提供計算md5checksum的命令。
（2)數字簽名
Hash算法也是現代密碼體系中的一個重要組成部分。由於非對稱算法的運算速度較慢，所以在數字簽名協定中，單向散列函式扮演了一個重要的角色。對Hash值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對檔案本身進行數字簽名是等效的。而且這樣的協定還有其他的優點。
（3)鑒權協定
如下的鑒權協定又被稱作挑戰--認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。以上就是一些關於hash以及其相關的一些基本預備知識。
散列表
散列表是散列函式的一個主要套用，使用散列表能夠快速的按照關鍵字查找數據記錄。（注意：關鍵字不是像在加密中所使用的那樣是秘密的，但它們都是用來“解鎖”或者訪問數據的。）例如，在英語字典中的關鍵字是英文單詞，和它們相關的記錄包含這些單詞的定義。在這種情況下，散列函式必須把按照字母順序排列的字元串映射到為散列表的內部數組所創建的索引上。
散列表散列函式的幾乎不可能/不切實際的理想是把每個關鍵字映射到唯一的索引上，因為這樣能夠保證直接訪問表中的每一個數據。
一個好的散列函式（包括大多數加密散列函式）具有均勻的真正隨機輸出，因而平均只需要一兩次探測就能找到目標。同樣重要的是，隨機散列函式幾乎不可能出現非常高的衝突率。但是，少量的可以估計的衝突在實際狀況下是不可避免的。
在很多情況下，heuristic散列函式所產生的衝突比隨機散列函式少的多。Heuristic函式利用了相似關鍵字的相似性。例如，可以設計一個heuristic函式使得像FILE0000.CHK,FILE0001.CHK,FILE0002.CHK,等等這樣的檔案名稱映射到表的連續指針上，也就是說這樣的序列不會發生衝突。相比之下，對於一組好的關鍵字性能出色的隨機散列函式，對於一組壞的關鍵字經常性能很差，這種壞的關鍵字會自然產生而不僅僅在攻擊中才出現。性能不佳的散列函式表意味著查找操作會退化為費時的線性搜尋。
擴展
MD5、SHA1的破解
2004年8月17日，在美國加州聖芭芭拉召開的國際密碼大會上，山東大學王小雲教授在國際會議上首次宣布了她及她的研究小組的研究成果——對MD5、HAVAL－128、MD4和RIPEMD四個著名密碼算法的破譯結果。次年二月宣布破解SHA-1密碼。
命令描述
Linux命令——hash
hash命令用來顯示、添加和清除哈希表。該命令的語法格式如下所示。
語法
hash[-l][-r][-p<path><name>][-t<command>]
選項說明
| 選項 | 說明 |
| -l | 顯示哈希表，包括路徑 |
| -r | 清除哈希表 |
| -p <path> <name> | 向哈希表中增加內容 |
| -t <command> | 顯示指定命令的完整路徑 |
