雜湊函式和雜湊表

雜湊是使用稱為雜湊函式的數學函式，從文字或數字列表生成值的程序。許多雜湊函式使用數字或字母數字鍵。以下是幾種不同的雜湊函式。

雜湊函式

以下是部分雜湊函式：

這是建立雜湊函式最簡單的方法。雜湊函式可以描述為：

h(k) = k mod n

這裡，h(k) 是透過將鍵值 k 除以雜湊表大小 n 並取餘數獲得的雜湊值。最好 n 是質數，這樣可以確保鍵更均勻地分佈。

除法法的示例如下：

k=1276
n=10
h(1276) = 1276 mod 10
= 6

獲得的雜湊值為 6

除法法的缺點是連續的鍵會對映到雜湊表中連續的雜湊值。這會導致效能下降。

乘法法使用的雜湊函式為：

h(k) = floor( n( kA mod 1 ) )

這裡，k 是鍵，A 可以是 0 到 1 之間的任何常數值。k 和 A 相乘，然後分離其小數部分。然後將其乘以 n 以獲得雜湊值。

乘法法的示例如下：

k=123
n=100
A=0.618033
h(123) = 100 (123 * 0.618033 mod 1)
= 100 (76.018059 mod 1)
= 100 (0.018059)
= 1

獲得的雜湊值為 1

乘法法的優點是可以使用任何 A 值，儘管一些值被認為比其他值更好。

中間平方法是一個非常好的雜湊函式。它包括對鍵值進行平方，然後提取中間 r 位數字作為雜湊值。可以根據雜湊表的大小確定 r 的值。

中間平方法的示例如下：

假設雜湊表有 100 個記憶體位置。所以 **r=2**，因為需要兩位數字才能將鍵對映到記憶體位置。

k = 50
k*k = 2500
h(50) = 50

The hash value obtained is 50

雜湊表是一種將鍵對映到值的資料結構。它使用雜湊函式計算資料鍵的索引，並將鍵儲存在索引中。

雜湊表的示例如下：

需要儲存在雜湊表中的鍵序列為：

35 50 11 79 76 85

使用的雜湊函式 h(k) 為

h(k) = k mod 10

使用線性探測，值儲存在雜湊表中，如下所示：

Hash Table

Alex Onsman

更新於：2020年6月22日

11K+ 次瀏覽

透過完成課程獲得認證

開始