哈希的应用优秀课件.ppt

哈希的应用 基本概念 很简单，哈希就是标记数组。我们把需要保存的状态（例如一列数、一个字符串等）用一个数代替，再存到一个数组中，这个数组就称为哈希数组。 为此，我们须要设计一个将状态对应到数的函数，称为哈希函数。 哈希函数 设计方法有很多，例如对于字符串S： hash(s)=((s[0]*256+s[1])*256+s2)*256+s[3]…… 或 hash(s)=s[0]*s[1]*s[2]*… 不过，这样哈希值可能会变得很大，以致于无法存到一个数组中。 所以在此基础上我们还要把哈希值模一个大质数，但这样有可能出现哈希冲突。 解决冲突 方法一般有二： 闭散列：当出现冲突时，一直往后寻找没有被占有的哈希值，找到后再插入； 开散列：开一个二维哈希数组hash，设当前要插入的哈希值为h，若hash[h][0]未被占则插入hash[h][0]，否则查询hash[h][1]是否被占，未被占则插入hash[h][1]…… 应用：RK算法 这是一个基于哈希的字符串匹配算法。效率略低于kmp。 具体方法曾经讲过，这里再提一下： 设母串为a，子串为b，子串长度为lenb,则我们可以求出a[0]~a[lenb-1]，a[1]~a[lenb]……这些字符串的哈希，再与b的哈希值比较，若相等则“极有可能”匹配。此时再一个一个比对就可以确认是否的确匹配。 RK算法 现在问题是如何很快算出a[i]~a[i+lenb-1]的哈希。 定义哈希函数hash(s)=((s[0]*256+s[1])*256+s2)*256+s[3]…… 则已知a[i-1]~a[i+lenb-2]的哈希值则可以很快推出a[i]~a[i+lenb-1]的哈希值。 应用：小藩的LCS（最长公共子串）问题。 LCP问题 给你一个字符串S及很多询问q(i,j)，问s[i]~s[len-1]与s[j]~s[len-1]的最长公共前缀长度是多少。要求O(nlogn)的时间复杂度。 例：S=“bcbaabcbaabbac” q(1,6)=5 （即“cbaab”） 方法很多，如后缀数组、后缀树等等。 不过这些方法特点明显：常数大、代码繁重。 LCP哈希算法 定义f[i][j]为s[i]~s[i+2j-1]的哈希值。在计算f[i][j]时，可以从f[i][j-1]与f[i+2j-1-1][j-1]的值（也就是这个子串的左半部分与右半部分的哈希值推出。） 例如，我们定义哈希函数为把所有字符乘起来，则f[i][j]=f[i][j-1]* f[i+2j-1-1][j-1]再模一个大质数，其余函数自己推就可以了。 LCP哈希算法 既然是哈希，那么两个哈希值相等则两个字符串很可能相等。实在对RP不放心可以多用几个哈希函数，再逐一比较。 当询问q(i,j)时，（设i=j） 先令k=log2(len-j+1)，比较f[i][k]与f[j][k]。 若f[i][k]==f[j][k]，说明s[i]~s[i+2k-1]与s[j]~s[j+2k-1]相等，那么i=i+2k ,j=j+2k ,k--，答案累加k。 否则说明k过大，则k--。 由于运用了倍增思想，时间复杂度O(nlogn)。