企业官网建设流程全解析

Hello 算法：深入解析雜湊演算法——從衝突根源到設計原則與常見演算法

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

雜湊演算法（Hash Algorithm）決定了鍵值對在雜湊表中的分佈，是影響雜湊表查詢效能的核心因素。本篇基於《Hello 算法》「雜湊演算法」章節展開，結合倉庫內simple_hash.c、built_in_hash.py等原始碼，完整講解雜湊演算法的設計目標、四種基礎實現、質數取模原理、常見標準演算法（MD5/SHA 系列）以及程式語言內建雜湊值的行為差異，讀者讀完後將具備獨立設計、評估與選用雜湊演算法的能力。

為什麼需要重視雜湊演算法

前兩節（雜湊表、雜湊衝突）介紹了雜湊表的工作原理與衝突處理方法。然而，無論是開放定址還是鏈式位址，它們只能保證雜湊表可以在發生衝突時正常工作，而無法減少雜湊衝突的發生。

如果雜湊衝突過於頻繁，雜湊表的效能則會急劇劣化。對於鏈式位址雜湊表，理想情況下鍵值對均勻分佈在各個桶中，達到最佳查詢效率 $O(1)$；最差情況下所有鍵值對都儲存到同一個桶中，時間複雜度退化至 $O(n)$。

鍵值對的分佈情況由雜湊函式決定。回憶雜湊函式的計算步驟：先計算雜湊值，再對陣列長度取模：

index = hash(key) % capacity

觀察以上公式，當雜湊表容量capacity固定時，雜湊演算法hash()決定了輸出值，進而決定了鍵值對在雜湊表中的分佈情況。這意味著，為了降低雜湊衝突的發生機率，我們應當將注意力集中在雜湊演算法hash()的設計上。

雜湊演算法的目標

為了實現「既快又穩」的雜湊表資料結構，雜湊演算法應具備以下特點。

• 確定性：對於相同的輸入，雜湊演算法應始終產生相同的輸出。這樣才能確保雜湊表是可靠的。
• 效率高：計算雜湊值的過程應該足夠快。計算開銷越小，雜湊表的實用性越高。
• 均勻分佈：雜湊演算法應使得鍵值對均勻分佈在雜湊表中。分佈越均勻，雜湊衝突的機率就越低。

實際上，雜湊演算法除了可以用於實現雜湊表，還廣泛應用於其他領域中。

• 密碼儲存：為了保護使用者密碼的安全，系統通常不會直接儲存使用者的明文密碼，而是儲存密碼的雜湊值。當用戶輸入密碼時，系統會對輸入的密碼計算雜湊值，然後與儲存的雜湊值進行比較。如果兩者匹配，那麼密碼就被視為正確。
• 資料完整性檢查：資料傳送方可以計算資料的雜湊值並將其一同傳送；接收方可以重新計算接收到的資料的雜湊值，並與接收到的雜湊值進行比較。如果兩者匹配，那麼資料就被視為完整。

對於密碼學的相關應用，為了防止從雜湊值推導出原始密碼等逆向工程，雜湊演算法需要具備更高等級的安全特性。

• 單向性：無法透過雜湊值反推出關於輸入資料的任何資訊。
• 抗碰撞性：應當極難找到兩個不同的輸入，使得它們的雜湊值相同。
• 雪崩效應：輸入的微小變化應當導致輸出的顯著且不可預測的變化。

請注意，「均勻分佈」與「抗碰撞性」是兩個獨立的概念，滿足均勻分佈不一定滿足抗碰撞性。例如，在隨機輸入key下，雜湊函式key % 100可以產生均勻分佈的輸出。然而該雜湊演算法過於簡單，所有後兩位相等的key的輸出都相同，因此我們可以很容易地從雜湊值反推出可用的key，從而破解密碼。

雜湊演算法的設計：四種基礎實現

雜湊演算法的設計是一個需要考慮許多因素的複雜問題。然而對於某些要求不高的場景，我們也能設計一些簡單的雜湊演算法。

• 加法雜湊：對輸入的每個字元的 ASCII 碼進行相加，將得到的總和作為雜湊值。
• 乘法雜湊：利用乘法的不相關性，每輪乘以一個常數，將各個字元的 ASCII 碼累積到雜湊值中。
• 互斥或雜湊：將輸入資料的每個元素透過互斥或操作累積到一個雜湊值中。
• 旋轉雜湊：將每個字元的 ASCII 碼累積到一個雜湊值中，每次累積之前都會對雜湊值進行旋轉操作。

在《Hello 算法》倉庫中，這四種演算法以多種語言完整實現於 simple_hash.c、simple_hash.py、simple_hash.java 等文件中。以旋轉雜湊為例，其 C 語言實作如下（simple_hash.c）：

/* 旋轉哈希 */ int rotHash(char *key) { long long hash = 0; const int MODULUS = 1000000007; for (int i = 0; i < strlen(key); i++) { hash = ((hash << 4) ^ (hash >> 28) ^ (unsigned char)key[i]) % MODULUS; } return (int)hash; }

其他三種實作的核心迴圈如下（simple_hash.c）：

• 加法雜湊：hash = (hash + (unsigned char)key[i]) % MODULUS
• 乘法雜湊：hash = (31 * hash + (unsigned char)key[i]) % MODULUS
• 互斥或雜湊：hash ^= (unsigned char)key[i]，最終以hash & MODULUS收斂到合法範圍

觀察可以發現，每種雜湊演算法的最後一步都是對大質數 $1000000007$ 取模，以確保雜湊值在合適的範圍內。值得思考的是，為什麼要強調對質數取模，或者說對合數取模的弊端是什麼？

為什麼要對大質數取模

先給出結論：使用大質數作為模數，可以最大化地保證雜湊值的均勻分佈。因為質數不與其他數字存在公約數，可以減少因取模操作而產生的週期性模式，從而避免雜湊衝突。

舉個例子，假設我們選擇合數 $9$ 作為模數，它可以被 $3$ 整除，那麼所有可以被 $3$ 整除的key都會被對映到 $0$、$3$、$6$ 這三個雜湊值。

$$ \begin{aligned} \text{modulus} & = 9 \newline \text{key} & = { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \dots } \newline \text{hash} & = { 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6,\dots } \end{aligned} $$

如果輸入key恰好滿足這種等差數列的資料分佈，那麼雜湊值就會出現聚堆積，從而加重雜湊衝突。現在，假設將modulus替換為質數 $13$，由於key和modulus之間不存在公約數，因此輸出的雜湊值的均勻性會明顯提升。

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

值得說明的是，如果能夠保證key是隨機均勻分佈的，那麼選擇質數或者合數作為模數都可以，它們都能輸出均勻分佈的雜湊值。而當key的分佈存在某種週期性時，對合數取模更容易出現聚集現象。

總而言之，我們通常選取質數作為模數，並且這個質數最好足夠大，以儘可能消除週期性模式，提升雜湊演算法的穩健性。1000000007正是這樣一個常用的質數：它大於 $10^9$，遠超一般字串累積的雜湊值量級，同時又能容納在 32 位元整數的運算範圍內（simple_hash.c中配合long long中間變數使用）。

簡單雜湊演算法的局限性

不難發現，以上介紹的簡單雜湊演算法都比較「脆弱」，遠遠沒有達到雜湊演算法的設計目標。例如，由於加法和互斥或滿足交換律，因此加法雜湊和互斥或雜湊無法區分內容相同但順序不同的字串，如"abc"與"cba"會得到相同的雜湊值，這可能會加劇雜湊衝突，並引起一些安全問題。

常見的標準雜湊演算法

在實際中，我們通常會用一些標準雜湊演算法，例如 MD5、SHA-1、SHA-2 和 SHA-3 等。它們可以將任意長度的輸入資料對映到恆定長度的雜湊值。

近一個世紀以來，雜湊演算法處在不斷升級與最佳化的過程中。一部分研究人員努力提升雜湊演算法的效能，另一部分研究人員和駭客則致力於尋找雜湊演算法的安全性問題。下表展示了在實際應用中常見的雜湊演算法。

• MD5 和 SHA-1已多次被成功攻擊，因此它們被各類安全應用棄用。
• SHA-2 系列中的 SHA-256是最安全的雜湊演算法之一，仍未出現成功的攻擊案例，因此常用在各類安全應用與協議中。
• SHA-3相較 SHA-2 的實現開銷更低、計算效率更高，但目前使用覆蓋度不如 SHA-2 系列。

值得注意的是，這類密碼學雜湊演算法側重的是抗碰撞性與單向性，而非單純的查詢效率；而雜湊表內使用的內建雜湊則優先保證均勻分佈與計算效率。兩者在設計目標上各有側重，不能混為一談。

資料結構的雜湊值

我們知道，雜湊表的key可以是整數、小數或字串等資料型別。程式語言通常會為這些資料型別提供內建的雜湊演算法，用於計算雜湊表中的桶索引。以 Python 為例，可以呼叫hash()函式來計算各種資料型別的雜湊值；倉庫中對應的完整可執行程式位於 built_in_hash.py。

• 整數和布林量的雜湊值就是其本身。
• 浮點數和字串的雜湊值計算較為複雜，有興趣的讀者請自行學習。
• 元組的雜湊值是對其中每一個元素進行雜湊，然後將這些雜湊值組合起來，得到單一的雜湊值。
• 物件的雜湊值基於其記憶體位址生成。透過重寫物件的雜湊方法，可實現基於內容生成雜湊值。

!!! tip

請注意，不同程式語言的內建雜湊值計算函式的定義和方法不同。

Python

num = 3 hash_num = hash(num) # 整數 3 的雜湊值為 3 bol = True hash_bol = hash(bol) # 布林量 True 的雜湊值為 1 dec = 3.14159 hash_dec = hash(dec) # 小數 3.14159 的雜湊值為 326484311674566659 str = "Hello 演算法" hash_str = hash(str) # 字串“Hello 演算法”的雜湊值為 4617003410720528961 tup = (12836, "小哈") hash_tup = hash(tup) # 元組 (12836, '小哈') 的雜湊值為 1029005403108185979 obj = ListNode(0) hash_obj = hash(obj) # 節點物件 <ListNode object at 0x1058fd810> 的雜湊值為 274267521

C++

int num = 3; size_t hashNum = hash<int>()(num); // 整數 3 的雜湊值為 3 bool bol = true; size_t hashBol = hash<bool>()(bol); // 布林量 1 的雜湊值為 1 double dec = 3.14159; size_t hashDec = hash<double>()(dec); // 小數 3.14159 的雜湊值為 4614256650576692846 string str = "Hello 演算法"; size_t hashStr = hash<string>()(str); // 字串“Hello 演算法”的雜湊值為 15466937326284535026 // 在 C++ 中，內建 std::hash() 僅提供基本資料型別的雜湊值計算 // 陣列、物件的雜湊值計算需要自行實現

Java

int num = 3; int hashNum = Integer.hashCode(num); // 整數 3 的雜湊值為 3 boolean bol = true; int hashBol = Boolean.hashCode(bol); // 布林量 true 的雜湊值為 1231 double dec = 3.14159; int hashDec = Double.hashCode(dec); // 小數 3.14159 的雜湊值為 -1340954729 String str = "Hello 演算法"; int hashStr = str.hashCode(); // 字串“Hello 演算法”的雜湊值為 -727081396 Object[] arr = { 12836, "小哈" }; int hashTup = Arrays.hashCode(arr); // 陣列 [12836, 小哈] 的雜湊值為 1151158 ListNode obj = new ListNode(0); int hashObj = obj.hashCode(); // 節點物件 utils.ListNode@7dc5e7b4 的雜湊值為 2110121908

C#

int num = 3; int hashNum = num.GetHashCode(); // 整數 3 的雜湊值為 3; bool bol = true; int hashBol = bol.GetHashCode(); // 布林量 true 的雜湊值為 1; double dec = 3.14159; int hashDec = dec.GetHashCode(); // 小數 3.14159 的雜湊值為 -1340954729; string str = "Hello 演算法"; int hashStr = str.GetHashCode(); // 字串“Hello 演算法”的雜湊值為 -586107568; object[] arr = [12836, "小哈"]; int hashTup = arr.GetHashCode(); // 陣列 [12836, 小哈] 的雜湊值為 42931033; ListNode obj = new(0); int hashObj = obj.GetHashCode(); // 節點物件 0 的雜湊值為 39053774;

Go

// Go 未提供內建 hash code 函式

Swift

let num = 3 let hashNum = num.hashValue // 整數 3 的雜湊值為 9047044699613009734 let bol = true let hashBol = bol.hashValue // 布林量 true 的雜湊值為 -4431640247352757451 let dec = 3.14159 let hashDec = dec.hashValue // 小數 3.14159 的雜湊值為 -2465384235396674631 let str = "Hello 演算法" let hashStr = str.hashValue // 字串“Hello 演算法”的雜湊值為 -7850626797806988787 let arr = [AnyHashable(12836), AnyHashable("小哈")] let hashTup = arr.hashValue // 陣列 [AnyHashable(12836), AnyHashable("小哈")] 的雜湊值為 -2308633508154532996 let obj = ListNode(x: 0) let hashObj = obj.hashValue // 節點物件 utils.ListNode 的雜湊值為 -2434780518035996159

JavaScript / TypeScript

// JavaScript 未提供內建 hash code 函式

// TypeScript 未提供內建 hash code 函式

Dart

int num = 3; int hashNum = num.hashCode; // 整數 3 的雜湊值為 34803 bool bol = true; int hashBol = bol.hashCode; // 布林值 true 的雜湊值為 1231 double dec = 3.14159; int hashDec = dec.hashCode; // 小數 3.14159 的雜湊值為 2570631074981783 String str = "Hello 演算法"; int hashStr = str.hashCode; // 字串“Hello 演算法”的雜湊值為 468167534 List arr = [12836, "小哈"]; int hashArr = arr.hashCode; // 陣列 [12836, 小哈] 的雜湊值為 976512528 ListNode obj = new ListNode(0); int hashObj = obj.hashCode; // 節點物件 Instance of 'ListNode' 的雜湊值為 1033450432

Rust

use std::collections::hash_map::DefaultHasher; use std::hash::{Hash, Hasher}; let num = 3; let mut num_hasher = DefaultHasher::new(); num.hash(&mut num_hasher); let hash_num = num_hasher.finish(); // 整數 3 的雜湊值為 568126464209439262 let bol = true; let mut bol_hasher = DefaultHasher::new(); bol.hash(&mut bol_hasher); let hash_bol = bol_hasher.finish(); // 布林量 true 的雜湊值為 4952851536318644461 let dec: f32 = 3.14159; let mut dec_hasher = DefaultHasher::new(); dec.to_bits().hash(&mut dec_hasher); let hash_dec = dec_hasher.finish(); // 小數 3.14159 的雜湊值為 2566941990314602357 let str = "Hello 演算法"; let mut str_hasher = DefaultHasher::new(); str.hash(&mut str_hasher); let hash_str = str_hasher.finish(); // 字串“Hello 演算法”的雜湊值為 16092673739211250988 let arr = (&12836, &"小哈"); let mut tup_hasher = DefaultHasher::new(); arr.hash(&mut tup_hasher); let hash_tup = tup_hasher.finish(); // 元組 (12836, "小哈") 的雜湊值為 1885128010422702749 let node = ListNode::new(42); let mut hasher = DefaultHasher::new(); node.borrow().val.hash(&mut hasher); let hash = hasher.finish(); // 節點物件 RefCell { value: ListNode { val: 42, next: None } } 的雜湊值為15387811073369036852

C

// C 未提供內建 hash code 函式

Kotlin

val num = 3 val hashNum = num.hashCode() // 整數 3 的雜湊值為 3 val bol = true val hashBol = bol.hashCode() // 布林量 true 的雜湊值為 1231 val dec = 3.14159 val hashDec = dec.hashCode() // 小數 3.14159 的雜湊值為 -1340954729 val str = "Hello 演算法" val hashStr = str.hashCode() // 字串“Hello 演算法”的雜湊值為 -727081396 val arr = arrayOf<Any>(12836, "小哈") val hashTup = arr.hashCode() // 陣列 [12836, 小哈] 的雜湊值為 189568618 val obj = ListNode(0) val hashObj = obj.hashCode() // 節點物件 utils.ListNode@1d81eb93 的雜湊值為 495053715

Ruby

num = 3 hash_num = num.hash # 整數 3 的雜湊值為 -4385856518450339636 bol = true hash_bol = bol.hash # 布林量 true 的雜湊值為 -1617938112149317027 dec = 3.14159 hash_dec = dec.hash # 小數 3.14159 的雜湊值為 -1479186995943067893 str = "Hello 演算法" hash_str = str.hash # 字串“Hello 演算法”的雜湊值為 -4075943250025831763 tup = [12836, '小哈'] hash_tup = tup.hash # 元組 (12836, '小哈') 的雜湊值為 1999544809202288822 obj = ListNode.new(0) hash_obj = obj.hash # 節點物件 #<ListNode:0x000078133140ab70> 的雜湊值為 4302940560806366381

從以上對比可以看出各語言在 API 設計上的差異：Java、Kotlin、C#、Dart、Ruby 透過物件方法（如hashCode()、hash）提供內建雜湊；C++ 透過std::hash<T>模板特化提供；Rust 則需要配合DefaultHasher與Hashtrait 手動組裝；而 Go、JavaScript、TypeScript、C 並未提供可直接呼叫的內建 hash code 函式，需要自行實現。此外，同一資料型別在不同語言中的雜湊值輸出並不一致（例如 Java 中true的雜湊值為 1231，而 Python 中為 1），因此在跨語言場景下不應假設雜湊值具有可移植性。

為什麼只有不可變物件適合做 key

在許多程式語言中，只有不可變物件才可作為雜湊表的key。假如我們將串列（動態陣列）作為key，當串列的內容發生變化時，它的雜湊值也隨之改變，我們就無法在雜湊表中查詢到原先的value了。

雖然自定義物件（比如鏈結串列節點）的成員變數是可變的，但它是可雜湊的。這是因為物件的雜湊值通常是基於記憶體位址生成的，即使物件的內容發生了變化，但它的記憶體位址不變，雜湊值仍然是不變的。

隨機鹽值與 HashDoS 防護

細心的你可能發現在不同控制檯中執行程式時，輸出的雜湊值是不同的。這是因為 Python 直譯器在每次啟動時，都會為字串雜湊函式加入一個隨機的鹽（salt）值。這種做法可以有效防止 HashDoS 攻擊，提升雜湊演算法的安全性。

HashDoS 攻擊的思路是：如果雜湊函式是確定且公開的，攻擊者可以精心構造大量雜湊值相同的key（例如利用加法雜湊無法區分字元順序的特性），使它們全部落入同一個桶中，將雜湊表的查詢複雜度退化至 $O(n)$，從而癱瘓服務。隨機鹽值讓每次程式啟動的雜湊結果都不同，攻擊者無法預先構造針對性的碰撞輸入，從根源上瓦解了這類攻擊。這也正是本節開頭「均勻分佈」與「抗碰撞性」兩個概念相互獨立的最佳例證：Python 的內建字串雜湊本身分佈良好，但仍需透過加鹽來獲得額外的抗碰撞能力。

從演算法到雜湊表：倉庫中的完整閉環

雜湊演算法的設計最終要服務於雜湊表本體。在《Hello 算法》倉庫中，可以沿著 雜湊表 → 雜湊衝突 → 雜湊演算法 的章節脈絡，結合以下原始碼完整驗證這套理論：

• 簡單雜湊演算法的可執行示例：simple_hash.c 在main()中對字串"Hello 算法"依次輸出四種演算法的雜湊值，可以直接編譯運行對比；Python 版本見 simple_hash.py，Java 版本見 simple_hash.java。
• 鏈式位址的完整實現：hash_map_chaining.c 實現了每個桶為一個串列的雜湊表，並包含負載因子超過 $2/3$ 時擴容至 2 倍的邏輯，可直接觀察雜湊值分佈對查詢效能的影響。
• 開放定址的完整實現：hash_map_open_addressing.c 實現了含懶刪除（TOMBSTONE標記）的線性探測雜湊表，將陣列視為環形結構使用。
• 內建雜湊的可執行示例：built_in_hash.py 對整數、布林、浮點數、字串、元組與鏈結串列節點逐一輸出雜湊值。

小結與延伸閱讀

雜湊演算法是雜湊表效能與安全性的基石。本文從「衝突的根源在於hash()的設計」這一核心論點出發，完整覆蓋了雜湊演算法的三大目標（確定性、高效率、均勻分佈）、四種基礎實現、大質數取模的原理、標準雜湊演算法對比，以及程式語言內建雜湊值的行為差異與 HashDoS 防護機制。

對照本章的 重點回顧與問答，還有幾個關鍵要點值得牢記：雜湊表的 $O(1)$ 查詢效率建立在良好的雜湊分佈之上，一旦衝突加劇仍會退化至 $O(n)$；雜湊函式的最後一步通常是對陣列長度取模，因此擴容可以重新分配key以緩解衝突；內建雜湊表由於雜湊函式的常數開銷，在相同時間複雜度下未必比陣列、鏈結串列更快。讀者可以繼續研讀 hash_collision.md 中鏈式位址與開放定址的實作細節，以及 hash_map.md 中雜湊表的完整操作流程，形成從「為什麼需要好的雜湊」到「衝突如何被處理」的完整知識閉環。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo