哈希值的算术运算

Question

是否有在算术运算中关闭的散列算法？更具体地说，如果a和b是两个整数，那么是否有任何哈希算法hash满足：hash(a + b) == hash(a) + hash(b) (以及类似于-、*、/)？是否有可能以某种方式修改这些操作符以达到这一条件？

Answer 1

假设h(a+b) = h(a) + h(b)。使用归纳，您可以显示h(c * a)，如果c是一个常量，则等于h(c*a) = c * h(a)。因此，它意味着函数h必须是线性的(根据线性代数中线性映射的定义)，并且每一个线性函数，例如h(x) = c * x (c是一个整数和常数)都可以回答您的问题。但是，它是线性的，不会是一个有用的散列函数！此外，您也可以对-进行同样的操作。

对于乘法，它可能更复杂。h(a*b) = h(a)*h(b)。你可以从这个方程中得到，对于每一个常数m，我们都可以得到h(a^m) = h(a)^m。现在，就像现在一样，我们可以用x = p_1^a_1 * p_2^a_2 * ... * p_k^a_k这样的因子来编写每个数字，所有的p_i都是素数。因此，h(x) = h(p_1)^a_1 * h(p_2)^a_2 * ... * h(p_k)^a_k。因此，质数上的h值很重要，其他值将由这些值决定。

Answer 2

是否有可能以某种方式修改这些操作符以达到这一条件？

是的:取消散列。因此，对于任何运算符a·b，计算散列(散列⁻(A)·散列⁻(B))。

这适用于任何双射散列，典型的整数散列都属于这一类:乘奇常量的组合，按位旋转的组合，按常数的异或，加常数，特定的异或/移位。例如，Murmurhash终结器。

对于哈希和运算符的某些组合，它更容易一些，例如乘法散列是线性的，因此它已经分布在加法和减法上。