什么是哈希/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í)行查詢操作。請?jiān)O(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的初始化查詢函數(shù)，使得檢索盡可能的快。（不能使用stl::map,等等key-value刑類庫）。

哈希是將任意長的輸入編程加密的固定長度輸出的過程。哈希并不等同于加密方法，因?yàn)闊o法解密哈希值來獲取原始數(shù)據(jù)。事實(shí)上哈希是一種單向加密函數(shù)。

With a hash function,data on the Internet can be saved as a fixed length string.One method is SHA-256(secure hash algorithm-256 bits).SHA-256 is the successor of SHA-1,and the output of SHA-1 is 160 bits.

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

//ELF Hash Function

unsigned int ELFHash(char*str)

{

unsigned int hash=0;

unsigned int x=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ì)被移出，因此要有如下處理。

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

hash^=(x>>24);

//清空28-31位。

hash&=~x;

}

}

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

return(hash&0×7FFFFFFF);

}

//該散列算法是基于貝爾實(shí)驗(yàn)室的彼得J溫伯格的的研究。

//在Compilers一書中（原則，技術(shù)和工具），建議采用這個(gè)算法的散列函數(shù)的哈希方法。

unsigned int PJWHash(const char*str)

{

unsigned int BitsInUnignedInt=(unsigned int)(sizeof(unsigned int)*8);

unsigned int ThreeQuarters=(unsigned int)((BitsInUnignedInt*3)/4);

unsigned int OneEighth=(unsigned int)(BitsInUnignedInt/8);

unsigned int HighBits=(unsigned int)(0xFFFFFFFF)<<(BitsInUnignedInt

-OneEighth);

unsigned int hash=0;

unsigned int test=0;

while(*str)

{

hash=(hash<)+(*str++);<>

if((test=hash&HighBits)!=0)

{

hash=((hash^(test>>ThreeQuarters))&(~HighBits));

}

}

return(hash&0x7FFFFFFF);

}

審核編輯：符乾江