字符串hash以及7大问题

《字符串hash以及7大问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1Bypeterpan字符串hash简介&有关字符串hash的7个问题！字符串hash关于字符串hash，就一句话：把字符串有效地转化为一个整数在计算机里，用的是二进制编码。在很多语言里，都是用数字作为数组的下标。因为用数字来存储、表达一个object非常方便。如果能有一种算法，把每个字符串有效地、”唯一”的映射到每个“不同”的整数，我们就能很好的处理字符串。hash函数现在我们希望找到一个hash函数，使得每一个字符串都能够映射到一个整数上比如hash[i]=(hash[i-1]*p+idx(s[i]))%mod字符串：abc，bb

2、c，aba，aadaabac字符串下标从0开始先把a映射为1，b映射为2，c->3，d->4,即idx(a)=1,idx(b)=2,idx(c)=3,idx(d)=4；好！开始对字符串进行hashhash函数假设我们取p=13，mod=101先把abc映射为一个整数hash[0]=1，表示a映射为1hash[1]=(hash[0]*p+idx(b))%mod=15，表示ab映射为15hash[2]=(hash[1]*p+idx(c))%mod=97这样，我们就把abc映射为97这个数字了。hash函数用同样的方法，我们可以把bbc，a

3、ba，aadaabac都映射到一个整数用同样的hash函数，得到如下结果abc->97bbc->64aba->95aadaabac->35那么，我们发现，这是一个字符串到整数的映射hash函数这样子，我们就可以记录下每个字符串对应的整数，当下一次出现了一个已经出现的字符串时，查询整数是否出现过，就可以知道字符串是否重复出现。现在要判断两个字符串是否一致，怎么办呢？直接用它们的hash值判断即可，若hash值一致，则认为字符串一致；若hash值不一致，则认为是不同的字符串。hash我们要判断两个字符串是否一致，没有那么麻烦，直接先判断长

4、度是否一致，然后再判断每个对应的字符是否一致即可。但，如果要判断多个字符串里有多少个不同的字符串，怎么办呢？两两字符串都进行比较？时间复杂度太高把每个字符串hash成一个整数，然后把所有整数进行一个去重操作，即可知道答案了。我们来具体看下这个问题。关于hash的简单问题问题：给N个字符串，每个字符串长度不超过100，问这些字符串里有多少个不同的字符串？即相同字符串只取一个，最后剩下多少字符串？数据范围：1=

5、不超过100Output输出一个整数，表示有多少个不同的串。样例SampleInput7aaaaaababbaabaabcdebbaSampleOutput4解释：很显然，左边字符串集去重后只剩4个字串aaaaa，ababba，abcde解题方法：hash用hash来做.我们把每个字符串hash为一个整数，这样每个整数都表示成一个字符串把N个字符串存下来，排个序，去重，剩下多少个整数，就表示去重后有多少个字符串当然，也可以用字典树来解。但字典树耗内存会比hash大得多hash算法的问题！我们想，刚才给出的hash函数hash[i]=(

6、hash[i-1]*p+idx(s[i]))%mod并且我们取的是p=13，mod=101；这样做真的不会有问题吗？实际上是会有的，问题就是冲突！有没有可能两个不同的字符串，映射到了一个整数上，这样子就会导致结果出错？可能！怎么解决呢？字符串hash解决的方法非常简单，想办法调整p和mod，使得冲突概率减小之又小。那么怎么调整才能使冲突概率小之又小呢？一句话告诉你，p取一个较大素数，mod取一个大素数。习惯上，p取一个6到8位的素数即可，mod一般取大素数1e9+7（1000000007）或1e9+9（1000000009）可是，为什

7、么这样做就会冲突概率小之又小？hash的解释我们想，如果mod取的很小，mod=97，或者更小，mod=13，它与mod取一个大数相比，比如1e9+7=1000000007，是不是冲突的概率就会更大？同时考虑p，p取2，相比p取一个较大的素数，是不是冲突的概率会更大？换句话说，我们希望取得一个p和mod，使得这个函数”越乱越好”，“越没有规律越好”，这样才能降低冲突的概率！p和mod的取法我们一般认为p和mod一般取素数，p取一个较大的素数即可（6位到8位），mod取一个大素数，比如1e9+7，或者1e9+9。具体为什么这样做就能够大

8、概率地避免冲突，或者它具体的概率是多少，若想钻研，请google但，可以肯定的是，这样子的取法，冲突的概率非常低！低到我们可以基本放心地去用这个函数解决一般的hash问题。如何求一个子串的hash值？实在抱歉，算法讲座的