雜湊演算法#

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

優秀雜湊演算法的特性#

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

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

應用一：安全加密#

密碼存儲#

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

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

import hashlib

def hash_password(password, salt):
    return hashlib.sha256((password + salt).encode()).hexdigest()

為何無法破解？#

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

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

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

應用二：唯一標識#

海量圖片去重#

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

解決方案：

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

應用三：資料校驗#

BT 下載檔案校驗#

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

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

應用四：負載均衡#

會話粘滯（Session Sticky）#

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

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

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

方案二：雜湊計算

server_id = hash(client_ip) % server_count

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

應用五：資料分片#

統計 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 等分布式系統

雜湊演算法總結#