哈希函数和哈希表

哈希是使用称为哈希函数的数学函数，从文本或数字列表生成值的进程。许多哈希函数使用数字或字母数字键。以下是几种不同的哈希函数。

哈希函数

以下是部分哈希函数：

这是创建哈希函数最简单的方法。哈希函数可以描述为：

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+ 次浏览

通过完成课程获得认证

开始