對于輸入值的可逆“混合”運算而得到。

常用HASH函數

·直接取余法：f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一個(gè)質(zhì)數。

·乘法取整法：f(x):=trunc((x/maxX)*maxlongit) mod maxM，主要用于實(shí)數。

·平方取中法：f(x):=(x*x div 1000 ) mod 1000000); 平方后取中間的，每位包含信息比較多。

構造方法

散列函數能使對一個(gè)數據序列的訪(fǎng)問(wèn)過(guò)程更加迅速有效，通過(guò)散列函數，數據元素將被更快地定位。

（詳細構造方法可以參考hash函數中的【哈希表的構造方法】）

1．直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線(xiàn)性函數值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數（這種散列函數叫做自身函數）

2． 數字分析法

3． 平方取中法

4． 折疊法

5． 隨機數法

6． 除留余數法：取關(guān)鍵字被某個(gè)不大于散列表表長(cháng)m的數p除后所得的余數為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易產(chǎn)生同義詞。

處理沖突方法

1．開(kāi)放尋址法；Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中H(key)為散列函數，m為散列表長(cháng)，di為增量序列，可有下列三種取法：

1)． di=1,2,3,…，m-1，稱(chēng)線(xiàn)性探測再散列；

2)． di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)稱(chēng)二次探測再散列；

3)． di=偽隨機數序列，稱(chēng)偽隨機探測再散列。

2． 再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函數，即在同義詞產(chǎn)生地址沖突時(shí)計算另一個(gè)散列函數地址，直到?jīng)_突不再發(fā)生，這種方法不易產(chǎn)生“聚集”，但增加了計算時(shí)間。

3． 鏈地址法(拉鏈法)

4． 建立一個(gè)公共溢出區

查找性能分析

散列表的查找過(guò)程基本上和造表過(guò)程相同。一些關(guān)鍵碼可通過(guò)散列函數轉換的地址直接找到，另一些關(guān)鍵碼在散列函數得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過(guò)程。所以，對散列表查找效率的量度，依然用平均查找長(cháng)度來(lái)衡量。

查找過(guò)程中，關(guān)鍵碼的比較次數，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：

1．散列函數是否均勻；

2. 處理沖突的方法；

3．散列表的裝填因子。

散列表的裝填因子定義為：α= 填入表中的元素個(gè)數/散列表的長(cháng)度

α是散列表裝滿(mǎn)程度的標志因子。由于表長(cháng)是定值，α與“填入表中的元素個(gè)數”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。

實(shí)際上，散列表的平均查找長(cháng)度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。

了解了hash基本定義，就不能不提到一些著(zhù)名的hash算法，MD5和SHA-1可以說(shuō)是應用最廣泛的Hash算法，而它們都是以MD4為基礎設計的。

常用hash算法的介紹：

（1)MD4

MD4(RFC 1320)是 MIT 的Ronald L. Rivest在 1990 年設計的，MD 是 Message Digest（消息摘要） 的縮寫(xiě)。它適用在32位字長(cháng)的處理器上用高速軟件實(shí)現——它是基于 32位操作數的位操作來(lái)實(shí)現的。

（2)MD5

MD5(RFC 1321)是 Rivest 于1991年對MD4的改進(jìn)版本。它對輸入仍以512位分組，其輸出是4個(gè)32位字的級聯(lián)，與 MD4 相同。MD5比MD4來(lái)得復雜，并且速度較之要慢一點(diǎn)，但更安全，在抗分析和抗差分方面表現更好。

（3)SHA-1及其他

SHA1是由NIST NSA設計為同DSA一起使用的，它對長(cháng)度小于2^64的輸入，產(chǎn)生長(cháng)度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時(shí)基于和MD4相同原理,并且模仿了該算法。