2023-11-08：用 go 语言，字符串哈希原理和实现比如 p = 233, 也就是课上说的选择的质数进制 “ 3 1 2 5 6 ...“ 0 1 2 3 4 hash[0] = 3 * p 的 0

作者：福大大架构师每日一题

2023-11-08
北京
本文字数：2795 字
阅读完需：约 9 分钟

2023-11-08：用 go 语言，字符串哈希原理和实现

比如 p = 233, 也就是课上说的选择的质数进制

" 3 1 2 5 6 ..."

0 1 2 3 4

hash[0] = 3 * p 的 0 次方

hash[1] = 3 * p 的 1 次方 + 1 * p 的 0 次方

hash[2] = 3 * p 的 2 次方 + 1 * p 的 1 次方 + 2 * p 的 0 次方

hash[3] = 3 * p 的 3 次方 + 1 * p 的 2 次方 + 2 * p 的 1 次方 + 5 * p 的 0 次方

hash[4] = 3 * p 的 4 次方 + 1 * p 的 3 次方 + 2 * p 的 2 次方 + 5 * p 的 1 次方 + 6 * p 的 0 次方

次方是倒过来的，课上讲错了

所以 hash[i] = hash[i-1] * p + arr[i]，这个方式就可以得到上面说的意思

于是，你想得到子串"56"的哈希值

子串"56"的哈希值 = hash[4] - hash[2]*p 的 2 次方(就是子串"56"的长度次方)

hash[4] = 3 * p 的 4 次方 + 1 * p 的 3 次方 + 2 * p 的 2 次方 + 5 * p 的 1 次方 + 6 * p 的 0 次方

hash[2] = 3 * p 的 2 次方 + 1 * p 的 1 次方 + 2 * p 的 0 次方

hash[2] * p 的 2 次方 = 3 * p 的 4 次方 + 1 * p 的 3 次方 + 2 * p 的 2 次方

所以 hash[4] - hash[2] * p 的 2 次方 = 5 * p 的 1 次方 + 6 * p 的 0 次方

这样就得到子串"56"的哈希值了

抱歉，课上讲错了。应该是上面的方式。

所以，子串 s[l...r]的哈希值 = hash[r] - hash[l-1] * p 的(r-l+1)次方

也就是说，hash[l-1] * p 的(r-l+1)次方，正好和 hash[r]所代表的信息，前面对齐了

减完之后，正好就是子串 s[l...r]的哈希值。

来自左程云。

答案 2023-11-08：

go 和 c++代码用灵捷 3.5 编写，不需要修改。

大体过程如下：

rightCheck 函数的过程：

1.检查 l1 和 l2 是否超出字符串边界，如果超出则返回 false。

2.如果 l1 和 l2 相等，则直接返回 true。

3.判断从 l1 开始长度为 length 的子串和从 l2 开始长度为 length 的子串是否相等，如果相等则返回 true，否则返回 false。

hashCheck 函数的过程：

1.计算 l1 到 r1 和 l2 到 r2 两个子串的哈希值。

2.检查 r1 和 r2 是否超出字符串边界，如果超出则返回 false。

3.根据哈希值判断两个子串是否相等，如果相等则返回 true，否则返回 false。

rightCheck 函数的时间复杂度：O(length)

hashCheck 函数的时间复杂度：O(1)

rightCheck 函数的额外空间复杂度：O(1)

hashCheck 函数的额外空间复杂度：O(1)

go 完整代码如下：

package main
import (  "fmt"  "math/rand")
const MAXN = 100005
var pow [MAXN]int64var hash [MAXN]int64var base = 499
func rightCheck(str string, l1 int, l2 int, length int) bool {  if l1+length > len(str) || l2+length > len(str) {    return false  }  if l1 == l2 {    return true  }  return str[l1:l1+length] == str[l2:l2+length]}
func build(str string, n int) {  pow[0] = 1  for j := 1; j < n; j++ {    pow[j] = pow[j-1] * int64(base)  }  hash[0] = int64(str[0]-'a') + 1  for j := 1; j < n; j++ {    hash[j] = hash[j-1]*int64(base) + int64(str[j]-'a') + 1  }}
func hashCheck(n, l1, l2, length int) bool {  r1 := l1 + length - 1  r2 := l2 + length - 1  if r1 >= n || r2 >= n {    return false  }  return hashf(l1, r1) == hashf(l2, r2)}
func hashf(l, r int) int64 {  var ans int64  ans = hash[r]  if l == 0 {    ans -= 0  } else {    ans -= hash[l-1] * pow[r-l+1]  }  return ans}
func randomString(length, v int) string {  str := make([]byte, length)  for i := 0; i < length; i++ {    str[i] = byte('a' + (int64(v)*int64(i))%26)  }  return string(str)}
func main() {  test := "abcabcabcabcabcabcabcabc"  size := len(test)  build(test, size)  fmt.Println(hashCheck(size, 6, 15, 3))
  fmt.Println("测试开始")  N := 10000  V := 3  testTeams := 100  testTimes := 5000  LEN := 6  for i := 0; i < testTeams; i++ {    n := (int)(rand.Float64()*float64(N)) + 1    str := randomString(n, V)    build(str, n)    for k := 0; k <= testTimes; k++ {      l1 := (int)(rand.Float64() * float64(n))      l2 := (int)(rand.Float64() * float64(n))      length := (int)(rand.Float64()*float64(LEN)) + 1      ans1 := rightCheck(str, l1, l2, length)      ans2 := hashCheck(n, l1, l2, length)      if ans1 != ans2 {        fmt.Println("出错了!")        break      }    }  }  fmt.Println("测试结束")}

复制代码

c++完整代码如下：

#include <iostream>#include <string>#include <cstdlib>using namespace std;
const int MAXN = 100005;long long pow0[MAXN];long long hashArr[MAXN];int base = 499;
bool rightCheck(string str, int l1, int l2, int len) {    if (l1 + len > str.length() || l2 + len > str.length()) {        return false;    }    if (l1 == l2) {        return true;    }    return str.substr(l1, len) == str.substr(l2, len);}
void build(string str, int n) {    pow0[0] = 1;    for (int j = 1; j < n; j++) {        pow0[j] = pow0[j - 1] * base;    }
    hashArr[0] = str[0] - 'a' + 1;    for (int j = 1; j < n; j++) {        hashArr[j] = hashArr[j - 1] * base + str[j] - 'a' + 1;    }}
bool hashCheck(int n, int l1, int l2, int len) {    int r1 = l1 + len - 1;    int r2 = l2 + len - 1;    if (r1 >= n || r2 >= n) {        return false;    }    return hashArr[l1 + len - 1] - (l1 == 0 ? 0 : hashArr[l1 - 1] * pow0[len]) == hashArr[l2 + len - 1] - (l2 == 0 ? 0 : hashArr[l2 - 1] * pow0[len]);}
string randomString(int len, int v) {    string str;    for (int i = 0; i < len; i++) {        str += char('a' + rand() % v);    }    return str;}
int main() {    string test = "abcabcabcabcabcabcabcabc";    int size = test.length();    build(test, size);    cout << hashCheck(size, 6, 15, 3) << endl;
    cout << "测试开始" << endl;    int N = 10000;    int V = 3;    int testTeams = 100;    int testTimes = 5000;    int LEN = 6;    for (int i = 0; i < testTeams; i++) {        int n = rand() % N + 1;        string str = randomString(n, V);        build(str, n);        for (int k = 0; k <= testTimes; k++) {            int l1 = rand() % n;            int l2 = rand() % n;            int len = rand() % LEN + 1;            bool ans1 = rightCheck(str, l1, l2, len);            bool ans2 = hashCheck(n, l1, l2, len);            if (ans1 != ans2) {                cout << "出错了!" << endl;                break;            }        }    }    cout << "测试结束" << endl;
    return 0;}