資料庫管理系統中有哪些不同的雜湊方法？

雜湊檔案組織也稱為直接檔案組織。

在這種方法中，為了儲存記錄，會計算一個雜湊函式，該函式提供儲存記錄的塊地址。任何型別的數學函式都可以用作雜湊函式。它可以很簡單，也可以很複雜。

雜湊函式應用於列或屬性以獲取塊地址。記錄是隨機儲存的。因此，它也稱為直接或隨機檔案組織。

如果生成的雜湊函式作用於被認為是鍵的列，則該列可以稱為雜湊鍵；如果生成的雜湊函式作用於被認為是非鍵的列，則該列可以稱為雜湊列。

假設一個檔案有n條記錄，每條記錄都有一個唯一確定該記錄的鍵。設K為鍵，L為記憶體位置。雜湊函式定義為H: K->L

示例

下面是一個雜湊檔案組織的示例：

0
1
2011 德里
3
4022 加爾各答
5
6033 金奈
7
8044 孟買
9

這裡城市的區號是鍵。雜湊函式透過簡單地將鍵的數字相加，將這些鍵對映到地址2,4,6,8。

雜湊函式的方法

雜湊函式H(k)的方法解釋如下：

  • 除法法

雜湊函式H(k)=k (mod m)，其中m是一個大於鍵數量的素數。

示例

假設有76名學生，每個學生都有一個唯一的10位學號。這裡的學號是鍵。

m=79（大於76）

L包含100個記憶體位置00,01,02,…,99

對於學號0148105102、0148105124、0148105405，H(k)如下所示：

H(0148105102) = 0148105102 % 79 = 10
H(0148105124) = 0148105124 % 79 = 32
H(0148105405) = 0148105405 % 79 = 76
  • 中間平方法

對鍵k進行平方，然後透過取中間數字來獲得地址。

示例

假設有200名員工，每個員工都有一個唯一的3位員工ID。這裡，員工ID是鍵。

H(k) = 2nd and 3rd digit of k2
K: 067 048 146
K2: 4489 2304 21316
H(k): 48 30 13
  • 摺疊法

將鍵分成k1、k2、……kn幾部分，然後將這些部分加在一起，忽略進位，即H(k) = k1+ k2+ ……..+ kn

示例

假設有2000名員工，每個員工都有一個唯一的4位員工ID。這裡，員工ID是鍵。

H(1643) =16+43 =57
H(1999) =19+99 = 18 (The leading digit 1 is ignored)
H(1176) = 11 + 76 = 87
H( 1374) = 13+ 74 =87

當多個鍵引用同一個記憶體位置時，這個問題稱為衝突。

更新於：2021年7月8日

319 次檢視

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告