哈希函数和哈希表

哈希是指使用称为哈希函数的数学函数，从文本或数字列表生成值的过程。有许多哈希函数使用数字或字母数字键。下面给出了一些不同的哈希函数。

哈希函数

以下是哈希函数的一些示例：

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

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+ 次查看

通过完成课程获得认证