Go：用于字符串比较的多项式指纹。

Question

我想实现一个滚动的哈希函数来进行字符串比较（Rabin-Karp）。

要做到这一点，我将输入的字符串转换为一个字节片（使用go unicodeutf8），并对其进行 "多项式指纹 "函数操作。

例如，我输入的字符串是 qwerty 译为 [113 119 101 114 116 121] 我用的是基座 256

rune 121, base 256.0, exponent 0, value 121
rune 116, base 256.0, exponent 1, value 29696
rune 114, base 256.0, exponent 2, value 7471104
rune 101, base 256.0, exponent 3, value 1694498816
rune 119, base 256.0, exponent 4, value 511101108224
rune 113, base 256.0, exponent 5, value 124244813938688

我对 "多义性指纹 "的概念有疑问：很快，基数就会变得非常大，如何能与用户想要匹配的字符串相匹配？

在我的使用案例中，它在7个字符之后就会变得一团糟，因为Go的 math.Pow 函数使用float64类型

rune 114, base 256.0, exponent 7, value 8214565720323784704
rune 101, base 256.0, exponent 8, value -9223372036854775808
rune 119, base 256.0, exponent 9, value -9223372036854775808
rune 113, base 256.0, exponent 10, value -9223372036854775808

我觉得用uint64只是把问题往前推一下而已

Answer 1

哈希函数的概念其实是它会溢出，但概率很高，不同的字符串会给出不同的哈希值。为了使其工作，你需要使用共质数来作为运算的基数和模数。你应该使用一些质数基数（大于字母大小），并执行所有的操作模数一些质数（尽可能大）（质数将导致最小的碰撞机会）。对这个哈希使用整数类型。如果你需要你的字母表至少是256个符号，你可以使用uint64，基数257，并执行所有的操作，例如，模数10。¹²+39