第4章 雜湊表#

本章目標#

• 了解雜湊函數的設計原則與常見策略。
• 實作鏈接法與開放定址法兩種碰撞處理。
• 掌握雜湊表在實務問題中的典型用法。

章前言#

如果要選一個「改變程式世界最深」的資料結構，雜湊表（hash table）一定入圍。它的承諾很驚人：平均 O(1) 的插入、刪除、查詢。Python 的 dict、set，Java 的 HashMap，資料庫的索引快取、編譯器的符號表、網頁的 session 儲存——到處都是雜湊表。

雜湊表的核心想法是「用空間換直接定位」：準備一個陣列，設計一個雜湊函數把任意鍵（字串、數字、元組……）映射成陣列索引，查詢時用同一個函數算出位置、直接去取，不必逐項比對。理想很美好，但兩個鍵可能算出同一個索引——這叫碰撞（collision），無可避免（鍵的空間遠大於陣列格子，鴿籠原理）。本章的兩大主題正是：(1) 如何設計均勻的雜湊函數；(2) 碰撞發生後如何收拾——鏈接法把撞在一起的鍵串成小串列，開放定址法則在陣列內另尋空格。

我們還會實際拆解 Python dict 的運作：擴容策略、負載因子、為什麼 dict 的鍵必須可雜湊、為什麼刪除開放定址法中的元素要用特殊標記。學完本章，你面對「從一百萬筆資料即時查詢」的需求時，不再需要猶豫用什麼工具。