拉链哈希表

抄的 OI-wiki。

hash_table?

首先要有哈希函数，将一个特定的复杂结构变成一个整数， 当然， 哈希函数不应有随机性。

然后对于哈希表的值域进行拉链， 避免哈希冲突。

如果哈希表的值域大小为 \(M\)， 表内插入了 \(N\) 个元素， 那么单次查询的期望复杂度是 \(O(\frac NM)\)（看上去不太靠谱啊）。

比如这题 [USACO12DEC]Running Away From the Barn G 就可以用 hash_table

糊了下代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 100003;

int n,m,a[30];
int tot, hd[N], nt[N], ky[N][30], p[N];
bool eq(int *x,int *y) {
	for(int i=0;i<m;++i) if(x[i]!=y[i]) return false;
	return true;
}
int has() {
	int res = 0;
	for(int i=0;i<m;++i) res = (res*233ll+a[i])%N;
	return (res%N+N)%N;
}
void ad(int x,int i) {
	nt[++tot]=hd[x], hd[x]=tot;
	memcpy(ky[tot],a,sizeof a);
	p[tot] = i;
}
int get(int pp) {
	int x = has();
	for(int i=hd[x]; i; i=nt[i])
		if(eq(ky[i],a)) return p[i];
	return ad(x,pp), -1;
}

int main()
{
	scanf("%d%d",&n,&m);
	ad(0,0);
	int ans = 0;
	for(int i=1;i<=n;++i) {
		int x; scanf("%d",&x); for(int j=0;j<m;++j) a[j]+=((x>>j)&1);
		if(x&1) for(int j=0;j<m;++j) --a[j];
			int pr = get(i);
		if(pr!=-1) ans = max(ans,i-pr);
	}
	cout << ans;
	return 0;
}

拉链哈希表

原文：https://www.cnblogs.com/tztqwq/p/14121764.html