雜湊分頁表（hashed page table）

假設你保存聯絡人，不是用一張為每個可能的名字都留一格、編號龐大的清單，而是用一組小桶子：你把每個名字丟進一條固定規則（雜湊）算出一個桶，再把聯絡人存在那裡。要找某人，套用同一條規則、走到那個桶、掃一掃桶裡那寥寥幾筆。雜湊分頁表用同樣的方式組織轉譯：它不是每頁一格（對稀疏空間而言多半空著），而是把頁號雜湊到一個桶，只存真正存在的轉譯。

機制上，硬體或作業系統取虛擬頁號，餵進一個雜湊函式，產生一個雜湊表的索引。雜湊表的每一格指向一條鏈（一個小型鏈結串列），因為兩個不同的頁號可能雜湊到同一格——碰撞。鏈中每筆記錄存著一個頁號、它的頁框號，以及指向下一筆記錄的指標。要翻譯時，硬體把頁號雜湊，沿著那一格的鏈往下走，拿存著的頁號與它想要的比對，相符就回傳頁框。由於這張表只為真正有對應的頁保留項目，它的大小隨「用到的」頁增長，而非隨位址空間的大小——這正是它對非常大、非常稀疏的空間的全部意義。這種做法在位址空間大於 32 位元的系統上尤其常見，那裡平面表、甚至多層表都會笨重不堪。

雜湊分頁表之所以重要，是因為它能緊湊地處理大型、稀疏的位址空間，而不需深層的多層走訪。誠實的提醒：查找需要比對完整的頁號（平面表從不需要，因為索引「就是」頁號），而碰撞意味著一次查找可能得掃描好幾筆記錄，所以最壞情況的時間取決於鏈長與一個好的雜湊函式。一個變體叫叢集分頁表，每筆項目存好幾個連續的頁，以減少鏈的走訪。一如往常，TLB 仍攔下大多數存取，所以雜湊走訪只在失誤時才執行。