C++哈希算法

在上兩節(jié)中，我們了解了哈希表的工作原理和哈希沖突的處理方法。然而無(wú)論是開(kāi)放尋址還是鏈地址法，它們只能保證哈希表可以在發(fā)生沖突時(shí)正常工作，但無(wú)法減少哈希沖突的發(fā)生。

如果哈希沖突過(guò)于頻繁，哈希表的性能則會(huì)急劇劣化。如圖 6-7 所示，對(duì)于鏈地址哈希表，理想情況下鍵值對(duì)平均分布在各個(gè)桶中，達(dá)到最佳查詢(xún)效率；最差情況下所有鍵值對(duì)都被存儲(chǔ)到同一個(gè)桶中，時(shí)間復(fù)雜度退化至 O(n) 。

圖 6-7   哈希沖突的最佳與最差情況

鍵值對(duì)的分布情況由哈希函數(shù)決定。回憶哈希函數(shù)的計(jì)算步驟，先計(jì)算哈希值，再對(duì)數(shù)組長(zhǎng)度取模：

index = hash(key) % capacity

觀察以上公式，當(dāng)哈希表容量 capacity 固定時(shí)，哈希算法 hash() 決定了輸出值，進(jìn)而決定了鍵值對(duì)在哈希表中的分布情況。

這意味著，為了減小哈希沖突的發(fā)生概率，我們應(yīng)當(dāng)將注意力集中在哈希算法 hash() 的設(shè)計(jì)上。

6.3.1   哈希算法的目標(biāo)?

為了實(shí)現(xiàn)“既快又穩(wěn)”的哈希表數(shù)據(jù)結(jié)構(gòu)，哈希算法應(yīng)包含以下特點(diǎn)。

• 確定性：對(duì)于相同的輸入，哈希算法應(yīng)始終產(chǎn)生相同的輸出。這樣才能確保哈希表是可靠的。
• 效率高：計(jì)算哈希值的過(guò)程應(yīng)該足夠快。計(jì)算開(kāi)銷(xiāo)越小，哈希表的實(shí)用性越高。
• 均勻分布：哈希算法應(yīng)使得鍵值對(duì)平均分布在哈希表中。分布越平均，哈希沖突的概率就越低。

實(shí)際上，哈希算法除了可以用于實(shí)現(xiàn)哈希表，還廣泛應(yīng)用于其他領(lǐng)域中。

• 密碼存儲(chǔ)：為了保護(hù)用戶(hù)密碼的安全，系統(tǒng)通常不會(huì)直接存儲(chǔ)用戶(hù)的明文密碼，而是存儲(chǔ)密碼的哈希值。當(dāng)用戶(hù)輸入密碼時(shí)，系統(tǒng)會(huì)對(duì)輸入的密碼計(jì)算哈希值，然后與存儲(chǔ)的哈希值進(jìn)行比較。如果兩者匹配，那么密碼就被視為正確。
• 數(shù)據(jù)完整性檢查：數(shù)據(jù)發(fā)送方可以計(jì)算數(shù)據(jù)的哈希值并將其一同發(fā)送；接收方可以重新計(jì)算接收到的數(shù)據(jù)的哈希值，并與接收到的哈希值進(jìn)行比較。如果兩者匹配，那么數(shù)據(jù)就被視為完整的。

對(duì)于密碼學(xué)的相關(guān)應(yīng)用，為了防止從哈希值推導(dǎo)出原始密碼等逆向工程，哈希算法需要具備更高等級(jí)的安全特性。

• 抗碰撞性：應(yīng)當(dāng)極其困難找到兩個(gè)不同的輸入，使得它們的哈希值相同。
• 雪崩效應(yīng)：輸入的微小變化應(yīng)當(dāng)導(dǎo)致輸出的顯著且不可預(yù)測(cè)的變化。

請(qǐng)注意，“均勻分布”與“抗碰撞性”是兩個(gè)獨(dú)立的概念，滿(mǎn)足均勻分布不一定滿(mǎn)足抗碰撞性。例如，在隨機(jī)輸入 key 下，哈希函數(shù) key % 100 可以產(chǎn)生均勻分布的輸出。然而該哈希算法過(guò)于簡(jiǎn)單，所有后兩位相等的 key 的輸出都相同，因此我們可以很容易地從哈希值反推出可用的 key ，從而破解密碼。

6.3.2   哈希算法的設(shè)計(jì)?

哈希算法的設(shè)計(jì)是一個(gè)需要考慮許多因素的復(fù)雜問(wèn)題。然而對(duì)于某些要求不高的場(chǎng)景，我們也能設(shè)計(jì)一些簡(jiǎn)單的哈希算法。

• 加法哈希：對(duì)輸入的每個(gè)字符的 ASCII 碼進(jìn)行相加，將得到的總和作為哈希值。
• 乘法哈希：利用了乘法的不相關(guān)性，每輪乘以一個(gè)常數(shù)，將各個(gè)字符的 ASCII 碼累積到哈希值中。
• 異或哈希：將輸入數(shù)據(jù)的每個(gè)元素通過(guò)異或操作累積到一個(gè)哈希值中。
• 旋轉(zhuǎn)哈希：將每個(gè)字符的 ASCII 碼累積到一個(gè)哈希值中，每次累積之前都會(huì)對(duì)哈希值進(jìn)行旋轉(zhuǎn)操作。

simple_hash.cpp

/* 加法哈希 */
int addHash(string key) {
    long long hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash = (hash + (int)c) % MODULUS;
    }
    return (int)hash;
}

/* 乘法哈希 */
int mulHash(string key) {
    long long hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash = (31 * hash + (int)c) % MODULUS;
    }
    return (int)hash;
}

/* 異或哈希 */
int xorHash(string key) {
    int hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash ^= (int)c;
    }
    return hash & MODULUS;
}

/* 旋轉(zhuǎn)哈希 */
int rotHash(string key) {
    long long hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash = ((hash << 4) ^ (hash >> 28) ^ (int)c) % MODULUS;
    }
    return (int)hash;
}

觀察發(fā)現(xiàn)，每種哈希算法的最后一步都是對(duì)大質(zhì)數(shù) 1000000007 取模，以確保哈希值在合適的范圍內(nèi)。值得思考的是，為什么要強(qiáng)調(diào)對(duì)質(zhì)數(shù)取模，或者說(shuō)對(duì)合數(shù)取模的弊端是什么？這是一個(gè)有趣的問(wèn)題。

先拋出結(jié)論：當(dāng)我們使用大質(zhì)數(shù)作為模數(shù)時(shí)，可以最大化地保證哈希值的均勻分布。因?yàn)橘|(zhì)數(shù)不會(huì)與其他數(shù)字存在公約數(shù)，可以減少因取模操作而產(chǎn)生的周期性模式，從而避免哈希沖突。

舉個(gè)例子，假設(shè)我們選擇合數(shù) 9 作為模數(shù)，它可以被 3 整除。那么所有可以被 3 整除的 key 都會(huì)被映射到 0、3、6 這三個(gè)哈希值。

$\begin{array}{cc}\text{<br>}\text{modulus}& =9\mathrm{<br>}\\ \text{key}& <br>=<br>\{0,3,6,9,12,15,18,21,24,27,30,33,\dots \}\\ \text{hash}& <br>=\{0,3,6,0,3,6,0,3,6,0,3,6,\dots \}<br>\end{array}$

如果輸入 key 恰好滿(mǎn)足這種等差數(shù)列的數(shù)據(jù)分布，那么哈希值就會(huì)出現(xiàn)聚堆，從而加重哈希沖突?，F(xiàn)在，假設(shè)將 modulus 替換為質(zhì)數(shù) 13 ，由于 key 和 modulus 之間不存在公約數(shù)，輸出的哈希值的均勻性會(huì)明顯提升。

$\begin{array}{cc}\text{modulus}& <br>=13\\ \text{key}& <br>=\{0,3,6,9,12,15,18,21,24,27,30,33,\dots \}\\ \text{hash}& <br>=\{0,3,6,9,12,2,5,8,11,1,4,7,\dots \}\end{array}$

值得說(shuō)明的是，如果能夠保證 key 是隨機(jī)均勻分布的，那么選擇質(zhì)數(shù)或者合數(shù)作為模數(shù)都是可以的，它們都能輸出均勻分布的哈希值。而當(dāng) key 的分布存在某種周期性時(shí)，對(duì)合數(shù)取模更容易出現(xiàn)聚集現(xiàn)象。

總而言之，我們通常選取質(zhì)數(shù)作為模數(shù)，并且這個(gè)質(zhì)數(shù)最好足夠大，以盡可能消除周期性模式，提升哈希算法的穩(wěn)健性。

常見(jiàn)哈希算法

不難發(fā)現(xiàn)，以上介紹的簡(jiǎn)單哈希算法都比較“脆弱”，遠(yuǎn)遠(yuǎn)沒(méi)有達(dá)到哈希算法的設(shè)計(jì)目標(biāo)。例如，由于加法和異或滿(mǎn)足交換律，因此加法哈希和異或哈希無(wú)法區(qū)分內(nèi)容相同但順序不同的字符串，這可能會(huì)加劇哈希沖突，并引起一些安全問(wèn)題。

在實(shí)際中，我們通常會(huì)用一些標(biāo)準(zhǔn)哈希算法，例如 MD5、SHA-1、SHA-2、SHA3 等。它們可以將任意長(zhǎng)度的輸入數(shù)據(jù)映射到恒定長(zhǎng)度的哈希值。

近一個(gè)世紀(jì)以來(lái)，哈希算法處在不斷升級(jí)與優(yōu)化的過(guò)程中。一部分研究人員努力提升哈希算法的性能，另一部分研究人員和黑客則致力于尋找哈希算法的安全性問(wèn)題。表 6-2 展示了在實(shí)際應(yīng)用中常見(jiàn)的哈希算法。

• MD5 和 SHA-1 已多次被成功攻擊，因此它們被各類(lèi)安全應(yīng)用棄用。
• SHA-2 系列中的 SHA-256 是最安全的哈希算法之一，仍未出現(xiàn)成功的攻擊案例，因此常被用在各類(lèi)安全應(yīng)用與協(xié)議中。
• SHA-3 相較 SHA-2 的實(shí)現(xiàn)開(kāi)銷(xiāo)更低、計(jì)算效率更高，但目前使用覆蓋度不如 SHA-2 系列。

表 6-2   常見(jiàn)的哈希算法

數(shù)據(jù)結(jié)構(gòu)的哈希值

我們知道，哈希表的 key 可以是整數(shù)、小數(shù)或字符串等數(shù)據(jù)類(lèi)型。編程語(yǔ)言通常會(huì)為這些數(shù)據(jù)類(lèi)型提供內(nèi)置的哈希算法，用于計(jì)算哈希表中的桶索引。以 Python 為例，我們可以調(diào)用 hash() 函數(shù)來(lái)計(jì)算各種數(shù)據(jù)類(lèi)型的哈希值。

• 整數(shù)和布爾量的哈希值就是其本身。
• 浮點(diǎn)數(shù)和字符串的哈希值計(jì)算較為復(fù)雜，有興趣的同學(xué)請(qǐng)自行學(xué)習(xí)。
• 元組的哈希值是對(duì)其中每一個(gè)元素進(jìn)行哈希，然后將這些哈希值組合起來(lái)，得到單一的哈希值。
• 對(duì)象的哈希值基于其內(nèi)存地址生成。通過(guò)重寫(xiě)對(duì)象的哈希方法，可實(shí)現(xiàn)基于內(nèi)容生成哈希值。

Tip

請(qǐng)注意，不同編程語(yǔ)言的內(nèi)置哈希值計(jì)算函數(shù)的定義和方法不同。

built_in_hash.cpp

int num = 3;
size_t hashNum = hash<int>()(num);
// 整數(shù) 3 的哈希值為 3

bool bol = true;
size_t hashBol = hash<bool>()(bol);
// 布爾量 1 的哈希值為 1

double dec = 3.14159;
size_t hashDec = hash<double>()(dec);
// 小數(shù) 3.14159 的哈希值為 4614256650576692846

string str = "Hello 算法";
size_t hashStr = hash<string>()(str);
// 字符串 Hello 算法 的哈希值為 15466937326284535026

// 在 C++ 中，內(nèi)置 std:hash() 僅提供基本數(shù)據(jù)類(lèi)型的哈希值計(jì)算
// 數(shù)組、對(duì)象的哈希值計(jì)算需要自行實(shí)現(xiàn)

在許多編程語(yǔ)言中，只有不可變對(duì)象才可作為哈希表的 key 。假如我們將列表（動(dòng)態(tài)數(shù)組）作為 key ，當(dāng)列表的內(nèi)容發(fā)生變化時(shí)，它的哈希值也隨之改變，我們就無(wú)法在哈希表中查詢(xún)到原先的 value 了。

雖然自定義對(duì)象（比如鏈表節(jié)點(diǎn)）的成員變量是可變的，但它是可哈希的。這是因?yàn)閷?duì)象的哈希值通常是基于內(nèi)存地址生成的，即使對(duì)象的內(nèi)容發(fā)生了變化，但它的內(nèi)存地址不變，哈希值仍然是不變的。

細(xì)心的你可能發(fā)現(xiàn)在不同控制臺(tái)中運(yùn)行程序時(shí)，輸出的哈希值是不同的。這是因?yàn)?Python 解釋器在每次啟動(dòng)時(shí)，都會(huì)為字符串哈希函數(shù)加入一個(gè)隨機(jī)的鹽（Salt）值。這種做法可以有效防止 HashDoS 攻擊，提升哈希算法的安全性。