哈希在競賽中也是一個很常用，且非常厲害的一個算法。

哈希的主要思想就是把一個東西轉換成一個大整數，這樣比較兩個東西是否相等的就只要比較兩個整數是否相等就行了，
比較的時間復雜度是O(1)的。

舉一個比較常見的例子：比較倆字符串是否相等，我們可以將字符串變成一個值，然后直接比較這倆字符串的哈希值就行了。
可能你會有疑問？在c++中string 不是可以直接就比較了么？ 為啥還要用哈希呢？
假如人家問的是倆矩陣是否相等呢？假如人家問這個矩陣是否在一個大矩陣中出現過呢？
那么如何存矩陣呢？我們就可以用二維哈希，將矩陣也映射成一個哈希值，這樣比較矩陣直接比較哈希值就行了。

其實，通過上面你已經對哈希有了一個初步的了解了。哈希它其實就是將一些特別難存的東西，通過某種手法變成一個唯一的值，
然后只需比較哈希值就行了。

哈希常見的幾種模型：

• 一維哈希(字符串)
• 二維矩陣哈希

核心思想：將字符串看成P進制數，P的經驗值是131，13331，233,2333,10007等質數 取這些值的沖突概率低
取模的時候選一個較大的質數避免沖突。
小技巧：取模的數用2^64，這樣直接用unsigned long long存儲，溢出的結果就是取模的結果

一維哈希模板：

typedef long long int LL; const int M=233;//是我們自己選擇的進制數，一般可以選233,2333,10007等質數 const int mod=1e9+7;//一般選一個比較大的質數 LL get(string s)//獲取字符串對應的哈希值 {LL sum=0;for(int i=0;i<s.size();i++) sum=(sum*M+s[i]-'a')%mod;return sum; } typedef unsigned long long int ull; const int N=1e5+10; const int M=233; ull h[N],base[N]; ull query(int l,int r)//獲取字符串[l,r]的哈希值 {return h[r]-h[l-1]*base[r-l+1]; } void init(string s)//初始化哈希 {int n=s.size();s="0"+s;//讓其下標從1開始base[0]=1;for(int i=1;i<=n;i++){h[i]=h[i-1]*M+s[i];base[i]=base[i-1]*M;// base[i]=M^i} } ull merge(int l1, int r1, int l2, int r2) //求[l1,r1],[l2,r2]子串并的哈希值 {return query(l1, r1) * base[r2 - l2 + 1] + query(l2, r2); }

字符串哈希入門：
P3370 【模板】字符串哈希
841. 字符串哈希
103. 子串查找

二維哈希模板

typedef long long int ll; const int N=1010; ll h[N][N],base1[N],base2[N]; int a[N][N],n,m; void init()//構建 {base1[0]=base2[0]=1;for(int i=1;i<N;i++){base1[i]=base1[i-1]*131;base2[i]=base2[i-1]*233;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)h[i][j]=h[i][j-1]*131+a[i][j];//行哈希for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)h[i][j]=h[i-1][j]*233+h[i][j];//列哈希 } ll query(int x1,int y1,int x2,int y2)//查詢矩陣的哈希值 {return h[x2][y2]-h[x2][y1-1]*base1[y2-y1+1]-h[x1-1][y2]*base2[x2-x1+1]+h[x1-1][y1-1]*base1[y2-y1+1]*base2[x2-x1 + 1]; }

二維哈希習題：
Matrix
矩陣

好的文章推薦：
哈希入門
哈?；A例題
二維哈希

總結

以上是生活随笔為你收集整理的ACM入门之【哈希】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。