「兩個名字落在同一個位置，不代表他們是同一個人；要等桶裡排成一列，才看得出誰先來、誰是後來硬擠進去的。」
——《阿帕契開源審計錄》¹ 卷二·雜湊碰撞篇²

幕間
獵人獨坐暗處按著槍身。
女巫低語：「大家都以為你早死了，不出來自證？」
「趴著。」獵人眼神冰冷，「預言家要我伏到最後。這槍留給真狼，不留給誤會。」

法官報完夜間死訊，白天第一輪發言還沒過半，四號和六號已經被推到同一個位置上——兩個人都被咬定是「昨晚那隻起刀的狼」。四號說六號的票投得太急，六號說四號的發言跟前一夜對不上，兩邊各有一串人附和，聲音疊在一起，聽起來都像。

坐我斜對面的二號一直低著頭，炭筆在膝上的紙角來回劃，沒抬眼。有人問他記什麼，他把紙往腿邊一收：「隨手寫的，等等就用得到。」

七號沒加入任何一邊。她把羊皮紙攤平，不再是之前那種散落的短句，而是畫了幾條直線，隔出四個欄位：誰、第幾夜、投給誰、憑什麼。她先把四號和六號各填一行，然後抬頭問了一句，聲音不大卻讓兩邊都停下來：「你們說的是同一件事，還是只是剛好指到同一個人？」

兩個聲明落在同一個位置上。村莊要怎麼分辨，一個是真的、另一個只是碰巧撞進來的？

雜湊表把「名字」換算成「位置」

字典、映射表這類關聯集合，底層都在做同一件事：把鍵（key）丟進一個雜湊函式，得到一個整數，再把整數對桶陣列長度取模，算出這筆資料該放進哪一格。雜湊函式夠均勻，資料就散得開；可是只要鍵的數量逼近桶的數量，根據鴿籠原理，一定會有兩個鍵算出同一格——這就是碰撞。處理碰撞有兩條主線：鏈結法在每個桶裡掛一條鏈（串列或樹），同格的資料排成一列；開放定址法發現這格有人，就照規則往後探測下一格，直到找到空位。四種語言各自選了一條路，也各自付出不同代價。

Java HashMap：桶裡拉一條鏈，太長就變樹

HashMap 用一個 Node[] 陣列，先把 hashCode() 再攪一次（h ^ (h >>> 16)）讓高位也參與分佈，再用 (n - 1) & hash 算索引。碰撞時同桶的節點接成單向鏈結。真正值得想清楚的是那個「鏈長達到八、且表容量至少六十四就轉紅黑樹」的門檻：在雜湊夠均勻的前提下，同一個桶塞進八個元素的機率照 Poisson 分佈算大約是千萬分之一，所以只要真的看到某條鏈長到八，幾乎可以斷定不是運氣不好，而是 hashCode() 寫壞了，或者有人在餵毒。這個攻擊叫雜湊碰撞阻斷服務（HashDoS）：攻擊者送進一批 hashCode() 相同的鍵，把一個 O(1) 的查表退化成 O(n)，整個請求就變 O(n²)。轉紅黑樹把最壞查詢從 O(n) 拉回 O(log n)，等於替這條退化路徑裝了個安全閥。多執行緒場景要用 ConcurrentHashMap——它沒有全域鎖，空桶用 CAS 寫入，更新時只鎖那個桶的頭節點，讀取完全不上鎖，不同桶可以真的平行寫。

Go map：桶裝八格，滿了掛 overflow

Go 的 map 每個桶有八組鍵值槽位加一段 tophash，塞滿才再掛一個 overflow 桶接下去。它沒有走 Java 那種一個節點一個物件的經典鏈結，是有原因的：八組鍵值連續擺在同一塊記憶體裡，一次快取列載入就能掃過好幾個元素，而 tophash 陣列先存了每個鍵雜湊值的高八位，比對時先掃這排單位元組、對上了才去比完整的鍵，省下大量指標追逐。經典鏈結每跳一個節點就是一次可能的快取失誤，桶陣列這種佈局把碰撞的代價壓在快取友善的範圍內。它的雜湊種子每個 map 隨機產生，所以你無法預測碰撞，連迭代順序都被刻意打亂，避免程式意外依賴順序。負載因子超過 6.5 就擴容成兩倍，分批搬移。要注意 map 不是併發安全的，多個 goroutine 同時寫會直接 fatal error: concurrent map writes。

Rust HashMap：SwissTable 加上抗攻擊的 SipHash

Rust 標準庫預設用 SipHash-1-3，而且每個 map 帶一把隨機金鑰。這個選擇是刻意用一點速度換安全：SipHash 是帶金鑰的密碼學雜湊，攻擊者不知道金鑰就沒辦法預先算出一批會碰撞的鍵，HashDoS 從源頭失效；代價是它比一個簡單的乘法雜湊慢上數倍，短鍵尤其明顯。所以標準庫把 hasher 設計成可抽換——當鍵來源可信、又在效能熱點上，換成 FxHashMap、ahash 這類非抗攻擊的快速實作是常見做法。底層的 hashbrown（SwissTable）走開放定址，用一排控制位元組記錄槽位狀態，靠 SIMD 一次掃描一組槽位找空位或找命中——完全沒有碰撞鏈這回事，碰撞就是往後探測下一組。

Python dict：開放定址加緊湊佈局

CPython 的 dict 用開放定址，探測序列帶擾動：j = (5 * j + 1 + perturb) % 2**k，perturb 每次右移五位，讓碰撞後的落點盡量分散，而不是像線性探測那樣擠成一團。從 3.6 起改成緊湊 dict——真正的鍵值放在一個依插入順序排列的密集陣列裡，另一個稀疏的索引陣列只存位置。這裡有個常被誤會的點：保留插入順序不是當初的設計目標，是副產品。原本的動機是省記憶體，用一個裝小整數的稀疏索引陣列，取代原本一整排全尺寸的 entry 結構；順序被保留只是因為密集陣列本來就照插入順序長。官方一直到 3.7 才願意把「保留順序」寫進語言規格。裝到三分之二滿就重新配置。在 GIL 之下，單一 dict 操作實際上是原子的。

import java.util.HashMap;
import java.util.Map;

// Two distinct keys engineered to land in the same bucket.
final class SeatKey {
    private final String label;
    private final int forcedHash;

    SeatKey(String label, int forcedHash) {
        this.label = label;
        this.forcedHash = forcedHash;
    }

    @Override
    public int hashCode() {
        return forcedHash; // identical for both keys -> guaranteed collision
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof SeatKey key && label.equals(key.label);
    }

    @Override
    public String toString() {
        return label;
    }
}

public class CollisionDemo {
    public static void main(String[] args) {
        Map<SeatKey, String> accusations = new HashMap<>();

        SeatKey seatFour = new SeatKey("seat-4", 42);
        SeatKey seatSix = new SeatKey("seat-6", 42);

        accusations.put(seatFour, "night-1 knife");
        accusations.put(seatSix, "night-1 knife");

        // Same bucket, same chain, still two separate entries.
        System.out.println("size = " + accusations.size());          // 2
        System.out.println("seat-4 -> " + accusations.get(seatFour)); // night-1 knife
        System.out.println("seat-6 -> " + accusations.get(seatSix));  // night-1 knife
    }
}

這段程式碼要看的是 hashCode() 被寫死成常數：兩個 SeatKey 的雜湊值都是 42，所以它們必定落進同一個桶、接成同一條鏈。但 equals() 比的是 label，於是它們仍然是兩個不同的鍵，accusations.size() 印出 2、兩筆資料各自查得到——如果 HashMap 是用覆蓋而不是鏈結處理碰撞，第二個 put 就會蓋掉第一個，size 會是 1。這裡也順帶示範了 hashCode 與 equals 的合約：兩個 equals 相等的物件雜湊值必須相同，反過來不必成立。合約寫壞的後果很具體——equals 沒跟著 hashCode 一起改，同一個鍵放進去就再也拿不出來，因為查詢先用雜湊定位桶，再用 equals 在桶裡逐一比對。

雜湊值只告訴你「去哪一格找」，equals 才告訴你「找到的是不是你要的」。七號那張表做的是同一件事——把兩個被指成同一隻狼的人攤開，「投給誰」「第幾夜」這些欄位就是她的 equals，逐格比對才知道碰撞背後是不是同一個東西。

四號和六號的僵局，最後不是靠誰喊得大聲解開的。七號把兩行紀錄並排：四號那行「第二夜投給三號、理由是發言太順」，六號那行「第二夜棄票、理由是資訊不足」——同一個雜湊值（都被指成起刀的狼），拉開鏈結一看，兩個人的軌跡根本不重疊。碰撞只是說「他們被放進同一格」，不代表「他們是同一個東西」；要分辨，得有欄位、得逐格比對。那一輪投票因此改了方向，六號被留了下來，後來證明他確實是好人。

我在旁邊看著，想起前幾世我遇到這種雙指認，總是憑一句「感覺六號比較像」就跟著投——那等於只看雜湊值不看 equals，把碰撞當成等同。那天清晨法官報死訊時，我還聽見那把「上帝的聲音」前半句和後半句對不太上——前半冷得像唱名，後半卻像換了個人在講。兩個東西共用一張嘴、落在同一個位置，你不逐格比對，就會當成同一個。二號那晚也沒閒著，他的炭筆一直在膝上動，可是等七號攤開整頁紙，他反而先收了手，什麼都沒補。

提示詞快取：把「內容相同」換算成「同一個桶」

雜湊表的核心動作是「把一串內容換算成一個位置，位置相同就先假設可能是同一份東西，再逐格比對確認」。Claude 官方的**提示詞快取（Prompt Caching）**機制做的正是這件事，只是換了一個尺度：每次請求送出時，系統會對提示詞的前綴內容計算雜湊，如果這個雜湊值命中一份先前已經處理過、還在有效期內的快取項目，就直接複用那份已經算好的中間狀態（KV-cache），不必重新跑一次完整的推理運算——這正是 Day 07 提到「省下 58%～73% 成本」背後的機制根源。前綴哪怕只改動一個字，換算出來的雜湊值就完全不同，等於落進了另一個桶，快取直接失效，得從頭計算。

這與本篇的核心提醒完全一致：雜湊值相同只代表「值得去比對看看」，不代表「兩份東西真的一樣」——提示詞快取判斷「是否命中」靠的也不只是雜湊落點，還得逐位元組核對前綴內容是否真的完全相同，才敢放心複用。七號的表格分欄比對「第幾夜、投給誰」，本質上就是在替雜湊相同的兩個嫌疑對象做這道「逐格核對」；快取系統替內容相同的提示詞省下的，則是重新計算一整段推理的成本。

你現在該能：說清楚雜湊函式、桶、碰撞三者的關係，並解釋鏈結法與開放定址法各自的代價；知道為什麼 Java 的鏈結過長會轉紅黑樹、Rust 與 Python 為何預設用帶隨機種子的雜湊抵擋碰撞攻擊。想動手，就照官方文件把四種語言的預設 map 各塞一萬筆資料量一次查詢延遲，再刻意餵進碰撞鍵看曲線怎麼變。roadmap.sh 的資料結構路線與 Hyperskill 的對應章節可以補足底層細節。

參考資料與延伸閱讀

• Oracle Java 21 官方 API 文件 - HashMap（treeify 門檻與雜湊擾動）
• Go 原始碼 - runtime/map.go（桶陣列、tophash、overflow 桶）
• Rust 官方文件 - std::collections::HashMap（SipHash 與可抽換 hasher）
• hashbrown（Rust SwissTable 實作）GitHub 倉庫
• CPython 原始碼 - Objects/dictobject.c（開放定址與擾動探測）
• Claude 官方文件 - Prompt Caching（前綴雜湊與快取命中機制）
• Claude Community Taiwan 社群網站
• Taipei | Claude Code Build Day（Anthropic 官方首場全球黑客松）
• 關鍵檢索詞（建議使用 Felo.ai / Perplexity 查詢）：HashMap separate chaining vs open addressing treeify Go map overflow bucket load factor hash seed Rust SwissTable hashbrown SipHash HashDoS Python compact dict perturbation probing Claude prompt caching cache hit prefix hash

¹ 註：本書名為情境設定之虛構文獻，非真實歷史或開源紀錄。
² 註：現實彩蛋——距 Claude Taipei 中秋烤肉聚會 還有 5 天。三位主辦人之一是 Justin Shaw：台灣 Claude 大使三人之中第二位獲封者（此排序依獲封時間先後，不代表任何形式的排名），41.tech 共同創辦人。他也是 Anthropic 官方首場全球黑客松 Taipei | Claude Code Build Day 的主辦人，創辦了 Claude Community Taiwan 社群網站。