是否可以为整个整数范围实现通用散列？

Question

我正在阅读关于整数的Universal散列.该先决条件和强制性先决条件似乎是我们选择一个素数p大于设定的所有可能的密钥更大.

我不清楚这一点.

如果我们的密钥集是类型,int那么这意味着素数需要是下一个更大的数据类型,例如long.

但最终无论我们得到什么,因为哈希需要下载到一个int来索引哈希表.这种降级是否会以某种方式影响Universal Hashing的质量(我指的是桶上的密钥分配)？

Answer 1

如果我们的键集是整数，那么这意味着素数需要是下一个更大的数据类型，例如 long。

那不是问题。有时是必要的，否则哈希族不能是通用的。请参阅下面的详细信息。

但最终无论我们得到什么作为散列都需要向下转换为 int来索引散列表。

这种向下转换不会以某种方式影响通用哈希的质量（我指的是键在存储桶上的分布）吗？

答案是不。我会尽力解释。

是否p具有其他数据类型对于哈希族是否通用并不重要。重要的是它p等于或大于u（整数域的最大整数）。重要的p是足够大（即>= u）。

当碰撞概率等于或小于时，散列族是通用的1/m。

所以我们的想法是保持这个约束。

的值p，理论上可以和 a 一样大long或更多。它只需要是一个整数和素数。

u是域/宇宙的大小（或键的数量）。给定宇宙U = {0, ..., u-1}，u表示大小|U|。
m 是箱或桶的数量
p 是一个必须等于或大于的素数 n
散列族定义为H = {h(a,b)(x)}with h(a,b)(x) = ((a * x + b) mod p) mod m。请注意，a和b是随机选择的整数（从所有可能的整数中，因此理论上可以大于p）以素数为模p（这可以使它们小于或大于m，箱/桶的数量）；但这里也是数据类型（值域无关紧要）。有关符号，请参阅维基百科上的散列整数。
按照维基百科上的证明，您得出的结论是碰撞概率为_p/m_ * 1/(p-1)（下划线表示截断小数）。对于p >> m（p远大于m），概率趋于1/m（但这并不意味着概率越大越好p）。

换句话说，回答您的问题：p成为更大的数据类型在这里不是问题，甚至可能是必需的。p必须等于或大于uanda并且b必须是随机选择的整数模数p，无论桶的数量m。有了这些约束，您就可以构建一个通用的哈希族。

也许一个数学例子会有所帮助

设 U 是对应于unsigned char（例如在 C 中）的整数的全域。然后U = {0, ..., 255}
让p是（下一个可能的）素数等于或大于256。请注意，p可以是这些类型中的任何一种（short, int，long无论是有符号还是无符号）。关键是数据类型不起作用（在编程中类型主要表示值域。）。无论257是short，int还是long没有真正的问题在这里的数学证明的正确性的缘故。我们也可以选择更大的p（即更大的数据类型）；这不会改变证明的正确性。
1. 下一个可能的素数是257。
2. 我们说我们有25桶，即m = 25。这意味着如果碰撞概率等于或小于1/25，即近似为，则散列族将是通用的0.04。
3. 输入_p/m_ * 1/(p-1):的值，该值_257/25_ * 1/256 = 10/256 = 0.0390625小于0.04。它是具有所选参数的通用哈希系列。

我们可以选择m = u = 256桶。那么我们将有一个碰撞概率0.003891050584，它小于1/256 = 0,00390625。哈希族仍然是通用的。

让我们尝试m大于p，例如m = 300。碰撞概率为 0，小于1/300 ~= 0.003333333333。微不足道，我们有比键更多的桶。仍然是通用的，没有冲突。

我们有以下几点：

x类型int（的元素|U|）
a, b,p类型long
m 我们稍后会在示例中看到
1. 选择p使其大于最大值u（元素|U|）， p类型为long。
2. 随机选择a和b（模p）。他们是类型long，但总是< p。
3. 对于x（类型intfrom U）计算((a*x+b) mod p)。a*x是类型long，(a*x+b)也是类型long，所以((a*x+b) mod p也是类型long。请注意，它((a*x+b) mod p)的结果是< p。让我们表示结果h_a_b(x)。
4. h_a_b(x)现在被采取了modulo m，这意味着在这一步它取决于m是否会有向下转换的数据类型。然而，这并不重要。h_a_b(x)是< m，因为我们把它modulo m。因此，的值h_a_b(x) modulo m适合m的数据类型。万一它必须被贬低，就不会有价值损失。所以你已经将一个键映射到一个 bin/bucket。