【字元串】字元串哈希

目錄

字元串哈希

哈希

字元串的哈希沖突：

字元串哈希的思想

字元串哈希的基本運算

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$$​​