描述一个明确的通用哈希函数族

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

使用维基百科的定义：

A family of functions H = {h: U → [m]} is called a universal family if, ∀ x,y ∈ U, x ≠ y : Pr_h∈H[h(x) = h(y)] ≤ ¹/_m.

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

您的建议：

     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

描述一个明确的通用哈希函数族

Describe an Explicit Universal Hash Function Family

algorithm

universal-hashing