算法總結篇---哈希和哈希表

/kk

哈希和哈希表
- 單哈希
- 多哈希
- 哈希表
- 多哈希哈希表
- 關于哈希函數
- 字元串哈希
- 例題
  - Oulipo
  - 圖書管理
  - Power Strings
  - [BalticOI 2014 Day1] Three Friends
  - P3538 [POI2012]OKR-A Horrible Poem

什麼是哈希啊?

哈希是一種用來統計複雜資料的不完美算法，或者說思想，構造一個哈希函數将原始資料映射成便于統計的資訊上，在映射過程中會損失部分資訊。類似于離散化，僅保留大小關系。

舉個栗子：

維護一個資料結構，支援插入一個數，查詢一個的數在這個資料結構中的個數，數的大小 \(\le 2^{63} - 1\)

把插入的一個數對一個不是很大的數取模，令新數代替原數。

如果兩個數的餘數相等，則認為它們兩個相等

開一個 \(cnt\) 數組統計個數

同時對多個模數取模，判重時判取模後的所有數是否全部相等，

實作時可以定義一個結構體，用 \(set/map\) 維護，或寫哈希表。

正确性大幅增加，但仍不是完全正确。

一般寫雙哈希就夠了，卡不掉。

考慮單哈希。

不把餘數相等的一些數直接看做相等，開個連結清單把它們鍊起來。

判重時找到查詢的數的餘數對應的連結清單，周遊所有元素判重。

可以用鄰接表或 vector 實作。

随機資料下連結清單最大長度（每次判重的複雜度）期望 O(\frac{n}{mod})。

犧牲了時間，保證了正确性

可以用多哈希使數的分布更加均勻。

一般做法是對哈希得到的多個餘數再進行哈希。

對應的哈希函數相等是兩元素相等的必要條件

可以随便構造

構造哈希函數的方式多種多樣，模一個數，乘一個數，加一個數，甚至更複雜的關系

隻要正确性高就行，或者函數符合您的品味

用于判重字元串

将一串字元映射成一個整數再進行判斷

由于字元串是具有前後關系的，一般按下述方法構造：

選取兩個合适的互質常數 \(b\) 和 \(h (b < h)\)，假設有一個字元串 \(C = c_1c_2···c_m\)，那麼我們定義哈希函數：

\[H(C) = (c_1b^{m - 1} + c_2b^{m - 2} + ···+c_mb^{0}) \mod h

考慮遞推實作，設 \(H(C, k)\) 為前 \(k\) 個字元構成的字元串的哈希值，則：

\[H(C, k + 1) = H(C, k) \times b + c_{k + 1}

通常，題目要求的是判斷主串的一段字元與另一個比對串是否比對，即判斷字元串 \(C = c_1c_2···c_m\) 從位置 \(k + 1\) 開始的長度為 \(n\) 的子串 \(C^{'} = c_{k + 1}c_{k + 2}···c_{k + n}\) 的哈希值與另一比對串 \(S = s_1s_2···s_n\) 的哈希值是否相等，則：

\[H(C_{'}) = H(C, k + n) - H(C, k) \times b^{n}

隻要預求得 \(b^{n}\) ，就能 \(O(1)\) 判斷了

總時間複雜度 \(O(n + m)\)

闆子題

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
#define int long long

using namespace std;
const int MAXN = 1e6+10;
const int INF = 1;
const int mod = 1e9+9;
const int b = 1e9+7;

char A[MAXN], B[MAXN];
int H[MAXN], h[MAXN], pow, cnt = 0, sum = 0;

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

int quickpow(int x, int p, int mod){
	int res = 1;
	while(p){
		if(p & 1) res = res * x % mod;
		x = x * x % mod;
		p >>= 1;
	}
	return res;
}

#undef int 

int main()
{
#define int long long
//	init();
	cin>>A + 1;
	cin>>B + 1;
	int lenA = strlen(A + 1), lenB = strlen(B + 1);
	pow = quickpow(b, lenB, mod);
	for(int i = 1; i <= lenA; ++i){ H[i] = (H[i - 1] * b % mod + A[i]) % mod; }
	for(int i = 1; i <= lenB; ++i){ sum = (sum * b % mod + B[i]) % mod; }
	cnt = 0;
	for(int i = 0; i + lenB <= lenA; ++i){
//		cout<<(H[i + lenB] - H[i] * pow % mod + mod) % mod<<endl;
		if((H[i + lenB] - H[i] * pow % mod + mod) % mod == sum){
//			orz;
			cnt++;
		}
	}
	printf("%d", cnt);
	return 0;
}

發現圖書隻有加入沒有拿出，用字元串哈希轉換後和上面的例題類似

用

bool

數組來表示其是否加入，\(O(1)\) 查詢

考慮用雙哈希優化，會使重複的可能性降到很低

我這裡隻用了單哈希，開到一億多才卡過去

成為所有送出記錄中用時最長空間最長的一份代碼

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 3e4+4;
const int INF = 1;
const int mod = 101451419;
const int b = 1e9 + 7;

LL n, stc[MAXN], sc = 0;
bool vis[101452419];
char nam[210], opt[10];

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

int main()
{
	n = read();
	for(int i = 1, len; i <= n; ++i){
		LL sum = 0;
		cin>>opt;
		gets(nam + 1);
		len = strlen(nam + 1);
		for(int j = 1; j <= len; ++j){ sum = (sum * b % mod + nam[j]) % mod; }
		if(opt[0] == 'a') vis[sum] = 1;
		if(opt[0] == 'f') 
			if(vis[sum]) printf("yes\n");
			else printf("no\n");
	}
	return 0;
}

比較好出思路，枚舉重複的字元串的長度，因為長度必須是總長度的因子，是以 \(O(len)\) 枚舉即可，然後掃一遍看看是否符合條件，從小到大最先遇到的一定是答案

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e6+6;
const int INF = 1;
const int mod = 1e9+9;
const int b = 1e7+7;

char s[MAXN];
LL pow[MAXN], H[MAXN], sum;
int len;

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

void init(){
	pow[0] = 1;
	for(int i = 1; i <= 1e6; ++i){ pow[i] = pow[i - 1] * b % mod; }
}

bool check(int mid){
	sum = H[mid];
	for(int i = 0; i <= len - 1; i += mid){
		if((H[i + mid] - H[i] * pow[mid] % mod + mod) % mod != sum) return 0;
	}
	return 1;
}

int main()
{
	init();
	while((cin>>(s + 1)) && s[1] != '.'){
		len = strlen(s + 1);
		for(int i = 1; i <= len; ++i){
			H[i] = (H[i - 1] * b % mod + s[i]) % mod;
		}
		for(int i = 1; i <= len; ++i){
			if(len % i) continue;
			if(check(i)) {
				printf("%d\n", len / i);
				break;
			}
		}
	}
	return 0;
}

相關 \(Solution\) 請跳轉我的這篇題解

來自兩篇題解的思路，可以結合着了解一下，另外loj上這題卡我模數和進制數

1、循環節一定是長度的約數
2、如果n是一個循環節，那麼k*n也必定是一個循環節（關鍵所在）
3、n是[l,r]這一段的循環節  的充要條件是  [l,r-n]和[l+n,r]相同（利用這個性質我們在判斷是否為循環節是可以做到O(1)）  
是以我們可以在求出這個區間的長度之後，判斷它的每個約數是否是循環節（應用性質3），并且因為性質1，它的約數是循環節，原串一定也是。

循環節的長度的循環次數都一定是總長的約數
我的做法是把總長除掉循環次數
先把len分解質因數
（線性篩質數，并記錄下每個數的最小質因子加速分解，這已經是正常操作了）
因為最小循環節的倍數也是循環節
是以從len開始試除每個質因子并判斷（你可以了解為len的因子分為循環節的因子和循環次數的因子，要把循環次數的因子除掉）

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define LLL unsigned long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 5e5+10;
const int INF = 1;
const int mod = 1e9+7;
const int b = 7;

LL n, m;
char s[MAXN];
LLL Pow[MAXN], H[MAXN], sum;
LL prim[MAXN], sc = 0;
bool vis[MAXN], flag;

LL read(){
	LL s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
	return f ? -s : s;
}

void init(){
	for(LL i = 2; i <= n; ++i){
		if(vis[i]) continue;
		for(LL j = 1; i * j <= n; ++j){
			LL t = i * j;
			if(vis[t]) continue;
			vis[t] = true;
			prim[t] = i;
		}
	}
}

int main()
{
	n = read();
	init();
	cin >> (s + 1);
	Pow[0] = 1;
	for(LL i = 1; i <= n; ++i){ Pow[i] = Pow[i - 1] * b, H[i] = H[i - 1] * b + s[i]; }
	m = read();
	for(LL i = 1, l, r, len, ans; i <= m; ++i){
		l = read(), r = read();
		ans = len = r - l + 1;
		while(len > 1){
			LL k = ans / prim[len];
			len /= prim[len];
			if(H[r - k] - H[l - 1] * Pow[r - k - l + 1] == H[r] - H[l - 1 + k] * Pow[r - k - l + 1]){
				ans = k;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

算法總結篇---哈希和哈希表

繼續閱讀

1.1哈希表

非線性最小二乘求解方法總結

劍指 Offer 48. 最長不含重複字元的子字元串（中等）思路：代碼：分解：

poj2503 Babelfish

LeetCode算法題：1.兩數之和

（LeetCode）Java 求解兩數之和

【樹狀數組】樹狀數組入門(簡單的原理講解) 樹狀數組入門(簡單的原理講解)

資料結構與算法第三天線性表（一）

LintCode Consistent Hashing（一緻性雜湊演算法）

雜湊演算法在密碼加密存儲中的應用

POJ-3349 Snowflake Snow Snowflakes

劍指offer032---有效的變位詞(簡單難度)題目概述(簡單難度)思路與代碼

LeetCode187. 重複的DNA序列 --哈希表+排序

LeetCode 187. Repeated DNA Sequences（重複DNA序列）

LeetCode學習筆記——單詞拼寫

LeetCode刷題實戰350：兩個數組的交集 II