背景

字符串hash是特殊的hash方式。
利用把字符串转成p进制的方式，通过p进制的特性，利用前缀字符串的p进制的十进制表示(即hash值)，可以轻松计算出某一段子串的hash值。
比如说十六进制的字符串：abcd13456，前缀字符串的计算如下：

  1. prefix[1] = 16^0 * 10; // a --- 10
  2. prefix[2] = prefix[1]*16 + 11; // ab
  3. ...
  4. prefix[9] = prefix[8]*16 + 6; //abcd13456

如果我想计算’bcd’子串的hash值，直接通过进制来计算当然是OK的，但是计算复杂度比较高。我们尝试通过prefix的hash值来进行计算。

  1. hash_value['bcd'] = 'b'*16^2 + 'c'*16 + d;
  2. // the hash value above can be calculated with prefix[4] and prefix[1]
  3. // hash_value[2-4] = prefix[4] - prefix[1] * 16^3;
  4. prefix[1] = 'a';
  5. prefix[4] = 'a'*16^3 + 'b'*16^2 + 'c'*16 + d;
  7. hash_value['cd'] = 'c'*16 + d;
  8. // the hash value above can be calculated with prefix[4] and prefix[2]
  9. // hash_value[3-4] = prefix[4] - prefix[2] * 16^2;
  10. prefix[2] = 'a'*16^1 + b;
  11. prefix[4] = 'a'*16^3 + 'b'*16^2 + 'c'*16 + d;

note

利用字符串hash需要注意的两点：

  1. 不能有字符对应的p进制值为0(不然会有hash冲突)
  2. 假定没有hash冲突，其实按照进制的方式，是不会有hash冲突的，但是要存储的话，只能是有限的空间，一般的hash方式都是mod某个值。我们可以通过经验值保证大概率没有hash冲突。(通过经验值可以保证99.99%没有hash冲突，p = 131/13331， Q = 2^64)
  3. 一般情况下，字符对应的p进制的值，就是ASCII码的值。