Hello 算法：深入解析雜湊演算法——從衝突根源到設計原則與常見演算法-北京尧图网络

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 系列。MD5SHA-1SHA-2SHA-3推出時間1992199520022008輸出長度128 bit160 bit256/512 bit224/256/384/512 bit雜湊衝突較多較多很少很少安全等級低已被成功攻擊低已被成功攻擊高高應用已被棄用仍用於資料完整性檢查已被棄用加密貨幣交易驗證、數字簽名等可用於替代 SHA-2值得注意的是這類密碼學雜湊演算法側重的是抗碰撞性與單向性而非單純的查詢效率而雜湊表內使用的內建雜湊則優先保證均勻分佈與計算效率。兩者在設計目標上各有側重不能混為一談。資料結構的雜湊值我們知道雜湊表的key可以是整數、小數或字串等資料型別。程式語言通常會為這些資料型別提供內建的雜湊演算法用於計算雜湊表中的桶索引。以 Python 為例可以呼叫hash()函式來計算各種資料型別的雜湊值倉庫中對應的完整可執行程式位於 built_in_hash.py。整數和布林量的雜湊值就是其本身。浮點數和字串的雜湊值計算較為複雜有興趣的讀者請自行學習。元組的雜湊值是對其中每一個元素進行雜湊然後將這些雜湊值組合起來得到單一的雜湊值。物件的雜湊值基於其記憶體位址生成。透過重寫物件的雜湊方法可實現基於內容生成雜湊值。!!! tip請注意不同程式語言的內建雜湊值計算函式的定義和方法不同。Pythonnum 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 的雜湊值為 274267521Cint num 3; size_t hashNum hashint()(num); // 整數 3 的雜湊值為 3 bool bol true; size_t hashBol hashbool()(bol); // 布林量 1 的雜湊值為 1 double dec 3.14159; size_t hashDec hashdouble()(dec); // 小數 3.14159 的雜湊值為 4614256650576692846 string str Hello 演算法; size_t hashStr hashstring()(str); // 字串“Hello 演算法”的雜湊值為 15466937326284535026 // 在 C 中內建 std::hash() 僅提供基本資料型別的雜湊值計算 // 陣列、物件的雜湊值計算需要自行實現Javaint 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.ListNode7dc5e7b4 的雜湊值為 2110121908C#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 函式Swiftlet 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 的雜湊值為 -2434780518035996159JavaScript / TypeScript// JavaScript 未提供內建 hash code 函式// TypeScript 未提供內建 hash code 函式Dartint 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 的雜湊值為 1033450432Rustuse 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 } } 的雜湊值為15387811073369036852C// C 未提供內建 hash code 函式Kotlinval 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 arrayOfAny(12836, 小哈) val hashTup arr.hashCode() // 陣列 [12836, 小哈] 的雜湊值為 189568618 val obj ListNode(0) val hashObj obj.hashCode() // 節點物件 utils.ListNode1d81eb93 的雜湊值為 495053715Rubynum 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::hashT模板特化提供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.pyJava 版本見 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

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

相关推荐

GE图引擎内存管理接口

Impeccable Android 平台设计指南：以 Material 3 为准绳的原生 Android 界面审查与验证实践

FreeCAD Placement 对象完全指南：位置与姿态的 Python API 详解

更多资讯

考虑多容量电动汽车接入的配电网承载能力评估附Matlab代码

Spring Boot在线视频教育平台：视频上传、转码、鉴权播放全链路实战

猪源分泌素多肽定制：从序列解析到C端酰胺化的关键点

2026 科普：Work Agent 品类概念、核心能力与代表性产品

magnitude不是CLI工具：轻量向量检索库的核心原理与实战

基于类Sagnac干涉仪的矢量光束生成与VirtualLab Fusion仿真

今日更新

CopilotKit Vue Demo 与 React Demo 的 Parity 实现指南：路由、运行时端点与交互语义的全框架对齐

Harbor RBAC 实战：db_auth 模式下非管理员用户管理项目成员的完整验证与权限模型解析

STM32平衡车纯平衡程序从拆包到参数整定的完整调试指南

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？