雜湊是什麼？為什麼雜湊出來的字串是固定的？
雜湊就像果汁機，丟入任意字串、檔案，能跑出一組固定大小，但看起來完全隨機的字串；雜湊還有個特性，即便只改一個字，也能產生完全不同的雜湊值。這篇文章帶你看出為什麼小字串或大檔案都可以算出一樣長度的雜湊值，也帶你看出是怎麼改一個字就算出很大的不同的字串。
雜湊怎麼做
怕你不懂程式碼，先用數學方式定義一下一個簡單的雜湊函數 h：
$h(x) = \left(\sum_{i=0}^{n-1} \text{ASCII}(x_i) \times (i+1)\right) \bmod 1000$
其中 $x$ 是輸入的字串，$x_i$ 是第 $i$ 個字元、$n$ 是字串長度、$\text{ASCII}(x_i)$ 是指第 $i$ 個字元的 ASCII 值。
我們來算一下把 A 丟進去的樣子：$h(\text{"A"})$ 就是把 A 的 ASCII 值取出來（65）乘上自己的字元位置（1）最後除以 1000 取餘數：
$h(\text{"A"}) = (65 \times 1) \bmod 1000$
$= 65$
看懂一個字元的例子，我們來看三個字元的例子，把 CAT 丟進去會怎樣？
$h(\text{"CAT"}) = (67 \times 1 + 65 \times 2 + 84 \times 3) \bmod 1000$
$= (67 + 130 + 252) \bmod 1000$
$= 449 \bmod 1000 = 449$
接著給你一段 JS 程式碼，試試看找出 "CAT"、"CAP" 等字串的結果吧：
function h(text) {
let sum = 0;
for (let i = 0; i < text.length; i++) {
sum += text.charCodeAt(i) * (i + 1);
}
return sum % 1000;
}
console.log(h('A')); // --> 65
console.log(h('CAT')); // --> 449
console.log(h('CAP')); // --> 437
接著我們回顧一下剛剛這個雜湊函數 $h$ 的特性：
- 確定性：對於相同輸入，雜湊函數總是產生相同的雜湊值。（
h(A)永遠等於 65）。 - 固定長度輸出：我們最後取了一個 1000 的餘數，可以確保這個值一定介於 0~999 之間，（只要前面補零）長度是固定的。
- 不可逆性：給你一個雜湊值 449，你沒辦法直接用算的算回原本的值是 CAT。（你只能一直湊單字來試試看）不過這個例子很爛，A 的 ASCII 值就是 65，所以看到 65 你就可以猜猜看是不是 A 的。
- 抗碰撞性：在一個設計良好的雜湊函數中，要很難找到兩個不同輸入卻得到相同輸出。這個函數在這裡就做得很不好，例如 h('A') 等於 65、h('ZAAAN') 也等於 65。
- 雪崩效應（或敏感性）：在一個設計良好的雜湊函數中，要改動原始字串的一小部分也能得到很大的不同。但在這個函數裡也做得不好，例如 h('CAT') 得到 449、h('BAT') 得到 448。
但從這邊我們還是可以理解：
- 雜湊函數計算速度很快，基本上就是簡單的數學
- 不管是小字串還是大檔案，轉成文字（轉成位元組 bytes 序列）後逐一處理，最後取餘數（取模/裁切），是可以把大檔案轉成小字串的
好的雜湊函數怎麼做
剛剛那個 h 函數只是簡單的加法和乘法，如果加上位元運算，就能有更好的雪崩效應。先來看基本的位元運算，首先先知道 A 和 B 的 ASCII 值分別為 65 和 66，寫成二進位後就是：
"A" → 01000001 (ASCII 值 65)
"B" → 01000010 (ASCII 值 66)
接著來看 XOR 運算子、<< 左移位、>> 右移位：
// XOR 運算子 - 相同為 0，不同為 1
01000001 // A
01000010 // B
--------
00000011
// 左移位 (<<) - 所有位元往左移
01000001 << 2 = 00000100 // 相當於乘以 4 (2^2)
// 右移位 (>>) - 所有位元往右移
01000001 >> 1 = 00100000 // 相當於除以 2 (2^1)
接著來看這段新的雜湊函數 h2：
function h2(text) {
let hash = 0;
for (let i = 0; i < text.length; i++) {
const c = text.charCodeAt(i);
hash = (hash << 3) + hash;
hash = hash ^ c;
hash = hash ^ (hash >> 4);
hash = hash * 17;
hash >>>= 0;
}
return hash & 0xFF;
}
再算一次剛剛的幾個值
- h2('A') = 149
- h2('CAT') = 183
- h2('BAT') = 90
這次 CAT 和 BAT 差一個字母但就差很多。
但為什麼雜湊可以用左右移位、XOR 運算和乘以質數就達到這些特性呢？
左移位：把差異「放大」
這是最簡單的一部分，左移 3 位就相當於乘上 $2^3$，也就是乘以 8。原先 A（65）和 B（66）只差 1，放大 8 倍就差 8 了。
質數：分布更均勻
這個就很好直觀理解，也很好舉例。非質數的乘積通常會有明顯週期性，例如 1~10 的每一個數乘上 6 後取 10 的餘數：
for (let i=1; i<=10; i++) {
console.log( (i*6) % 10 );
}
你會得到：6, 2, 8, 4, 0, 6, 2, 8, 4, 0，有明顯的週期。
但乘以 7 的話再取 10 的餘數：
for (let i=1; i<=10; i++) {
console.log( (i*7) % 10);
}
你會得到： 7, 4, 1, 8, 5, 2, 9, 6, 3, 0，看起來「隨機」多了。
XOR：雪崩、平衡
XOR 的基本運算就是：兩個不同就輸出 1、兩個相同就輸出 0。基本上就是「差異偵測」。所以在對兩數 a 和 b 做運算時，在該位上，只要 b 翻轉，對應輸出一定翻轉。以擲兩枚硬幣來說（其實就是看真值表）：
| a | b | a XOR b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
例如原本 a 和 b 都是反面（0），XOR 計算結果是 0，但只要把 b 改成正面（1），結果就跟著改變了。
另外，比較 XOR、AND 和 OR 計算：
| a | b | a AND b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| a | b | a OR b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
假設 a、b 兩個都是公平硬幣，但（對應上面三張表）：
- AND 算出來有 75% 的機率是 0、25% 的機率是 1。
- OR 算出來有 25% 的機率是 0、75% 的機率是 1。
- XOR 算出來有 50% 機率是 0、50% 機率是 1。
XOR 的算法剛好平衡，很適合做出雜湊函數要的「看起來很平均、看起來很亂」的樣子。
結語
雜湊就像把任意資料打成固定長度的「指紋」，好的雜湊會搭配位移、XOR、乘以質數等位元級混合，把微小變動擴散成巨大差異（雪崩效應）並且難以逆推。本文提到的超簡單雜湊函數是用來展示概念，實務上還是要使用標準的雜湊函數法（SHA-256、bcrypt 等），若你沒有足夠的理由，不要自製雜湊函數。
另外，雜湊有夠專業，包含非密碼學用的雜湊、密碼學用的雜湊，有些追求快速、有的是為了安全，用途完全不同。這篇文章只是試著解釋雜湊在密碼學上的基本概念。