使用多项式滚动哈希函数进行字符串哈希

引言

字符串匹配计算在软件工程领域产生了深远的影响，在解决不同领域的实际问题中发挥着基础性作用。在涉及在一个字符串中搜索另一个特定字符串的任务中，它们的效率尤为明显。字符串匹配方法在多个领域都有应用，例如数据库模式设计和网络系统。这些计算有助于优化任务的性能，证明了它们在解决现实世界挑战中的多功能性和相关性。字符串匹配问题：

时间复杂度：给定两个长度相同（设为 n）的字符串 s1 和 s2。比较这两个字符串 (s1==s2) 的时间复杂度是 O(n)。

哈希函数

哈希函数是一种将任意大小的数据转换为固定大小值的工具。这些生成的值通常被称为哈希值。哈希函数的主要目的是为给定数据集生成一个唯一的标识符，提供简洁的表示，而不考虑原始数据的大小或复杂性。

使用哈希的解决方案

时间复杂度：给定两个长度相同（设为 n）的字符串 s1 和 s2。现在，使用哈希比较，比较 (s1==s2) 两个字符串的时间复杂度是 O(1)（理想情况）。

字符串哈希

字符串 -> 哈希函数 -> 哈希值/键

上面提到的哈希函数将字符串作为输入，并生成一个称为哈希值或键的唯一值。

示例

假设我们给定的字符串 s1、s2 和 s3 作为输入到哈希值，分别生成了 109469、236853 和 945739。

现在，为了比较字符串，而不是直接比较它们（这将需要 O(max([s1],[s2]))），我们只需比较它们的哈希值，这只需要 O(1)。

要点

1. 相同的字符串必须具有相同的哈希值。
2. 相同的哈希值意味着字符串可能相同。

两个不同的字符串可能具有相似的哈希值。当两个不同的字符串具有相同的哈希值时，这被称为冲突。

多项式滚动哈希函数

我们希望高效地比较字符串。这个想法很简单，将字符串转换为整数（哈希值）并进行比较。

为了将它们转换为整数，我们将使用多项式滚动哈希作为哈希函数。相同字符串的哈希值应该相似。

多项式滚动哈希函数是一个仅使用乘法和加法的哈希函数。以下是该函数。

这里 p >= 字符集大小。

P 是任何素数。

例如，hash ("abc") = 1+2.5¹+3.5²=90

在这个例子中，a 映射到 1，b 映射到 2，依此类推，并且我们可以看到 p = 5，它是一个素数。

为什么我们要使用模运算？

因为哈希函数是多项式的，所以哈希值呈指数增长。

整数：10 个字符

长整型：20 个字符

例如 p：11

为什么 p 应该大于 |字符集|？

它应该大于字符集的长度，以减少冲突。如果我们取较小的值，发生冲突的可能性会更大。

多项式滚动哈希函数的简单代码实现

输出

多项式滚动哈希函数中的冲突及其解决方法

哈希函数输出一个范围在 [0, m) 的整数，这可能导致冲突，即不同的字符串产生相同的哈希值。例如，当使用 p = 37 和 m = 10^9 + 9 时，字符串 "answers" 和 "stead" 会产生相同的哈希值。在给定的 [0, m) 范围内，实现完美的 一对一 映射具有挑战性。

虽然较大的 m 会降低冲突的几率，但也会减慢算法的速度。实际限制，例如 C、C++ 和 Java 等语言中的整数大小限制，限制了 m 超过特定限制的增加。为了减轻冲突概率，一种策略是使用不同的参数对 (p, m) 为给定的字符串生成一对哈希值。这种方法并不能完全消除冲突，但可以大大降低其概率。

结论

使用多项式滚动哈希函数的哈希字符串技术，将字符串转换为整数以便进行高效比较。该函数依靠乘法和加法来实现简单性和有效性。选择素数作为参数对哈希值有显著影响。模运算对于维持哈希值的指数增长至关重要。当与精心选择的参数和冲突解决方法一起使用时，多项式滚动哈希函数提高了字符串匹配算法的效率和可靠性，使其成为各种计算应用中的宝贵工具。