0

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

 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
4

1 回答 1

2

使用维基百科的定义：

如果 ∀ x,y ∈ U, x ≠ y : Pr h∈H [h(x) = h(y)] ≤ 1 ，则函数族 H = {h: U → [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
于 2018-10-16T01:39:36.660 回答