hash - 是否可以为整个整数范围实现通用哈希？

Question

我正在阅读 Universal hashing在整数上。 先决条件并且强制性的前提似乎是我们选择了 素数p大于所有可能键的集合 .

这一点我不清楚。

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

但最终无论我们得到什么作为散列都需要向下转换为 int 以索引散列表。这种向下转换不会以某种方式影响通用哈希的质量(我指的是键在存储桶上的分布)吗？

Answer 1

If our set of keys are integers then this means that the prime number needs to be of the next bigger data type e.g. long.

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

But eventually whatever we get as the hash would need to be down-casted to an int to index the hash table.

Doesn't this down-casting affect the quality of the Universal Hashing (I am referring to the distribution of the keys over the buckets) somehow?

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

是否 p是否具有另一种数据类型对于散列系列是否通用并不重要。重要的是 p等于或大于 u (整数域的最大整数)。重要的是 p足够大(即 >= u )。

A hash family is universal when the collision probability is equal or smaller than 1/m.

所以我们的想法是保持这个约束。
p的值，理论上可以和 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 ，箱/桶的数量)；但这里也是数据类型(值域无关紧要)。见 Hashing integers on Wikipedia为符号。

关注 proof on Wikipedia你得出的结论是碰撞概率是 _p/m_ * 1/(p-1) (下划线表示截断小数)。对于 p >> m ( p 远大于 m )概率趋于 1/m (但这并不意味着 p 越大，概率会越好)。

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

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

设 U 是对应于 unsigned char 的整数的全域(例如在 C 中)。然后U = {0, ..., 255}

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

下一个可能的质数是 257 .

我们说我们有 25桶，即 m = 25 .这意味着如果碰撞概率等于或小于 1/25，哈希族将是通用的。 ，即大约 0.04 .

输入 _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我们稍后会在示例中看到

选择 p使其大于最大值 u ( |U| 的元素), p类型为 long .

选择 a和 b (模 p )随机。它们的类型是 long ，但总是< p .

对于 x (类型 int 来自 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) .

h_a_b(x)现在被占用 modulo m ，这意味着在这一步它取决于 m 的数据类型是否会出现低迷。然而，这并不重要。 h_a_b(x)是 < m ，因为我们把它modulo m . 因此 h_a_b(x) modulo m 的值适合 m的数据类型。万一它必须被贬低，就不会有值(value)损失。 所以你已经将一个键映射到一个 bin/bucket。