C 语言中的哈希函数类型

散列（Hashing）是一种通过使用散列函数计算散列码来映射键值对的技术/过程。当给定一个（键：值）对时，散列函数会从键中计算出一个小的整数值。获得的整数称为散列值/散列码，并作为在散列表中存储相应值的索引。

如果对于两个（键：值）对，在应用散列函数后获得相同的索引，则此条件称为冲突。我们需要选择一个散列函数，使其不会发生冲突。

术语

1. 散列（Hashing）：整个过程
2. 散列值/码：在散列表中存储在相应键上计算散列函数后获得的值的索引。
3. 散列表（Hash Table）：与散列相关的数据结构，其中键映射到存储在数组中的值。
4. 散列函数/散列（Hash Function/Hash）：应用于键的数学函数，以获取其相应值在散列表中的索引。

本文解释了程序员经常使用的不同类型的散列函数。根据键是数字还是字母数字，我们可以选择以下四种散列函数：

1. 除法法
2. 平方取中法
3. 折叠法
4. 乘法法

1. 除法法

假设我们有一个大小为“S”的散列表，我们想在散列表中存储一个（键，值）对。根据除法法，散列函数将是：

• 这里 M 是用于计算散列值的整数值，M 应该大于 S。有时，S 也用作 M。
• 这是获取散列值最简单和最容易的方法。
• 最佳实践是当 M 是素数时使用此方法，因为我们可以均匀地分布所有键。
• 它也很快，因为它只需要一次计算 - 模数。

现在让我们举一个例子来理解这种方法的缺点：

散列表大小 = 5 (M, S)

键：值对：{10: "Sudha", 11: "Venkat", 12: "Jeevani"}

对于每对

1. {10: "Sudha"}
   键 mod M = 10 mod 5 = 0
2. {11: "Venkat"}
   键 mod M = 11 mod 5 = 1
3. {12: "Jeevani"}
   键 mod M = 12 mod 5 = 2

请注意，散列值是连续的。这是这种散列函数的一个缺点。我们为连续的键获得连续的索引，导致由于安全性降低而性能下降。有时，在选择散列表大小时，我们需要分析许多后果。

一个演示除法法机制的简单程序

输出

Enter the size of the Hash Table: 5
The indexes of the values in the Hash Table: 0 1 2

2. 平方取中法

这是一种计算散列值的两步过程。给定一个 {key: value} 对，散列函数将通过以下方式计算：

1. 将键平方 -> 键 * 键
2. 从数字中间选择一些数字以获得散列值。

我们应该根据散列表的大小选择要提取的位数。假设散列表大小为 100；索引范围从 0 到 99。因此，我们应该从中间选择 2 位数字。

假设散列表大小为 10，键值对为：

{10: "Sudha", 11: "Venkat", 12: "Jeevani"}

要选择的位数：索引：(0 - 9)，所以 1 位

H(10) = 10 * 10 = 100 = 0

H(11) = 11 * 11 = 121 = 2

H(12) = 12 * 12 = 144 = 4

• 键中的所有数字都被用于生成索引，从而提高了数据结构的性能。
• 如果键是一个大值，对其进行平方会进一步增加该值，这被认为是缺点。
• 也可能发生冲突，但我们可以尝试减少或处理它们。
• 这里另一个重要的点是，对于巨大的数字，我们需要注意溢出条件。例如，如果我们取一个 6 位键，平方后我们会得到一个 12 位数字，这会超出定义的整数范围。我们可以使用长整型或字符串乘法技术。

一个演示平方取中法机制的简单程序

3. 折叠法

给定一个 {key: value} 对，表大小为 100（0 - 99 索引），除了最后一个段，键被分解成 2 个段。最后一个段可以有较少位数。现在，散列函数将是：

• 在计算散列值时，带有较少位数的最后一个进位可以忽略。

例如，"k" 是一个 10 位键，表的大小是 100 (0 - 99)，k 被分成

sum = (k1k2) + (k3k4) + (k5k6) + (k7k8) + (k9k10)

现在，H(x) = sum % 100

现在让我们举一个例子：

键：值对：{1234: "Sudha", 5678: "Venkat"}

表大小：100 (0 - 99)

对于 {1234: "Sudha"}

1234 = 12 + 34 = 46

46 % 100 = 46

对于 {5678: "Venkat"}

5678 = 56 + 78 = 134

134 % 99 = 35

4. 乘法法

与上述三种方法不同，这种方法涉及更多步骤：

1. 我们必须选择一个介于 0 和 1 之间的常数，例如 A。
2. 将键与所选的 A 相乘。
3. 现在，取乘积的小数部分，并将其乘以表大小。
4. 散列将是上述结果的向下取整（仅整数部分）。

因此，在此方法下的散列函数将是：

例如

{Key: value} 对：{1234: "Sudha", 5678: "Venkat"}

表大小：100

A = 0.56

对于 {1234: "Sudha"}

H(1234) = floor(size(1234*0.56 mod 1))

= floor(100 * 0.04)

= floor(4) = 4

对于 {5678: "Venkat"}

H(5678) = floor(size(5678*0.56 mod 1))

= floor(99 * 0.68)

= floor(67.32)

= 67

• 当散列表大小是 2 的幂时，使用乘法法被认为是最佳实践，因为它使访问和所有操作都更快。

计算散列值之后怎么办？

使用散列函数计算出散列值后，此值将用作散列表中的索引。每当用户想要访问一个值时，都会使用散列函数对相应的键进行散列，这会以比常规数组和链表更低的成本给出键在散列表中的值索引。因此，散列用于减少程序的时间和空间复杂性。