什么是哈希/ Hash

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

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

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

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

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

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

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

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

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

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

// ELF Hash Function

unsignedintELFHash(char*str)

{

unsignedinthash = 0;

unsignedintx= 0;

while(*str)

{

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

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

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

//該處理，如果對(duì)于字符串(a-z或者A-Z)就會(huì)僅僅影響5-8位，否則會(huì)影響5-31位，因?yàn)?a href="http://www.brongaenegriffin.com/soft/data/21-24/" target="_blank">C語言使用的算數(shù)移位

hash ^= (x >> 24);

//清空28-31位。

hash &= ~x;

}

}

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

return(hash & 0×7FFFFFFF);

}

常見哈希算法

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

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

例如計(jì)算

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

得到的結(jié)果將是

“db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90”。

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

審核編輯：符乾江