【字符串】字符串哈希

目录

字符串哈希

哈希

字符串的哈希冲突：

字符串哈希的思想

字符串哈希的基本运算

acwing 138. 兔子与兔子

哈希就是将所要处理的数据转化成数字，且这个数字能唯一地去对应上这个数据，若这个数字对应上了多个数字，则称作哈希冲突。比如\(k_{1}!=k_{2}\),但\(hash(k_{1})=hash({k_{2}})\)

概念:字符串哈希是指将一个任意长度的字符串映射成一个非负整数,并且冲突的概率几乎为0.

冲突：两个字符串不相等，但是他们的p进制数相同

将字符串看成一连串的数字,字符串里的每一位看成在某一个特定位置上的单独的数字,并对这个数字赋予一定的权值,设为p(也用p来指说字符串可以看成是一个p进制数),这时候我们可以将由代表这个字符串的p进制数转化成十进制数, 并向一个固定的数m取余(m代表的是哈希值的范围).

p一般取131或者13331,如果题目的字符串仅有小写字母,可以考虑取26.

m可以设置成是2的64次方(只需unsigned long long),一方面,超出上界(溢出)后,数值会自动从0开始计算,这种天然的取余操作相比于再去使用mod取余操作会更高效.(面向一些大质数取余,比如1e9,能减少哈希冲突的概率(数论的知识,还不太懂)),另一方面,unsigned long long 具有数据范围大,能容纳的哈希值更多.

例子: 我们将a~z一一与1到26对应

\(hash("abcb")=a*p^{3}+b*p^{2}+c*p^{1}+b*p^{0}\)

已知某一字符串的哈希值,在其字符串的尾巴继续添置一个字母,求新组成的字符串的哈希值.

\(hash("abcb"+'d') =hash("abcbd")=(a*p^{4}+b*p^{3}+c*p^{2}+b*p^{1}+d=hash("abcb")*p+d)\%\space mod\)

进而我们有,已知字符串s和字符串t的哈希值,求s+t的哈希值

\[h(s+t)=(h(s)\times p^{len-of-t}+h(t))\% \space mod$$​

\]

\[h(t) =(h(s+t)-h(s)*p^{len-of-t})\%\space mod$$​​