雜湊函式和雜湊表

雜湊是指使用稱為雜湊函式的數學函式，從文字或數字列表生成值的過程。有許多雜湊函式使用數字或字母數字鍵。下面給出了一些不同的雜湊函式。

雜湊函式

以下是雜湊函式的一些示例：

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

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-06-22

11K+ 次檢視

透過完成課程獲得認證