何为字符串哈希
, j- E# j' G& k1 j7 S. Z. l3 Q* {所谓字符串哈希，即对一个字符串形成单向加密的过程，使其拥有尽可能独一无二的编号，通过这种低概率的编号重复，使得字符串的匹配尽可能高效。# v% l) B, o1 \: v6 t' D2 r
如何字符串哈希9 i  ^* f' d; Y
最普遍的字符串哈希方式，即进制哈希。核心是将字符串上的每一个字符理解为一个数字，然后固定一个进制，将该字符串转化成一个该进制下的的数，作为其哈希值，然后通过比对哈希值，判断两个字符串是否相等。7 d4 P. U0 J6 `! e: c
ll Hash(char s[])
2 a  [9 t1 [1 S( n{# a$ S; f  i9 h* U
        int len = strlen(s);  M, \. T- u( t) [
        ll ans = 0;
- e+ f! M& s  O: q        for (int i = 0; i
: f% R/ P3 ~( U4 F9 |& ]* x9 L5 X而对于再好的哈希，也不可避免会产生冲突，此时可以通过一些方法来尽可能降低哈希冲突。
' F( }! L  o& i' O/ Q' h1.无错哈希
7 y- i2 ~/ U3 c  a* C, x/ M: r原理就是当一个字符串得到一个哈希值后，判定该哈希值是否已经使用过，如果使用的话就不断加上一个大质数，使得不产生冲突。该方式的缺陷在于会十分消耗空间。3 u* h# [/ N' @$ l. y; l
2.多重哈希% Q& G: [% O; p) E
给定不唯一的哈希函数，对每一个字符串生成多个哈希值，由此来判断两个字符串是否相等。该方法会增加空间和时间，但也提高了正确性。