algorithm - Go:用于字符串比较的多项式指纹

Question

我想实现滚动哈希函数来进行字符串比较(Rabin-Karp)

为此，我将输入字符串转换为一个 byte slice (使用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

我对“一元指纹”的概念感到烦恼:很快，这个基数就变得很大了，如何根据用户想要匹配的字符串输入来缩放？

在我的用例中，因为Go math.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只会使问题向前发展

Answer 1

散列函数的想法实际上是它会溢出，但是很有可能，不同的字符串会产生不同的哈希值。为了使其起作用，您需要对操作的基数和模数使用互质数。您应该使用一些素数基数(大于字母的大小)，并以所有素数(尽可能大)执行所有运算模数(素数将导致最小的碰撞机会)。为此哈希使用整数类型。如果您需要字母至少为256个符号，则可以使用uint64(基数为257)并执行所有操作，例如模数1012 + 39