Horner 的哈希方法

Question

我知道如何通过 Horner 的方法获取字符串的哈希值，该方法采用三个参数

String str , int p (prime) and int

m 像这样

p(str)=( sumOf(str(0)+str(1)*M+....+str(n)*M^n) )%p = hashVal

但问题是如何通过仅给出 hashVal、p 和 M 来获取字符串 str，例如，如果我给你

hashval=7

、

p = 11

和

M = 2

，你必须给我一个字符串，例如“hello”（不是正确只是一个理解建议）

我的意思是我不知道如何做相反的事情 感谢您的帮助

Answer 1

您无法从您描述的哈希中获得唯一的输入，因为模运算会丢弃信息。如果您知道 hashval 为 7、M=2 且 p=11（如您的示例所示），您将不知道 sumOf(...) 是 7 还是 18 等。

即使您知道，假设您知道它是 5，例如，对于 2 个字符的字符串，您也无法计算出 str(0) 是否为 1，str(1) 是否为 2，或者 str( 0) 为 5，str(1) 为 0。

哈希通常很难/不可能逆转，尤其是唯一的。解决它们的最简单方法是散列所有可能的输入并检查它们的输出。您最终会得到许多具有相同 hashVal 的输入（如果示例中的 p 是 3，则只有 3 个不同的哈希值）。