what's the mechanism behind hash tables

雜湊表格 (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 雜湊碼函數
         如何依據元素內容計算雜湊值

1.  Bit representation (位元表現法)
2.  Polynomial hash codes (多項式雜湊碼)
3.  Cyclic-shift hash codes (循環平移雜湊碼)

  A2. Compression function 壓縮函數
        如何將雜湊碼 (hash_code) 依表格大小 (hash_table_size) 轉為找尋起點格下標

1.  Division method (求餘數法)
        hash_code mod hash_table_size
2.  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
         開放式定址       / 封閉式雜湊法

        放元素的格子不全由元素的雜湊碼決定，視當時踫撞情形而定 / 放元素的格子在雜湊表內

1. Linear probing 線性探索
2. Quadratic probing 平方探索
3. Double hashing 雙雜湊

Reference:

1. Open Addressing Collision Handling technique in Hashing - GeeksforGeeks
2. 2015-goodrich-wiley-data structures & algorithms in java, 6th ed.