本文主要是介绍字符串哈希相关问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

字符串哈希相关问题

如何对一个字符串进行哈希呢？

字符串哈希公式

\[str[i]: 表示字符串第i个位置的字符 \\ P: 质数 \\ \begin{aligned} hash(str[0..n]) &= str[0] * P ^ n + str[1] * P ^ {(n - 1)} + \cdots + str[n] * P ^ 0 \\ &= hash(str[0..{n - 1}]) * P + str[n] \end{aligned} \]

哈希是指☞将元素映射为一个确定的数值。

input: anything
output: number

• 参考文章：https://blog.csdn.net/u012835097/article/details/79407591

---

哈希函数的应用场景：散列表中用于确定元素在散列表中的位置。

那么上述的哈希公式会不会问题呢？

是有的，就是当输入的元素越来越多时，难免会出现哈希碰撞。这种情况对于一些需要唯一值的场景就很搞。

那么有什么解决方法吗？

最简单的方法，就加多一个哈希函数，采用双哈希的方法，来确定唯一值。一般这种方法基本不会出现哈希碰撞。

除了哈希碰撞外，这个公式还有其他问题吗？

没错，当字符串长度大到一定程度时会溢出。

此时，可以采用取模来解决此问题。

\[hash(str[0..n]) = ((hash({n - 1}) * P\quad mod \quad N) + str[n])\quad mod \quad N \]

如何求子串的哈希值？

\[\begin{aligned} hash(str[i..j]) &= hash(str[0..j]) - hash(str[0..{i-1}]) * P ^ {(j - i + 1)} \\ &= (str[0] * P ^ j + str[1] * P ^ {(j - 1)} + \cdots + str[{i-1}] * P ^ {(j - i + 1)} + \cdots + str[j] * P ^ 0) - (str[0] * P ^ {(i - 1)} + str[1] * P ^ {(i - 2)} + \cdots + str[{i - 1}] * P ^ 0) * P ^ {(j - i + 1)} \\ &= (str[0] * P ^ j + str[1] * P ^ {(j - 1)} + \cdots + str[{i-1}] * P ^ {(j - i + 1)} + \cdots + str[j] * P ^ 0) - (str[0] * P ^ j + str[1] * P ^ {(j - 1)} + \cdots + str[{i - 1}] * P ^ {(j - i + 1)}) \\ &= str[i] * P ^ {(j - i)} + \cdots + str[j] * P ^ 0 \end{aligned} \]

相关算法题：

• 重复的DNA序列
• 最长重复子串

这篇关于字符串哈希相关问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！