第七講：雜湊表

1. 資料結構#

DBMS 主要包括以下幾種資料

內部元數據：記錄有關數據庫和系統的信息
核心數據存儲：記錄 tuple 的信息
臨時數據結構
表索引

主要考慮以下兩個問題

資料組織
資料的可靠性

2. 哈希表#

哈希表

哈希表目標

哈希函數

將值轉化為一個較小的鍵
在速度和 碰撞率 之間進行權衡。

哈希方案

該如何處置碰撞的情形
需要在 哈希表大小 與 額外信息維護之間 權衡

3. 哈希函數#

不管輸入的 key 是什麼，輸出一個 特別的 數字的函數。

哈希函數

哈希函數基準

4. 靜態哈希方案#

4.1 線性探針哈希#

線性探針

我們解決哈希碰撞的方法是，如果我們的哈希函數返回的位置已經被佔用了，那麼則一直向下取一個位置，直到找到表中空的值。

在刪除操作中，可能會出現一種情形，有的值並不是 hash function 產生的直接值，而是通過一直取下一個位置得到的值。

在這種情形下，我們所採取的方法有。

將受到偏移影響的值往回調整。通過重新哈希的方式進行調整。效率比較低下。
將那些刪除了的值標記為已刪除。這些值可以在新的值需要使用的時候重新利用。不過需要周期性的垃圾回收。

存儲相同的值

非唯一鍵

存儲相同的 key 但有不同的 value 的值的時候，我們可以有兩種辦法解決。

對於每個 key 他們的 value 開闢出來一個單獨的空間
所有的 key 都用哈希函數散列在一個存儲空間中。

4.2 Robin Hood Hashing#

這是線性探針算法的一升級版，旨在解決分布不均的問題。在上面的算法中，可能存在一些 key，經過哈希計算後可能會聚集在一塊導致哈希算法劣化。 Robin Hood hashing 解決碰撞的方式會將部分 rich 的 key 分配給 poor key.

這種避免哈希碰撞的方法是，給每個值都記錄一個偏移值，表中的每個值在向下搜索的時候，需要和表中的值進行對比。如果當前偏移值比表中值的偏移值大，那麼則將當前值和表中值進行替換。直到找到空位結束。

void Robin_hood_Hashing(int key) {
     int val = hash(key);
     int offset = 0;
     for (int i = val ; ; i ++ , offset ++ ) {
          if(hash_table->is_empty(i)){ 
               hash_table->insert(i , val , offset);
               break;
          }

          if(hash_table->get_offset(i) < offset) {
               auto [n_val , n_offset] = hash_table->get_data(i);
               hash_table->insert(i , val , offset);
               val = n_val , offset = n_offset;
          }
          if(i == MAXSIZE) i = 0;
     }
}