雜湊演算法 (Hash Function)#

雜湊演算法將任意長度的資料映射為固定長度的雜湊值，廣泛應用於加密、校驗、分布式系統等領域。

優秀雜湊演算法的特性#

1. 單向性：無法從雜湊值反推原始資料
2. 敏感性：原始資料微小改變，雜湊值大幅變化
3. 低衝突：不同資料產生相同雜湊值的概率極低
4. 高效率：即使處理大量資料也能快速計算

常見雜湊演算法：MD5、SHA-1、SHA-256、CRC 等

好的雜湊函數長什麼樣：字串雜湊與乘數 31#

前面列的四個特性是「驗收標準」，但實際要寫一個雜湊函數時，可以聚焦在兩個最關鍵的要求：

1. 分佈均勻（雪崩效應）：輸入只要有一點點變動，輸出就要大幅改變，讓雜湊值盡量平均散落在整個值域，不擠在少數幾個位置。
2. 計算快：雜湊會被海量呼叫，每次計算都得便宜。

最經典的字串雜湊，就是逐字元累進：

var hash = 0
for (c in s) {
    // c.code 取得字元碼；Kotlin 的 Int 是 32 位定長整數，
    // 乘加溢位時自然在 32-bit 內環繞，正好等同 Java 的行為，不需額外遮罩
    hash = 31 * hash + c.code
}

這正是 Java String.hashCode() 的做法——在 Kotlin/JVM 上，Int 的 32 位溢位環繞語意與 Java 完全一致，所以這段程式碼可以直接對齊 Java 的雜湊值（Python 因整數是任意精度、不會溢位，反而得手動加上 & 0xFFFFFFFF 遮罩才能重現）。重點在那個神奇的乘數 31：

• 計算便宜：31 * hash 可被編譯器優化成位移減法 (hash shl 5) - hash，一次乘法變成「移位 + 減法」，幾乎不花成本。
• 分佈良好：31 是奇質數，每多一個字元就把舊值放大 31 倍再疊加，讓不同字串的雜湊值充分散開，達到雪崩效應。

為什麼不選 2 的次方當乘數？因為乘以 2 的次方等同於左移，低位會被持續推走、資訊流失，雜湊值容易撞在一起。選一個「接近 2 的次方、但又是奇質數」的 31，剛好兼顧速度與分佈。

資訊指紋：雜湊作為「唯一標識」#

雜湊還有一個極重要的面向：把任意長度的資料，透過雜湊（如 MD5、SHA）映射成一段定長、近乎唯一的「資訊指紋」。

以 128-bit 指紋為例，它能表示約 2^128 ≈ 3.4×10^38 個不同的值——這個數量大到，幾乎可以為世界上每一份資料都分到一個獨一無二的指紋。

這個「指紋」有三個關鍵性質，各自對應一類應用：

• 近乎唯一 ➡️ 資料的身分證：可用指紋當作資料的識別碼，做檔案比對去重；爬蟲在判斷網址是否抓過時，與其存一條條又長又佔空間的 URL，不如改存其 64-bit 指紋，省下大量記憶體。
• 不可逆 ➡️ 保護原文：無法從指紋反推回原始內容，所以密碼資料庫只存密碼的指紋；就算資料庫外洩，攻擊者拿到的也只是指紋，無法直接得到原始密碼。
• 雪崩效應 ➡️ 偵測篡改：內容只要差一個位元，指紋就天差地別，因此非常適合用來校驗資料有沒有被改動（呼應後面的「資料校驗」應用）。

生日問題：碰撞機率到底多低#

既然不同內容可能撞到同一指紋（碰撞），那實務上把碰撞「當成幾乎不會發生」，到底站不站得住腳？

直覺上會覺得碰撞很容易——這就像「生日問題」：一個房間只要 23 個人，就有過半機率有兩人同一天生日，比多數人想像的容易得多。但反過來算，對 128-bit 指紋而言，要累積到約 2^64（大約 1800 億億，即 1.8×10^19）個不同指紋，才會有 50% 機率出現一次碰撞。

換句話說，除非你的資料量逼近天文數字，否則碰撞機率低到可以忽略——這就是「為什麼實務上可把雜湊碰撞當成幾乎不發生」的理論依據。

由鴿籠原理可知，把無限多的輸入塞進有限的指紋空間，碰撞不可能完全避免。但一個分佈夠均勻的好雜湊，能把碰撞機率壓到低到可忽略——這跟雜湊表理論裡「碰撞無法消滅、只能妥善處理」的觀點是同一回事。

安全加密#

密碼存儲#

錯誤做法：明文存儲密碼（如 2011 年 CSDN 事件）

正確做法：存儲密碼的雜湊值

import java.security.MessageDigest

fun hashPassword(password: String, salt: String): String {
    val digest = MessageDigest.getInstance("SHA-256")
    val bytes = digest.digest((password + salt).toByteArray())
    // 每個 byte 轉成兩位十六進位字串（and 0xFF 避免負 byte 被符號延伸）
    return bytes.joinToString("") { "%02x".format(it.toInt() and 0xFF) }
}

為何無法破解？#

以 MD5 為例，輸出 128 位，有 2^128 種可能。即使存在衝突，在有限時間內找到衝突的概率極低。

字典攻擊：攻擊者預先計算常見密碼的雜湊值，進行比對。

防禦方法：加鹽（Salt）—— 將隨機字串與密碼組合後再雜湊。

唯一識別#

海量圖片去重#

1. 不能用檔名判斷（檔名相同內容可能不同）
2. 不能逐 byte 比對（太慢）

解決方案：

1. 從圖片取特徵部分（頭 100 位元組 + 中間 100 位元組 + 尾 100 位元組）
2. 計算 MD5 作為唯一識別
3. 存入雜湊表，快速查找

資料校驗#

BT 下載檔案校驗#

1. 大檔案分成多個小塊並行下載
2. 每個檔案塊的雜湊值預先存在種子檔案中
3. 下載完成後，計算檔案塊雜湊值並比對
4. 不一致則重新下載該塊

雜湊值對資料極度敏感，任何篡改都會導致雜湊值完全不同。

負載均衡#

會話粘滯（Session Sticky）#

問題：如何確保同一使用者的請求總是路由到同一伺服器？

方案一：維護映射表（用戶端 IP ➡️ 伺服器編號）

• 缺點：佔記憶體、維護成本高

方案二：雜湊計算

// String.hashCode() 可能為負，用 floorMod 確保索引落在 [0, serverCount)
val serverId = Math.floorMod(clientIp.hashCode(), serverCount)

• 優點：無需存儲映射關係

資料分片#

統計 1TB 日誌中關鍵詞頻率#

問題：資料太大，單機無法處理

解決方案：

1. 準備 n 台機器
2. 對每個關鍵詞計算 hash(keyword) % n
3. 將關鍵詞發送到對應機器
4. 各機器獨立統計，最後彙總

這就是 MapReduce 的基本思想！

海量圖片分片存儲#

1 億張圖片無法在單機建立雜湊表（記憶體不夠）

解決方案：

1. 估算：每張圖片元資料約 152 位元組，2GB 記憶體可存約 1000 萬張
2. 需要約 10 台機器
3. 按 hash(image_id) % 10 分配到各機器

分布式存儲#

問題：擴容時資料遷移#

假設原有 10 台機器，資料按 hash(key) % 10 分配。 新增 1 台機器後，需按 hash(key) % 11 重新分配。 幾乎所有資料都要搬移！

一致性雜湊 (Consistent Hashing)#

核心思想：

1. 將雜湊值範圍 [0, MAX] 想像成一個環
2. 將環分成 m 個小區間（m » 機器數 k）
3. 每台機器負責 m/k 個區間
4. 新增機器時，只需搬移部分區間的資料

一致性雜湊的優勢：

• 新增/移除節點時，只影響相鄰節點
• 資料搬移量最小化
• 廣泛應用於 Redis Cluster、Cassandra 等分布式系統

雜湊演算法總結#