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

最近发现不少小伙伴都对Golang很感兴趣，所以今天继续给大家介绍Golang相关的知识，本文《多项式指纹：用于比较字符串的Go方案》主要内容涉及到等等知识点，希望能帮到你！当然如果阅读本文时存在不同想法，可以在评论中表达，但是请勿使用过激的措辞~

我想实现一个滚动哈希函数来进行字符串比较（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

我对“多项式指纹”的概念遇到了麻烦：很快，基数就变得非常大，如何能够随着用户想要匹配的字符串输入进行扩展？

在我的用例中，它在 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 只会让问题稍微向前推进

解决方案

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

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《多项式指纹：用于比较字符串的Go方案》文章吧，也可关注golang学习网公众号了解相关技术文章。