算法打基础——HashⅡ: 全域哈希与完美哈希

算法打基础——HashⅡ:全域哈希与完美哈希的完整攻略

本文将为您提供关于全域哈希和完美哈希的完整攻略，包括算法原理、步骤和示例。

全域哈希

全域哈希是一种哈希函数族，它可以在不知道输入数据分布的情况下，将输入数据映射到哈希表中的不同位置。全域哈希的特点是，对于任意两个不同的输入数据，它们被映射到同一个哈希表位置的概率非常小。

算法原理

全域哈希的原理是，将输入数据与随机生成的哈希函数进行组合，得到一个哈希值。由于哈希函数是随机生成的，因此对于不同的输入数据，它们被映射到同一个哈希表位置的概率非常小。

算法步骤

全域哈希的步骤如下：

1. 随机生成一组哈希函数。

2. 将输入数据与哈希函数进行组合，得到一个哈希值。

3. 将哈希值映射到哈希表中的一个位置。

4. 重复步骤2-3，直到所有输入数据都被映射到哈希表中的不同位置。

示例

以下是一个示例，演示了如何使用全域哈希将输入数据映射到哈希表中的不同位置。

假设有以下输入数据：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

我们可以使用全域哈希将这些数据映射到哈希表中的不同位置。以下是步骤：

1. 随机生成一组哈希函数。

h1(x) = (3x + 7) % 11
h2(x) = (5x + 11) % 13
h3(x) = (7x + 13) % 17

1. 将输入数据与哈希函数进行组合，得到一个哈希值。

h1(1) = 10
h2(1) = 1
h3(1) = 14
h1(2) = 0
h2(2) = 8
h3(2) = 4
h1(3) = 9
h2(3) = 3
h3(3) = 15
h1(4) = 7
h2(4) = 6
h3(4) = 16
h1(5) = 6
h2(5) = 9
h3(5) = 0
h1(6) = 4
h2(6) = 12
h3(6) = 3
h1(7) = 2
h2(7) = 2
h3(7) = 10
h1(8) = 1
h2(8) = 5
h3(8) = 13
h1(9) = 11
h2(9) = 11
h3(9) = 1
h1(10) = 8
h2(10) = 1
h3(10) = 14

1. 将哈希值映射到哈希表中的一个位置。

[10, 1, 14, 0, 8, 4, 9, 6, 16, 3, 15, 2, 11, 5, 13, 7, 12]

1. 所有输入数据都被映射到哈希表中的不同位置。

完美哈希

完美哈希是一种哈希函数，它可以将输入数据映射到哈希表中的不同位置，且不会出现哈希冲突。完美哈希的特点是，对于已知的输入数据集合，它可以生成一个哈希函数，使得所有输入数据都被映射到哈希表中的不同位置。

算法原理

完美哈希的原理是，先使用全域哈希将输入数据映射到哈希表中的不同位置，然后再使用一个二次哈希函数对哈希表中的每个位置进行哈希，得到一个哈希值。由于二次哈希函数是根据已知的输入数据集合生成的，因此不会出现哈希冲突。

算法步骤

完美哈希的步骤如下：

1. 使用全域哈希将输入数据映射到哈希表中的不同位置。

2. 对哈希表中的每个位置使用一个二次哈希函数进行哈希，得到一个哈希值。

3. 将哈希值映射到哈希表中的一个位置。

4. 重复步骤2-3，直到所有输入数据都被映射到哈希表中的不同位置。

示例

以下是一个示例，演示了如何使用完美哈希将输入数据映射到哈希表中的不同位置。

假设有以下输入数据：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

我们可以使用完美哈希将这些数据映射到哈希表中的不同位置。以下是步骤：

1. 使用全域哈希将输入数据映射到哈希表中的不同位置。

[10, 1, 14, 0, 8, 4, 9, 6, 16, 3, 15, 2, 11, 5, 13, 7, 12]

1. 对哈希表中的每个位置使用一个二次哈希函数进行哈希，得到一个哈希值。

h(x) = (3x^2 + 5x + 7) % 17
h(10) = 2
h(1) = 0
h(14) = 0
h(0) = 7
h(8) = 4
h(4) = 0
h(9) = 4
h(6) = 7
h(16) = 2
h(3) = 2
h(15) = 4
h(2) = 2
h(11) = 4
h(5) = 7
h(13) = 0
h(7) = 7
h(12) = 0

1. 将哈希值映射到哈希表中的一个位置。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

1. 所有输入数据都被映射到哈希表中的不同位置。

结论

全域哈希和完美哈希是两种常用的哈希函数，它们可以将输入数据映射到哈希表中的不同位置。全域哈希适用于不知道输入数据分布的情况下，而完美哈希适用于已知输入数据集合的情况下。