哈希的应用 ppt课件.ppt

哈希的应用
*
哈希的应用
基本概念
很简单，哈希就是标记数组。我们把需要保存的状态（例如一列数、一个字符串等）用一个数代替，再存到一个数组中，这个数组就称为哈希数组。
为此，我们须要设计一个将状态对应到数的函数，称为哈希函数。
*
哈希的应用
精品资料
3
你怎么称呼老师？
如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？
你所经历的课堂，是讲座式还是讨论式？
教师的教鞭
“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘 ……”
“太阳当空照，花儿对我笑，小鸟说早早早……”
4
哈希函数
设计方法有很多，例如对于字符串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]的哈希值。
应用：小藩的