什麼是雜湊表
以雜湊函數由鍵計算存放位置，平均能以 O(1) 進行搜尋、插入與刪除的資料結構。不同的鍵落在相同位置的碰撞，以鏈結法或開放定址法處理。
日文名稱: ハッシュテーブル
「雜湊表」出現在4領域的7道練習題中（資料結構與演算法, 機率、統計與等候理論, 記憶體階層與效能等）。
這個名詞所屬的領域: 資料結構與演算法
運作原理與碰撞的處理
雜湊表以雜湊函數把鍵轉換為整數，並以除以表大小的餘數等作為存放位置。鍵的種類遠多於表的大小，因此不同的鍵落在相同位置的碰撞無法避免。鏈結法把相同位置的元素以鏈結串列等串接起來。開放定址法在表中尋找其他空位置，有依序檢查相鄰位置的線性探測，以及以另一個雜湊函數決定間隔的雙重雜湊等方法。
負載因子與重新雜湊
存放的元素數除以表的大小所得的值稱為負載因子。鏈結法中串列的平均長度與負載因子成正比，開放定址法則在負載因子接近1時，尋找空位的次數會急遽增加。因此負載因子超過設定值時，會把表放大到約2倍並重新放入所有元素（重新雜湊）。1次重新雜湊需要 O(n)，但放大的間隔會成倍拉長，因此每次加入的工作量維持在攤銷 O(1)。
效能與注意事項
平均 O(1) 的前提是雜湊函數能把鍵均勻分散到整個表。若雜湊函數有偏差，或遇到刻意造成碰撞的輸入（雜湊洪水攻擊），最差可能慢到 O(n)，因此網頁伺服器等會使用混入隨機種子的雜湊函數。此外，雜湊表不會依序保存元素，範圍搜尋或依序列舉較適合使用二元搜尋樹或 B 樹。實際速度也受快取效果影響，像線性探測這樣檢查相鄰位置的方式，往往比追蹤指標的鏈結法快。
練習雜湊表的題目
將10個鍵放入有100個桶的雜湊表。各鍵彼此獨立，以相等的機率被分配到100個桶中的某一個。在2個鍵的組合中，被分配到同一個桶的組合數的期望值為下列何者？
- A0.1
- B0.45
- C0.9
關於雜湊表中碰撞（collision）的說明，下列何者正確？
- A能從雜湊值求出原本的鍵
- B不同的鍵求出相同的雜湊值（存放位置）
- C相同的鍵每次執行都求出不同的雜湊值
常見問題
雜湊表與雜湊函數有什麼關係？
雜湊函數是由鍵計算出固定範圍之值的函數，雜湊表則是用它來計算存放位置的資料結構。雜湊表用的雜湊函數重視速度與分散的均勻度，通常不要求像密碼學雜湊函數那樣的單向性。
雜湊表用在哪些地方？
程式語言的字典（關聯陣列）與集合、編譯器的符號表、資料庫的雜湊連結與雜湊索引、快取管理等，許多需要以鍵快速查值的場合都會使用。
解析中的「雜湊表」
雜湊表以雜湊函數從鍵計算存放位置，平均能以 O(1) 進行搜尋、插入與刪除。
關於雜湊表中碰撞（collision）的說明，下列何者正確？以隨機鍵值參照雜湊表，位址同樣沒有規律，效果也很小。
硬體預取特別容易發揮效果的存取為下列何者？若採用像雜湊表依每個桶（bucket）分開上鎖這樣的細粒度，就能同時操作不同的部分。
比較以一把鎖保護整個大型資料結構的「粗粒度鎖」，與以不同的鎖保護各個部分的「細粒度鎖」，下列說明何者正確？
出現「雜湊表」的題目（7題）
- 將10個鍵放入有100個桶的雜湊表。各鍵彼此獨立，以相等的機率被分配到100個桶中的某一個。在2個鍵的組合中，被分配到同一個桶的組合數的期望值為下列何者？
- 關於雜湊表中碰撞（collision）的說明，下列何者正確？
- 在大小為7（位置0～6）的雜湊表中，以雜湊函數 h(k) = k mod 7 依序存放鍵10、17、24、3。發生碰撞時，使用把位置逐一往後移（6的下一個是0）來尋找空位置的線性探測法。鍵3會存放在哪個位置？
- 比較處理雜湊表碰撞的鏈結法（以鏈結串列串接相同位置的元素）與開放定址法（在表中尋找其他空位置），下列說明何者正確？負載因子為存放的元素數除以表的大小所得的值。
- 在元素很多、負載因子維持在0.5左右的雜湊表中，使用線性探測的開放定址法往往比鏈結法（以鏈結串列串接的方法）快，最適當的原因為下列何者？
- 硬體預取特別容易發揮效果的存取為下列何者？
- 比較以一把鎖保護整個大型資料結構的「粗粒度鎖」，與以不同的鎖保護各個部分的「細粒度鎖」，下列說明何者正確？