什么是哈希？

哈希又稱作“散列”，是一種數(shù)學(xué)計(jì)算機(jī)程序，它接收任何一組任意長(zhǎng)度的輸入信息，通過(guò)哈希算法變換成固定長(zhǎng)度的數(shù)據(jù)指紋輸出形式，如字母和數(shù)字的組合，該輸出就是“哈希值”?？傮w而言，哈希算法可理解為一種消息摘要算法，將消息或數(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刑類庫(kù)）。

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

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

我們思考Berkeley DB （DB）的原理可以曉得，這個(gè)就是一個(gè)Hash的過(guò)程，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ì)于長(zhǎng)字符串和短字符串都很有效，字符串中每個(gè)字符都有同樣的作用，它巧妙地對(duì)字符的ASCII編碼值進(jìn)行計(jì)算，ELFhash函數(shù)對(duì)于能夠比較均勻地把字符串分布在散列表中。

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

常見哈希算法

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

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

例如計(jì)算

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

得到的結(jié)果將是

“db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90”。

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

審核編輯：符乾江