0

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

为此，我将输入字符串转换为字节切片（使用 go unicode/utf8）并在其上运行“多项式指纹”功能。

例如，我输入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

我对“多项式指纹”的概念有疑问：很快，基础变得非常大，如何随着用户想要匹配的字符串输入进行扩展？

在我的用例中，因为 Gomath.Pow函数使用 float64 类型，所以在 7 个字符后它会变得混乱

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 只会使问题向前一点

4

1 回答 1

1

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

于 2020-05-03T12:32:14.317 回答