什么是哈希/ Hash

哈希又稱作“散列”，是一種數(shù)學計算機程序，它接收任何一組任意長度的輸入信息，通過哈希算法變換成固定長度的數(shù)據(jù)指紋輸出形式，如字母和數(shù)字的組合，該輸出就是“哈希值”。

總體而言，哈希算法可理解為一種消息摘要算法，將消息或數(shù)據(jù)壓縮變小并擁有固定格式。由于其單向運算具有一定的不可逆性，哈希算法已成為加密算法中一個構(gòu)成部分，但完整的加密機制不能僅依賴哈希算法。

在一個cache系統(tǒng)中，需要實現(xiàn)一個域名白名單，域名為下列數(shù)據(jù)：
、、sohu.com 等
該白名單需要在程序啟動時加載一次，主要執(zhí)行查詢操作。請設計一個數(shù)據(jù)結(jié)構(gòu)和相應的初始化查詢函數(shù)，使得檢索盡可能的快。（不能使用stl::map,等等key-value刑類庫）。

我們可以看到，該題目提出了字符串的快速查找，并且只加載一次。使用Hash比較好。

我們可能首先就是想到使用 C++ 中的 MAP ，題目中給出了不允許使用MAP，那么肯定第二選擇就是使用Berkeley DB (DB)這種的文件數(shù)據(jù)庫了，但是題目中明顯提出不允許使用key-value類型庫。

我們思考Berkeley DB (DB)的原理可以曉得，這個就是一個Hash的過程，map其實也是hash的思想。

自己設計一個hash系統(tǒng)咯。沖突處理…

字符串hash可能就想到使用ELFhash算法，主要分析下ELFHash算法。

ELFhash函數(shù)在UNIX系統(tǒng)V 版本4中的“可執(zhí)行鏈接格式”( Executable and Linking Format，即ELF )中會用到，ELF文件格式用于存儲可執(zhí)行文件與目標文件。ELFhash函數(shù)是對字符串的散列。它對于長字符串和短字符串都很有效，字符串中每個字符都有同樣的作用，它巧妙地對字符的ASCII編碼值進行計算，ELFhash函數(shù)對于能夠比較均勻地把字符串分布在散列表中。

這些函數(shù)使用位運算使得每一個字符都對最后的函數(shù)值產(chǎn)生影響。

// ELF Hash Function

unsignedintELFHash(char*str)

{

unsignedinthash = 0;

unsignedintx= 0;

while(*str)

{

hash = (hash << 4) + (*str++);//hash左移4位，當前字符ASCII存入hash低四位。?

if((x = hash & 0xF0000000L) != 0)

{//如果最高的四位不為0，則說明字符多余7個，如果不處理，再加第九個字符時，第一個字符會被移出，因此要有如下處理。

//該處理，如果對于字符串(a-z或者A-Z)就會僅僅影響5-8位，否則會影響5-31位，因為C語言使用的算數(shù)移位

hash ^= (x >> 24);

//清空28-31位。

hash &= ~x;

}

}

//返回一個符號位為0的數(shù)，即丟棄最高位，以免函數(shù)外產(chǎn)生影響。(我們可以考慮，如果只有字符，符號位不可能為負)

return(hash & 0×7FFFFFFF);

}

常見哈希算法

目前常見的 Hash 算法包括國際上的 Message Digest（ MD） 系列和 Secure Hash Algorithm（ SHA） 系列算法，以及國內(nèi)的 SM3 算法。

其中，SHA 256 是 SHA 系列算法之一，由美國國安局設計、美國國家標準與技術(shù)研究院發(fā)布的一套哈希算法，由于其摘要長度為 256bits，故稱 SHA 256。SHA 256也是保護數(shù)字信息的最安全的方法之一。

例如計算

“hello blockchain world, this is yeasy@github”的SHA-256 Hash值，

得到的結(jié)果將是

“db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90”。

對于某個文件，無需查看原始內(nèi)容，只要其 SHA-256 Hash 計算后結(jié)果相同，則說明該文件內(nèi)容極大概率就是一樣的。

審核編輯：符乾江