10

我正在阅读有关整数的通用散列。前提和强制性前提似乎是我们选择的质数p大于所有可能键的集合。

我不清楚这一点。

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

但最终我们得到的任何哈希值都需要向下转换为 int 来索引哈希表。这种向下转换不会以某种方式影响通用哈希的质量（我指的是密钥在桶上的分布）吗？

4

1 回答 1

6

如果我们的键集是整数，那么这意味着质数需要是下一个更大的数据类型，例如 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)}为h(a,b)(x) = ((a * x + b) mod p) mod m。注意a和是b随机选择的整数（从所有可能的整数中，因此理论上可以大于p）模素数p（这可以使它们小于或大于m，箱/桶的数量）；但这里也是数据类型（值域无关紧要）。有关符号，请参阅Wikipedia 上的散列整数。
  • 按照Wikipedia 上的证明，您得出的结论是碰撞概率为_p/m_ * 1/(p-1)（下划线表示截断小数）。对于p >> m（p远大于m），概率趋于1/m（但这并不意味着概率越大越好p）。

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

也许一个数学例子可以帮助

  • 令 U 是对应于unsigned char（例如在 C 中）的整数的全域。然后U = {0, ..., 255}

  • 让p（下一个可能的）素数等于或大于256。请注意，p可以是这些类型中的任何一种（short, int，long无论是有符号的还是无符号的）。关键是数据类型不起作用（在编程中，类型主要表示值的域。）。为了数学证明的正确性，这里是否真的很重要257。我们也可以选择更大的（即更大的数据类型）；这不会改变证明的正确性。shortintlongp

    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的类型）计算。是类型的，也是类型的，所以也是类型的。请注意，结果是. 让我们表示这个结果。intU((a*x+b) mod p)a*xlong(a*x+b)long((a*x+b) mod plong((a*x+b) mod p)< ph_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。
于 2015-07-08T20:31:18.257 回答