哈希樹演算法

1. 哪位能講講四叉樹演算法以及其實現原理

1、HMACSHA1的概念
HMACSHA1 是
從 SHA1 哈希函數構造的一種鍵控哈希演算法，被用作 HMAC（基於哈希的消息驗證代碼）。此 HMAC
進程將密鑰與消息數據混合，使用哈希函數對混合結果進行哈希計算，將所得哈希值與該密鑰混合，然後再次應用哈希函數。輸出的哈希值長度為 160
位，可以轉換為指定位數。
上面是微軟的標準定義，我看了也沒太明白，他的作用一句話來理解：就是確認請求的URL或者參數是否存在被篡改，以
簽名為例：發送方（自己）將參數等進行HMAC演算法計算，將得到的哈希值（即簽名值）與請求的參數一同提交至接收方（端），然後接收方再次將參數等值
進行HMAC演算法計算，將得到的哈希值與你傳遞過來的哈希值進行核對驗證，若一樣，說明請求正確、驗證通過，進行一下步工作，若不一樣，將返回錯誤。
（下面說的夠詳細了吧，還不理解，留言給我）

2、 OAuth 1.0中用到的哈希演算法

/// <summary>

/// HMACSHA1演算法加密並返回ToBase64String

/// </summary>

/// <param name="strText">簽名參數字元串</param>

/// <param name="strKey">密鑰參數</param>

/// <returns>返回一個簽名值(即哈希值)</returns>

public static string ToBase64hmac(string strText, string strKey)

{

HMACSHA1 myHMACSHA1 = new HMACSHA1(Encoding.UTF8.GetBytes(strKey));

byte[] byteText = myHMACSHA1.ComputeHash(Encoding.UTF8.GetBytes(strText));

return System.Convert.ToBase64String(byteText);

}
或者寫成，原理一樣：

public static string HMACSHA1Text(string EncryptText, string EncryptKey)
{
//HMACSHA1加密
string message;
string key;
message = EncryptText;
key = EncryptKey;

System.Text.ASCIIEncoding encoding = new System.Text.ASCIIEncoding();
byte[] keyByte = encoding.GetBytes(key);
HMACSHA1 hmacsha1 = new HMACSHA1(keyByte);
byte[] messageBytes = encoding.GetBytes(message);
byte[] hashmessage = hmacsha1.ComputeHash(messageBytes);

return ByteToString(hashmessage);
}

前面都注釋了參數含義，就不再說明了。COPY就可使用

註明：頁面請引用
using System.Security.Cryptography;

3、介紹另外一種HMACSHA1演算法的寫法

public static string HMACSHA1Text(string EncryptText, string EncryptKey)

{
//HMACSHA1加密
HMACSHA1 hmacsha1 = new HMACSHA1();
hmacsha1.Key = System.Text.Encoding.UTF8.GetBytes(EncryptKey);

byte[] dataBuffer = System.Text.Encoding.UTF8.GetBytes(EncryptText);
byte[] hashBytes = hmacsha1.ComputeHash(dataBuffer);
return Convert.ToBase64String(hashBytes);
}

2. 什麼是哈希演算法，哈希函數主要有哪些

額。。LZ是不是看了小說繪的終極解密啊？
我也蠻感興趣滴。。嘿嘿，
哈希函數是一般的線性表，樹中，記錄在結構中的相對位置是隨機的，即和記錄的關鍵字之間不存在確定的關系。
將數據元素的關鍵字K作為自變數，通過一定的函數關系（稱為哈希函數），計算出的值，即為該元素的存儲地址。表示為：
Addr = H（key）
為此在建立一個哈希表之前需要解決兩個主要問題：
⑴構造一個合適的哈希函數
均勻性 H（key）的值均勻分布在哈希表中；
簡單以提高地址計算的速度
⑵沖突的處理
沖突：在哈希表中，不同的關鍵字值對應到同一個存儲位置的現象。即關鍵字K1≠K2，但H（K1）= H（K2）。均勻的哈希函數可以減少沖突，但不能避免沖突。發生沖突後，必須解決；也即必須尋找下一個可用地址。 無論哈希函數設計有多麼精細，都會產生沖突現象，也就是2個關鍵字處理函數的結果映射在了同一位置上，因此，有一些方法可以避免沖突。
1.拉鏈
拉出一個動態鏈表代替靜態順序儲存結構，可以避免哈希函數的沖突，不過缺點就是鏈表的設計過於麻煩，增加了編程復雜度。此法可以完全避免哈希函數的沖突。
2.多哈希法
設計二種甚至多種哈希函數，可以避免沖突，但是沖突幾率還是有的，函數設計的越好或越多都可以將幾率降到最低（除非人品太差，否則幾乎不可能沖突）。
3.開放地址法
開放地址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）
其中，m為哈希表的表長。di 是產生沖突的時候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測再散列。
如果di取1，則每次沖突之後，向後移動1個位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2）
稱二次探測再散列。如果di取值可能為偽隨機數列。稱偽隨機探測再散列。
4.建域法
假設哈希函數的值域為[0,m-1]，則設向量HashTable[0..m-1]為基本表，另外設立存儲空間向量OverTable[0..v]用以存儲發生沖突的記錄。
LZ先把自己現階段的函數搞定，會慢慢接觸高等的函數滴，感覺蠻刺激的。。

3. 請問大家默克爾哈希樹是什麼它有什麼用處

這是比特幣核心代碼組成員Greg Maxwell主導的項目，主要給交易平台的審計程序提供一個公開的、可信賴的演算法。該演算法也被應用到亞馬遜的Dynamo項目中，以及分布式資料庫Cassandra。
顧名思義，「默克爾哈希樹（Merkel Hash Tree）」是一棵樹狀的數據結構（二叉或多叉），該樹狀結構的所有節點（昵稱「葉子」）都是Hash值。

在審計之前，交易平台向第三方審計者，提供完整的哈希樹節點信息，例如每個用戶的賬戶（金額、ID等）審計信息（據以計算節點哈希值的原始數據），以及交易平台的錢包和地址總余額。
因而，交易平台的地址隱私，至少暴露給了第三方審計者。而第三方審計者要對鑒定結果出具意見，承擔商業責任。

4. GSP演算法的GSP演算法描述

GSP演算法 基本步驟如下：
1）掃描序列資料庫，得到長度為1的序列模式L1，作為初始的種子集
2）根據長度為i 的種子集Li ，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然後掃描序列資料庫，計算每個候選序列模式的支持度，產生長度為i+1的序列模式Li+1，並將Li+1作為新的種子集
3）重復第二步，直到沒有新的序列模式或新的候選序列模式產生為止
產生候選序列模式主要分兩步：
連接階段：如果去掉序列模式s1的第一個項目與去掉序列模式s2的最後一個項目所得到的序列相同，則可以將s1與s2進行連接，即將s2的最後一個項目添加到s1中
修切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除
候選序列模式[ 的支持度計算：對於給定的候選序列模式集合C，掃描序列資料庫，對於其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，並增加其支持度計數
GSP需要多次掃描序列資料庫，在第一次掃描中，對所有的單個項目(1—序列模式)進行計數。利用頻繁1—序列模式生成候選頻繁2—序列模式，進行第二次掃描並求候選頻繁2—序列模式的支持數。使用頻繁2—序列模式生成候選頻繁3—序列模式，重復以上過程，直到找出所有的頻繁序列模式。 哈希樹GSP 採用哈希樹存儲候選序列模式。哈希樹的節點分為三類： 1、根節點；
2、內部節點；
3、葉子節點。
根節點和內部節點中存放的是一個哈希表，每個哈希表項指向其它的節點。而葉子節點內存放的是一組候選序列模式。 從根節點開始，用哈希函數對序列的第一個項目做映射來決定從哪個分支向下，依次在第n層對序列的第n個項目作映射來決定從哪個分支向下，直到到達一個葉子節點。將序列儲存在此葉子節點。
初始時所有節點都是葉子節點，當一個葉子節點所存放的序列數目達到一個閾值，它將轉化為一個內部節點。
候選序列模式支持度的計算
給定一個序列s是序列資料庫的一個記錄：
1）對於根節點，用哈希函數對序列s的每一個單項做映射來並從相應的表項向下迭代的進行操作 2）。
2）對於內部節點，如果s是通過對單項x做哈希映射來到此節點的，則對s中每一個和x在一個元素中的單項以及在x所在元素之後第一個元素的第一個單項做哈希映射，然後從相應的表項向下迭代做操作 2）或 3）。
3）對一個葉子節點，檢查每個候選序列模式c是不是s的子序列.如果是相應的候選序列模式支持度加一。
這種計算候選序列的支持度的方法避免了大量無用的掃描，對於一條序列，僅檢驗那些最有可能成為它子序列的候選序列模式。掃描的時間復雜度由O(n*m)降為O(n*t),其中n表示序列數量，m表示候選序列模式的數量，t代表哈希樹葉子節點的最大容量

5. 哈希演算法從原理到實戰

引言 

       將任意長度的二進制字元串映射為定長二進制字元串的映射規則我們稱為散列（hash）演算法，又叫哈希（hash）演算法，而通過原始數據映射之後得到的二進制值稱為哈希值。哈希表（hash表）結構是哈希演算法的一種應用，也叫散列表。用的是數組支持按照下標隨機訪問數據的特性擴展、演化而來。可以說沒有數組就沒有散列表。

哈希演算法主要特點

        從哈希值不能反向推導原始數據，也叫單向哈希。

        對輸入數據敏感，哪怕只改了一個Bit，最後得到的哈希值也大不相同。

        散列沖突的概率要小。

        哈希演算法執行效率要高，散列結果要盡量均衡。

哈希演算法的核心應用

         安全加密 ：對於敏感數據比如密碼欄位進行MD5或SHA加密傳輸。

         唯一標識 ：比如圖片識別，可針對圖像二進制流進行摘要後MD5，得到的哈希值作為圖片唯一標識。

         散列函數 :是構造散列表的關鍵。它直接決定了散列沖突的概率和散列表的性質。不過相對哈希演算法的其他方面應用，散列函數對散列沖突要求較低，出現沖突時可以通過開放定址法或鏈表法解決沖突。對散列值是否能夠反向解密要求也不高。反而更加關注的是散列的均勻性，即是否散列值均勻落入槽中以及散列函數執行的快慢也會影響散列表性能。所以散列函數一般比較簡單，追求均勻和高效。

        *負載均衡 ：常用的負載均衡演算法有很多，比如輪詢、隨機、加權輪詢。如何實現一個會話粘滯的負載均衡演算法呢？可以通過哈希演算法，對客戶端IP地址或會話SessionID計算哈希值，將取得的哈希值與伺服器列表大小進行取模運算，最終得到應該被路由到的伺服器編號。這樣就可以把同一IP的客戶端請求發到同一個後端伺服器上。

        *數據分片 ：比如統計1T的日誌文件中「搜索關鍵詞」出現次數該如何解決？我們可以先對日誌進行分片，然後採用多機處理，來提高處理速度。從搜索的日誌中依次讀取搜索關鍵詞，並通過哈希函數計算哈希值，然後再跟n(機器數)取模，最終得到的值就是應該被分到的機器編號。這樣相同哈希值的關鍵詞就被分到同一台機器進行處理。每台機器分別計算關鍵詞出現的次數，再進行合並就是最終結果。這也是MapRece的基本思想。再比如圖片識別應用中給每個圖片的摘要信息取唯一標識然後構建散列表，如果圖庫中有大量圖片，單機的hash表會過大，超過單機內存容量。這時也可以使用分片思想，准備n台機器，每台機器負責散列表的一部分數據。每次從圖庫取一個圖片，計算唯一標識，然後與機器個數n求余取模，得到的值就是被分配到的機器編號，然後將這個唯一標識和圖片路徑發往對應機器構建散列表。當進行圖片查找時，使用相同的哈希函數對圖片摘要信息取唯一標識並對n求余取模操作後，得到的值k，就是當前圖片所存儲的機器編號，在該機器的散列表中查找該圖片即可。實際上海量數據的處理問題，都可以藉助這種數據分片思想，突破單機內存、CPU等資源限制。

        *分布式存儲 ：一致性哈希演算法解決緩存等分布式系統的擴容、縮容導致大量數據搬移難題。

         JDK集合工具實現 ：HashMap、 LinkedHashMap、ConcurrentHashMap、TreeMap等。Map實現類源碼分析，詳見  https://www.jianshu.com/p/602324fa59ac

總結

        本文從哈希演算法的原理及特點，總結了哈希演算法的常見應用場景。

        其中基於余數思想和同餘定理實現的哈希演算法（除留取余法），廣泛應用在分布式場景中（散列函數、數據分片、負載均衡）。由於組合數學中的「鴿巢」原理，理論上不存在完全沒有沖突的哈希演算法。（PS:「鴿巢」原理是指有限的槽位，放多於槽位數的鴿子時，勢必有不同的鴿子落在同一槽內，即沖突發生。同餘定理：如果a和b對x取余數操作時a%x = b%x，則a和b同餘）

        構造哈希函數的常規方法有：數據分析法、直接定址法、除留取余法、折疊法、隨機法、平方取中法等  。

        常規的解決哈希沖突方法有開放定址法（線性探測、再哈希）和鏈表法。JDK中的HashMap和LinkedHashMap均是採用鏈表法解決哈希沖突的。鏈表法適合大數據量的哈希沖突解決，可以使用動態數據結構（比如：跳錶、紅黑樹等）代替鏈表，防止鏈表時間復雜度過度退化導致性能下降；反之開放定址法適合少量數據的哈希沖突解決。

6. 哈希表演算法的哈希表的優缺點

哈希表是種數據結構，它可以提供快速的插入操作和查找操作。第一次接觸哈希表時，它的優點多得讓人難以置信。不論哈希表中有多少數據，插入和刪除（有時包括側除）只需要接近常量的時間即0(1）的時間級。實際上，這只需要幾條機器指令。
對哈希表的使用者一一人來說，這是一瞬間的事。哈希表運算得非常快，在計算機程序中，如果需要在一秒種內查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時間級。哈希表不僅速度快，編程實現也相對容易。
哈希表也有一些缺點它是基於數組的，數組創建後難於擴展某些哈希表被基本填滿時，性能下降得非常嚴重，所以程序雖必須要清楚表中將要存儲多少數據（或者准備好定期地把數據轉移到更大的哈希表中，這是個費時的過程）。
而且，也沒有一種簡便的方法可以以任何一種順序〔例如從小到大〕遍歷表中數據項。如果需要這種能力，就只能選擇其他數據結構。
然而如果不需要有序遍歷數據，並且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。

7. 哈希桶演算法

通常大家所說的哈希函數也可以稱為散列函數，哈希函數的功能只是將你的目標key通過一種映射方法，也可以說是一種函數運算f，最後得到你目標的
hashValue = f(key)，這里的函數f就稱為哈希函數/散列函數。

可以看到哈希函數的選擇是一個很關鍵的步驟。為了引進哈希桶演算法，必然要介紹一下哈希沖突，因為哈希桶就是為了解決哈希沖突的。舉個例子，有一組序列為[10,11,21,31,38,48,55]，使用的哈希函數為f(key) = key mod 10

這個時候就產生了沖突了，也就是不同的key通過映射後得到了同樣值的hashvalue。

哈希桶演算法其實就是鏈地址解決沖突的方法

如上面的例子所示，就可以設置桶的個數為10，也就是f(key)集合的個數，而這樣的話，hashvalue就可以作為桶的索引，將10,11分別通過f(key)得到0，1則可將這幾個key放入桶0， 1的首地址所指的內存中，然後處理值為21的key，得到hashvalue值為1，這個時候需要放入桶1中，但桶1的首地址已經有了元素11，怎麼辦？那麼就可以為每個桶開辟一片內存，內存中存放所有hashvalue相同的key，沖突的key之間用單向鏈表進行存儲，這樣就解決了哈希沖突，在查找對應key的時候，只需要通過key索引到對應的桶，然後從桶的首地址對應的節點開始查找，就是鏈表順序找到，對比key的值，直到找到對應key的信息，所以，在沖突的時候，特別是沖突率比較高的時候，桶內的鏈表就會很長，使得查找效率比較低，而在最壞的情況下，所有的key都對應同一個hashvalue，當然這種情況不會出現，這樣的哈希函數選取的也沒有意義了，假設這種情況出現，那麼哈希表就退化成了單鏈表，其他桶內存浪費，且將查找效率從O(1)直接降到了O(N)，所以上面才說，哈希函數的選擇也是很關鍵的。

如果相同元素過多，元素在一個桶內部鏈接過長，反而導致時間復雜度上升。解決思路是桶中元素不再指向鏈表，而指向一個紅黑樹。

8. 【區塊鏈與密碼學】第5-2講：哈希函數的構造

本節課程我們將詳細講解哈希函數的構造。

MASH-1 (Molar Arithmetic Secure Hash)是一個基於RSA演算法的哈希演算法，在1995年提出，入選國際標准ISO/IEC 10118-4；MASH-2是MASH-1的改進，把第四步中的2換成了28+1；由於涉及模乘/平方運算，計算速度慢，非常不實用。

分組密碼的工作模式是： 根據不同的數據格式和安全性要求， 以一個具體的分組密碼演算法為基礎構造一個分組密碼系統的方法。

基於分組的對稱密碼演算法比如DES/AES演算法只是描述如何根據秘鑰對一段固定長度(分組塊)的數據進行加密，對於比較長的數據，分組密碼工作模式描述了如何重復應用某種演算法安全地轉換大於塊的數據量。

簡單的說就是，DES/AES演算法描述怎麼加密一個數據塊，分組密碼工作模式模式了如果重復加密比較長的多個數據塊。常見的分組密碼工作模式有五種：

電碼本( Electronic Code Book，ECB)模式

密文分組鏈接(Cipher Block Chaining，CBC)模式

密文反饋(Cipher Feed Back ，CFB)模式

輸出反饋(Output Feed Back ，OFB)模式

計數器(Counter, CTR)模式

ECB工作模式

加密：輸入是當前明文分組。

解密：每一個密文分組分別解密。

具體公式為：

CBC工作模式

加密：輸入是當前明文分組和前一次密文分組的異或。

解密：每一個密文分組被解密後，再與前一個密文分組異或得明文。

具體公式為：

CFB工作模式

加密演算法的輸入是64比特移位寄存器，其初值為某個初始向量IV。

加密演算法輸出的最左(最高有效位)j比特與明文的第一個單元P1進行異或，產生出密文的第1個單元C1，並傳送該單元。

然後將移位寄存器的內容左移j位並將C1送入移位寄存器最右邊(最低有效位)j位。

這一過程繼續到明文的所有單元都被加密為止。

OFB工作模式

OFB模式的結構類似於CFB

不同之處：

OFB模式是將加密演算法的輸出反饋到移位寄存器

CFB模式中是將密文單元反饋到移位寄存器

CTR工作模式

加密：輸入是當前明文分組和計數器密文分組的異或。

解密：每一個密文分組被解密後，再與計數器密文分組異或得明文。

具體公式為：

工作模式比較

ECB模式，簡單、高速，但最弱、易受重發攻擊，一般不推薦。

CBC模式適用於文件加密，比ECB模式慢，安全性加強。當有少量錯誤時，不會造成同步錯誤。

OFB模式和CFB模式較CBC模式慢許多。每次迭代只有少數比特完成加密。若可以容忍少量錯誤擴展，則可換來恢復同步能力，此時用CFB或OFB模式。在字元為單元的流密碼中多選CFB模式。

CTR模式用於高速同步系統，不容忍差錯傳播。

直接設計哈希函數

Merkle在1989年提出迭代型哈希函數的一般結構；(另外一個工作是默克爾哈希樹)，Ron Rivest在1990年利用這種結構提出MD4。(另外一個工作是RSA演算法)，這種結構在幾乎所有的哈希函數中使用，具體做法為：

把所有消息M分成一些固定長度的塊Yi

最後一塊padding並使其包含消息M的長度

設定初始值CV0

循環執行壓縮函數f，CVi=f(CVi -1||Yi -1)

最後一個CVi為哈希值

演算法中重復使用一個壓縮函數f

f的輸入有兩項，一項是上一輪輸出的n比特值CVi-1，稱為鏈接變數，另一項是演算法在本輪的b比特輸入分組Yi-1

f的輸出為n比特值CVi，CVi又作為下一輪的輸入

演算法開始時還需對鏈接變數指定一個初值IV，最後一輪輸出的鏈接變數CVL即為最終產生的雜湊值

通常有b>n，因此稱函數f為壓縮函數

演算法可表達如下：CV0=IV= n比特長的初值

CVi=f(CVi-1,Yi-1)；1≤i≤L

H(M)=CVL

演算法的核心技術是設計難以找到碰撞的壓縮函數f，而敵手對演算法的攻擊重點是f的內部結構

f和分組密碼一樣是由若干輪處理過程組成

對f的分析需要找出f的碰撞。由於f是壓縮函數，其碰撞是不可避免的，因此在設計f時就應保證找出其碰撞在計算上是困難的

哈希函數的構造就講到這里啦，以上三種方式都可以構造哈希函數。下節課我們將學習常用哈希函數，敬請期待！