雜湊表格 (HashTable)，雜湊集合 (HashSet)，或 雜湊映射 (HashMap)，以下統稱雜湊表格，是效能最佳的一種資料結構，其增刪查找的時間複雜度皆為 O(1)，和容器存放的元素個數 n 無關。Python語言的集合 (Set) 及字典 (Dictionary) 就是分別基於 雜湊集合 及 雜湊映射 而實現的，所以存取效能很好。
話雖如此，雜湊表格苦於兩個缺點，一是不能發生踫撞，只要踫撞嚴重，存取效能就會降低，退化成 O(n)。二是不能排序，不能查詢比某元素大/小的元素集合(tailSet/headSet)。若容器須要排序，只能退而求其次，改用樹狀結構 (TreeSet/TreeMap)，例如搜索樹等，其增刪查找效能降到 O(log(n))；或堆積 (Heap)，其增刪效能 O(log(n))，但查找最小或最大值效能 O(1)。
以下參考文獻，列出雜湊表格常採用的技術分類，供了解其極佳效能的作法及補救法。
A. Hash code and compression: (雜湊碼及壓縮技術)
A1. Hash code function 雜湊碼函數
如何依據元素內容計算雜湊值
- Bit representation (位元表現法)
- Polynomial hash codes (多項式雜湊碼)
- Cyclic-shift hash codes (循環平移雜湊碼)
A2. Compression function 壓縮函數
如何將雜湊碼 (hash_code) 依表格大小 (hash_table_size) 轉為找尋起點格下標
- Division method (求餘數法)
hash_code mod hash_table_size - MAD (multiply-add-and-divide) method (乘加求餘數法)
[(a * hash_code + b) mod p] mod hash_table_size
B. Hash collision handling 雜湊踫撞處理法
B1. Closed addressing / Open hashing or Separate chaining
封閉式定址 / 開放式雜湊法，個別串接
放元素的格子全由元素的雜湊碼決定 / 放元素的格子在雜湊表之外
B2. Open addressing / Closed hashing
開放式定址 / 封閉式雜湊法
放元素的格子不全由元素的雜湊碼決定，視當時踫撞情形而定 / 放元素的格子在雜湊表內
- Linear probing 線性探索
- Quadratic probing 平方探索
- Double hashing 雙雜湊
Reference:
