MD5即Message-Digest Algorithm 5（信息摘要演算法5），是計算機廣泛使用的散列演算法之一。經MD2、MD3和MD4發展而來，誕生於20世紀90年代初。用於確保信息傳輸完整一致。雖然已被破解，但仍然具有較好的安全性，加之可以免費使用，所以仍廣泛運用於數字簽名、文件完整性驗證以及口令加密等領域。
演算法原理：
散列演算法得到的結果位數是有限的，比如MD5演算法計算出的結果字長為128位，意味著只要我們窮舉2^128次，就肯定能得到一組碰撞，下面讓我們來看看一個真實的碰撞案例。我們之所以說MD5過時，是因為它在某些時候已經很難表現出散列演算法的某些優勢——比如在應對文件的微小修改時，散列演算法得到的指紋結果應當有顯著的不同，而下面的程序說明了MD5並不能實現這一點。
而諸如此類的碰撞案例還有很多，上面只是原始文件相對較小的一個例子。事實上現在我們用智能手機只要數秒就能找到MD5的一個碰撞案例，因此，MD5在數年前就已經不被推薦作為應用中的散列演算法方案，取代它的是SHA家族演算法，也就是安全散列演算法（Secure Hash Algorithm，縮寫為SHA）。
SHA實際包括有一系列演算法，分別是SHA-1、SHA-224、SHA-256、SHA-384以及SHA-512。而我們所說的SHA2實際是對後面4中的統稱。各種SHA演算法的數據比較如下表，其中的長度單位均為位：
MD5和SHA1，它們都有4個邏輯函數，而在SHA2的一系列演算法中都採用了6個邏輯函數。
以SHA-1為例，演算法包括有如下的處理過程：
和MD5處理輸入方式相同
經過添加位數處理的明文，其長度正好為512位的整數倍，然後按512位的長度進行分組，可以得到一定數量的明文分組，我們用Y 0 ，Y 1 ，……Y N-1 表示這些明文分組。對於每一個明文分組，都要重復反復的處理，這些與MD5都是相同的。
而對於每個512位的明文分組，SHA1將其再分成16份更小的明文分組，稱為子明文分組，每個子明文分組為32位，我們且使用M[t]（t= 0, 1,……15）來表示這16個子明文分組。然後需要將這16個子明文分組擴充到80個子明文分組，我們將其記為W[t]（t= 0, 1,……79），擴充的具體方法是：當0≤t≤15時，Wt = Mt；當16≤t≤79時，Wt = ( W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16 ) <<< 1，從而得到80個子明文分組。
所謂初始化緩存就是為鏈接變數賦初值。前面我們實現MD5演算法時，說過由於摘要是128位，以32位為計算單位，所以需要4個鏈接變數。同樣SHA-1採用160位的信息摘要，也以32位為計算長度，就需要5個鏈接變數。我們記為A、B、C、D、E。其初始賦值分別為：A = 0x67452301、B = 0xEFCDAB89、C = 0x98BADCFE、D = 0x10325476、E = 0xC3D2E1F0。
如果我們對比前面說過的MD5演算法就會發現，前4個鏈接變數的初始值是一樣的，因為它們本來就是同源的。
經過前面的准備，接下來就是計算信息摘要了。SHA1有4輪運算，每一輪包括20個步驟，一共80步，最終產生160位的信息摘要，這160位的摘要存放在5個32位的鏈接變數中。
在SHA1的4論運算中，雖然進行的就具體操作函數不同，但邏輯過程卻是一致的。首先，定義5個變數，假設為H0、H1、H2、H3、H4，對其分別進行如下操作：
（A）、將A左移5為與 函數的結果求和，再與對應的子明文分組、E以及計算常數求和後的結果賦予H0。
（B）、將A的值賦予H1。
（C）、將B左移30位，並賦予H2。
（D）、將C的值賦予H3。
（E）、將D的值賦予H4。
（F）、最後將H0、H1、H2、H3、H4的值分別賦予A、B、C、D
這一過程表示如下：
而在4輪80步的計算中使用到的函數和固定常數如下表所示：
經過4輪80步計算後得到的結果，再與各鏈接變數的初始值求和，就得到了我們最終的信息摘要。而對於有多個明文分組的，則將前面所得到的結果作為初始值進行下一明文分組的計算，最終計算全部的明文分組就得到了最終的結果。
『貳』 哈希表、哈希演算法、一致性哈希表
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。它通過把關鍵碼映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（哈希函數），存放記錄的數組叫做散列表。
優點：
哈希表可以提供快速的操作。
缺點：
哈希表通常是基於數組的，數組創建後難於擴展。
也沒有一種簡便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數據項 。
綜上， 如果不需要有序遍歷數據，井且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。
1. 使用哈希函數將被查找的鍵轉換為數組的索引。
2. 處理哈希碰撞沖突。
若關鍵字為 k ，則其值存放在 f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系 f 為散列函數，按這個思想建立的表為散列表。
若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為 均勻散列函數 (Uniform Hash function)，這就是使關鍵字經過散列函數得到一個"隨機的地址"，從而減少碰撞。
散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。
一個好的散列函數一般應該考慮下列因素 ：
1.計算簡單，以便提高轉換速度。
2.關鍵詞對應的地址空間分布均勻，以盡量減少沖突。
1. 直接定址法
取關鍵字或者關鍵字的某個線性函數值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數),這種散列函數也叫做自身函數.如果H(Key)的哈希地址上已經有值了,那麼就往下一個位置找,直到找到H(Key)的位置沒有值了就把元素放進去。
2. 數字分析法
數字分析法就是找出數字的規律，盡可能利用這些數據來構造沖突幾率較低的散列地址。
3. 平方取中法
取關鍵字平方後的中間幾位作為散列地址。這種方法的原理是通過取平方擴大差別，平方值的中間幾位和這個數的每一位都相關，則對不同的關鍵字得到的哈希函數值不易產生沖突，由此產生的哈希地址也較為均勻。該方法適用於關鍵字中的每一位都有某些數字重復出現頻度很高的現象。
4. 折疊法
折疊法是將關鍵字分割成位數相同的幾部分,最後一部分位數可以不同,然後取這幾部分的疊加和(注意:疊加和時去除進位)作為散列地址。
數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割後的每一部分的最低位對齊,然後相加;間界疊加是從一端向另一端沿分割界來回折疊,然後對齊相加。
該方法適用於關鍵字特別多的情況。
5. 隨機數法
選擇一個隨機數,作為散列地址,通常用於關鍵字長度不同的場合。
6. 除留余數法
取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關鍵字直接取模,也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選得不好，則很容易產生沖突。
對不同的關鍵字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，這種現象稱為碰撞(英語:Collision)。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。
通過構造性能良好的散列函數，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關鍵問題。 創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法應該一致。
下面以創建哈希表為例，說明解決沖突的方法。
1.開放定址法
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key)出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：Hi=(H(key)+di)%m i=1，2，…，m-1,其中H（key）為哈希函數，m 為表長，di稱為增量序列，i為碰撞次數。增量序列的取值方式不同，相應的再散列方式也不同。增量序列主要有以下幾種：
(1) 線性探測再散列
di=1，2，3，…，m-1
這種方法的特點是：沖突發生時，順序查看錶中下一單元，直到找出一個空單元或查遍全表。
(2)二次探測再散列
di=12，-12，22，-22，…，k2，-k2( k<=m/2 )
這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。
(3)偽隨機探測再散列
di=偽隨機數序列。
線性探測再散列的 優點 是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。線性探測再散列容易產生「二次聚集」，即在處理同義詞的沖突時又導致非同義詞的沖突。
其實除了上面的幾種方法，開放定址法還有很多變種，不過都是對di有不同的表示方法。（如雙散列探測法：di=i*h2(k)）
2.再哈希法
這種方法是同時構造多個不同的哈希函數：Hi=RHi（key），i=1，2,3，…,n。
當哈希地址H1=RH1（key）發生沖突時，再計算H2=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
3.鏈地址法(拉鏈法)
這種方法的基本思想是將所有哈希地址相同的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表（數組）中，因而查找、插入和刪除主要在同義詞鏈中進行。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。鏈地址法適用於經常進行插入和刪除的情況。
拉鏈法的優點
與開放定址法相比，拉鏈法有如下幾個優點：
(1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
(2)由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；
(3)開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中理論上可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；（散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度）
註：HashMap默認裝填因子是0.75。
(4)在用拉鏈法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放定址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之後填入散列表的同義詞結點的查找路徑。這是因為各種開放定址法中，空地址單元都被理解沒有查找到元素。 因此在用開放定址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。
拉鏈法的缺點
拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，此時將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。
4、建立公共溢出區
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表(在這個方法裡面是把元素分開兩個表來存儲)。
散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。
查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。
影響產生沖突多少有以下三個因素:
1. 散列函數是否均勻;
2. 處理沖突的方法;
3. 散列表的裝填因子。
散列表的裝填因子
定義為:α= 填入表中的元素個數 / 散列表的長度
α是散列表裝滿程度的標志因子。由於表長是定值，α與"填入表中的元素個數"成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大;α越小，填入表中的元素較少，產生沖突的可能性就越小。
實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。
這個HASH演算法不是大學里數據結構課里那個HASH表的演算法。這里的HASH演算法是密碼學的基礎，了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。
Hash演算法在信息安全方面的應用主要體現在以下的3個方面:
⑴ 文件校驗
我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗 數據篡改 的能力，它們一定程度上能檢測出數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。
MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性 校驗和 (Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。
⑵ 數字簽名
Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在 數字簽名 協議中，單向散列函數扮演了一個重要的角色。對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點。
⑶ 鑒權協議
如下的鑒權協議又被稱作挑戰--認證模式:在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。
一致性哈希表簡稱DHT，主要應用於分布式緩存中，可以用來解決分布式存儲結構下動態增加和刪除節點所帶來的問題。比如，一個分布式的存儲系統，要將數據存儲到具體的節點上，如果採用普通的hash方法，將數據映射到具體的節點上，如key%N（key是數據的key，N是機器節點數），如果有一個機器加入或退出這個集群，則所有的數據映射都無效了，如果是持久化存儲則要做數據遷移，如果是分布式緩存，則其他緩存就失效了。
判定哈希演算法好壞的四個定義 ：
1、平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。
2、單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。
3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由於不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。 分散性的定義就是上述情況發生的嚴重程度。好的哈希演算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。
4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那麼對於一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的， 因此好的哈希演算法應能夠盡量降低緩沖的負荷。
在分布式集群中，對機器的添加刪除，或者機器故障後自動脫離集群這些操作是分布式集群管理最基本的功能。如果採用常用的hash取模演算法，那麼在有機器添加或者刪除後，很多原有的數據就無法找到了，這樣嚴重的違反了單調性原則。接下來主要說明一下一致性哈希演算法是如何設計的。
以SpyMemcached的ketama演算法來說，思路是這樣的：
把數據用hash函數，映射到一個很大的空間里，如圖所示。數據的存儲時，先得到一個hash值，對應到這個環中的每個位置，如k1對應到了圖中所示的位置，然後沿順時針找到一個機器節點B，將k1存儲到B這個節點中。
如果B節點宕機了，則B上的數據就會落到C節點上，如下圖所示：
這樣，只會影響C節點，對其他的節點A，D的數據不會造成影響。然而，這又會造成一個「雪崩」的情況，即C節點由於承擔了B節點的數據，所以C節點的負載會變高，C節點很容易也宕機，這樣依次下去，這樣造成整個集群都掛了。
為此，引入了「虛擬節點」的概念：即把想像在這個環上有很多「虛擬節點」，數據的存儲是沿著環的順時針方向找一個虛擬節點，每個虛擬節點都會關聯到一個真實節點，如下圖所使用：
圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載存儲A1、A2的數據，機器B負載存儲B1、B2的數據，機器C負載存儲C1、C2的數據。由於這些虛擬節點數量很多，均勻分布，因此不會造成「雪崩」現象。
『叄』 哈希表與哈希（Hash）演算法
根據設定的 哈希函數H（key） 和 處理沖突的方法 將一組關鍵字影像到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的「像」作為記錄在表中的存儲位置，這種表便成為 哈希表 ，這一映像過程稱為哈希造表或 散列 ，所得存儲位置稱 哈希地址 或 散列地址 。
上面所提到的 哈希函數 是指：有一個對應關系 f ，使得每個關鍵字和結構中一個唯一的存儲位置相對應，這樣在查找時，我們不需要像傳統的爛碼查找演算法那樣進行比較，而是根據這個對應關系 f 找到給定值K的像 f（K） 。
哈希函數也可叫哈希演算法，它可以用於檢驗信息是否相同（ 文件校驗 ），或兆歷褲者檢驗信息的擁有者是否真實（ 數字簽名 ）。
下面分別就哈希函數和族簡處理沖突的方法進行討論;
構造哈希函數的方法有很多。在介紹各種方法前，首先需要明確什麼是「好」 的哈希演算法。若對於關鍵字集合中的任一個關鍵字，經哈希函數映像到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數是 均勻的 （Uniform）哈希函數。換句話說，就是使關鍵字經過哈希函數得到一個「隨機的地址」，以便使一組關鍵字的哈希地址均勻分布在整個地址區間中，從而減少沖突。
常用的構造哈希函數的方法有：
理論研究表明， 除留余數法的模 p 取不大於表長且最接近表長 m 的素數效果最好，且 p 最好取1.1 n ~ 1.7 n 之間的一個素數（n為存在的數據元素個數） 。
以上便是常用的6種構造哈希函數的方法，實際工作中需視不同的情況採用採用不同的哈希函數，通常考慮的因素有：
前面有提到過 均勻的哈希函數可以減少沖突，但不能避免 ，因此，如何處理沖突是哈希造表不可缺少的另一方面。
通常用的處理沖突的方法有下列幾種：
在哈希表上進行查找的過程和哈希建表的過程基本一致。 給定K值，根據建表時設定的哈希函數求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關鍵字，若和給定值相等，則查找成功；否則根據造表時設定的處理沖突的方案找「下一地址」 ，直到找到為止。