华师一附中OI组

标题: 字符串哈希技术 [打印本页]

作者: admin 时间: 2020-2-18 14:01
标题: 字符串哈希技术
即将一个字符串转化成一个整数，并保证字符串不同,得到的哈希值不同，这样就可以用来判断一个该字串是否重复出现过。
考试使用这种方法效率很高，不用写教复杂的KMP算法。
（如果直接把string当做键，则每次在map中查找时要一个一个字符地找，跟存在数组中每区别，比较数值当然更快。）

由哈希函数的性质，对于一个字符串：S=s1s2...sn,我们把每个字符转换成idx(si)=si-'a'+1 当然直接用字符串的ASCII码表示也可以，则哈希模型为Hash(i)=Hash(i-1)*p+idx(si),其中p为素数。最终算出的Hash(n)作为该字符串的哈希值。所以构造哈希函数的关键点在于使不同字符串的哈希冲突率尽可能小。下面介绍几种哈希函数：

1、自然溢出方法：利用unsigned long long 自然溢出,相当于自动对2^64−1取模
   定义哈希函数：unsigned long long hash[n];
   公式：Hash(i) = Hash(i-1)*p+idx(si)
2、单哈希方法
   公式：Hash[i] = (Hash[i-1]*p+idx(si))%mod
   p,mod均为质数，p<mod，p,mod取尽量大时冲突很小
3、双哈希方法：将字符串用不同mod单哈希两次，结果用二元组表示
   Hash1(i) =(Hash1(i-1)*p+idx(si))%mod
   Hash2(i) =(Hash2(i-1)*p+idx(si))%mod
   Hash[i]:<Hash1[i],Hash2[i]>
   这种方法很安全，清北学堂讲课的大神说好像还没有一个被卡的例子。

欢迎光临华师一附中OI组 (http://hsyit.cn/)