哈希(Hash)算法,就是把任意長度的輸入通過雜湊演算法變換成固定長度的輸出,該輸出就是散列值。這種轉換是一種壓縮映射,也就是,散列值的空間通常遠小于輸入的空間,不同的輸入可能會散列成相同的輸出,是以不可能從散列值來确定唯一的輸入值。簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5SZmdDZyUmN0QTNkFjMjVmMlRWOlNjNhJTNkNjYjRTN48CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
雜湊演算法性質
如果兩個散列值是不相同的,那麼這兩個散列值的原始輸入也是不相同的。如果兩個散列值是相同的,兩個輸入值很可能是相同的,但不絕對肯定二者一定相等。輸入一些資料計算出散列值,然後部分改變輸入值,一個具有強混淆特性的散列函數會産生一個完全不同的散列值。
哈希查找步驟
1、使用哈希函數将被查找的鍵轉換為數組的索引。在理想的情況下,不同的鍵會被轉換為不同的索引值,但是需要處理多個鍵被哈希到同一個索引值的情況。是以哈希查找的第二個步驟就是處理沖突
2、處理哈希碰撞沖突。如常用的拉鍊法和線性探測法。
哈希常用算法
1、MD4
MD4(RFC 1320)是 MIT 的 Ronald L.Rivest在 1990 年設計基于 32 位操作數的位操作來實作的算法。
2、MD5
MD5(RFC 1321)是Rivest于1991年對MD4的改進版本号。
3、SHA-1及其它
SHA1是由NIST NSA設計為同DSA一起使用的,它對長度小于264的輸入,産生長度為160bit的散列值,是以抗窮舉性能更好。
哈希時間複雜度
雜湊演算法就是把Key通過一個固定的算法函數既所謂的哈希函數轉換成一個整型數字,然後就将該數字對數組長度進行取餘,取餘結果就當作數組的下标,将value存儲在以該數字為下标的數組空間裡。是以哈希表的插入和查找的時間複雜度都是O(1)。
雜湊演算法特點
在用到哈希進行管理的資料結構中,就對速度比較重視,對抗碰撞不太看中,隻要保證哈希均勻分布就可以。在不同的使用場景中,如資料結構和安全領域裡,其中對某一些特點會有所側重。
1、正向快速:給定明文和 Hash算法,在有限時間和有限資源内能計算出Hash值。
2、逆向困難:給定Hash值,在有限時間内很難逆推出明文。
3、輸入敏感:原始輸入資訊修改一點資訊,産生的Hash值都有很大的不同。
4、沖突避免:很難找到兩段内容不同的明文,使得它們的Hash值一緻。即對于任意兩個不同的資料子產品,其Hash值相同的可能性極小。對于給定的資料塊,找到和它Hash值相同的資料塊極為困難。
哈希構造方法
1、直接定址法:位址集合和關鍵字集合大小相同
2、數字分析法:根據Hash的關鍵字的特點選擇合适Hash算法。
3、平方取中法:取關鍵字平方之後的中間極作為哈希位址,一個數平方之後中間幾位數字與數的每一位都相關,取得位數由表長決定。
4、折疊法:關鍵字位數很多,關鍵字每一位上的數字分布大緻均勻的時候,可以采用折疊法得到哈希位址。
5、随機數法:通常關鍵字不等的時候采用此法構造哈希函數較恰當。
雜湊演算法的應用
1、檔案校驗
MD5 Hash算法的"數字指紋"特性,使它成為應用最廣泛的一種檔案完整性校驗和(Checksum)算法,不少Unix系統有提供計算MD5 Checksum的指令。
2、數字簽名
由于非對稱算法的運算速度較慢,是以在數字簽名協定中,單向散列函數扮演了一個重要的角色。對Hash值進行數字簽名,在統計上可以認為與對檔案本身進行數字簽名是等效的。而且這樣的協定還有其他的優點。
3、鑒權協定
傳輸信道是可被偵聽的,但在不可被篡改的情況下,這是一種簡單而安全的傳輸方法。