雜湊#

雜湊（Hash）是電腦科學中最重要的概念之一。雜湊表提供 O(1) 的查找效率，雜湊演算法則廣泛應用於加密、校驗、分布式系統等領域。

英文 Hash 在中國大陸常譯為「散列」，本書統一使用台灣慣用的「雜湊」。

章節概覽#

主題核心內容
雜湊表原理雜湊函式、衝突解決、動態擴容
雜湊演算法加密、校驗、唯一識別
雜湊應用面試題實戰（Two Sum、Three Sum 等）

雜湊表的本質#

雜湊表是陣列的擴展：

  1. 陣列：透過下標直接存取，O(1)
  2. 雜湊表：透過 key 計算出下標，O(1)
key → hash(key) → index → array[index]

雜湊表的效能取決於：

  1. 雜湊函式的設計（是否均勻分布）
  2. 衝突解決策略的選擇
  3. 裝載因子的控制

跨倉庫導讀#

Backward 跳表 雜湊表原理 Forward