描述显式通用哈希函数系列

Question

在这个问题中，我得到了以下映射

U = {0, 1, 2, 3, 4, 5, 6, 7} to {0, 1}

由此，必须派生一个明确的通用哈希函数，并暗示这可以通过一组 4 个函数来完成。 不幸的是，尽管搜索了有关如何执行此操作的文章，但我仍然感到困惑。 任何有助于理解如何找到这个哈希函数并朝着正确的方向前进的帮助，我们将不胜感激！

编辑：

经过一番深思熟虑，这就是我想出的;这是正确的吗？

0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

Answer 1

使用维基百科的定义：

函数族 H = {h： U → [m]} 称为泛族，∀如果 x，y ∈ U， x ≠ y ： Pr h_∈H[h(x( = h(y(] ≤¹/_m。

在您的情况下，这意味着对于集合 {0， 1， 2， 3， 4， 5， 6， 7} 中的任何两个值x和y，四个哈希函数中最多有两个可以将它们映射到同一个位。

您的建议：

0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

不起作用，因为有四对 (x，y( — 即 (0,1(、(2,3(、(4,5( 和 (6,7( —其中所有四个哈希函数将它们映射到同一位。

相反，以下是一些有效的选项：

0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  0  1  1  1  1
h2 | 0  0  1  1  0  0  1  1
h3 | 0  1  0  1  0  1  0  1
h4 | 0  1  1  0  1  0  0  1
0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  1  0  1  1  1
h2 | 0  0  1  0  1  0  1  1
h3 | 0  1  0  0  1  1  0  1
h4 | 1  0  0  0  1  1  1  0