雜湊與散列#

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

「散列」與「雜湊」是同一概念的不同翻譯，英文都是 Hash。

章節概覽#

散列表的本質#

散列表是陣列的擴展：

1. 陣列：透過下標直接存取，O(1)
2. 散列表：透過 key 計算出下標，O(1)

key → hash(key) → index → array[index]

散列表的效能取決於：

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