2024年4月21日 星期日

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.

沒有留言: