字符串哈希相关问题
如何对一个字符串进行哈希呢？
字符串哈希公式
\[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
哈希函数的应用场景：散列表中用于确定元素在散列表中的位置。
那么上述的哈希公式会不会问题呢？
是有的，就是当输入的元素越来越多时，难免会出现哈希碰撞。这种情况对于一些需要唯一值的场景就很搞。
那么有什么解决方法吗？
最简单的方法，就加多一个哈希函数，采用双哈希的方法，来确定唯一值。一般这种方法基本不会出现哈希碰撞。
除了哈希碰撞外，这个公式还有其他问题吗？
没错，当字符串长度大到一定程度时会溢出。
此时，可以采用取模来解决此问题。
\[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} \]相关算法题：