什么是哈希/Hash

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

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

在一個cache系統中，需要實現一個域名白名單，域名為下列數據：

、、sohu.com等

該白名單需要在程序啟動時加載一次，主要執行查詢操作。請設計一個數據結構和相應的初始化查詢函數，使得檢索盡可能的快。（不能使用stl::map,等等key-value刑類庫）。

哈希是將任意長的輸入編程加密的固定長度輸出的過程。哈希并不等同于加密方法，因為無法解密哈希值來獲取原始數據。事實上哈希是一種單向加密函數。

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.

這些函數使用位運算使得每一個字符都對最后的函數值產生影響。

//ELF Hash Function

unsigned int ELFHash(char*str)

{

unsigned int hash=0;

unsigned int x=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語言使用的算數移位

hash^=(x>>24);

//清空28-31位。

hash&=~x;

}

}

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

return(hash&0×7FFFFFFF);

}

//該散列算法是基于貝爾實驗室的彼得J溫伯格的的研究。

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

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);

}

審核編輯：符乾江