【贴代码】Hash表

引入

Hash表是在Hash字符串的思想上，传入几个参数通过一个函数求得Hash值。
这样就可以把本来需要的大量空间压缩成小空间。
通常步骤如下：
1： 创建一个F函数，用来通过参数获得Hash值
2： 建立Hash数组，相当于vis数组。
3： 插入Hash值和询问某Hash值
但是，Hash值虽然对数组大小进行了压缩，但是这样就会存在Hash冲突。
也就是参数明明不相同，但Hash值却相同，这个时候我们就需要优化算法解决Hash冲突。
这里介绍一下拉链法：
我们可以以Hash值为下标，把Hash值相同的存在一个链表里。
链表中储存原参数，在询问时遍历链表中的参数。

这样要注意一点，F函数就要保证两点：
1： 返回值要>=0
2: 返回值要<=链表下标的最大值
所以F函数应该类似于：

int F(int a,int b,int c,int ...)
{
	return abs(运算)%H;
}

另外链表的下标要是一个较大质数，为了不能与Hash值约分。
链表可以用链式前向星实现。

例题

Squares

分析

暴力枚举正方形的四个顶点会超时，但因为是正方形，所以其实知道两个点就可以算出另外两个点，
分别是：（x1+(y2-y1) , y1-(x2-x1)) 和 (x2+(y2-y1) , y2-(x2-x1)).
然后用Hash表判断这两个点是否存在即可。
要注意的是，在遍历顶点时，会遍历4次（正方形四个顶点）。所以答案要/4。

代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define full(a,b) memset(a,b,sizeof a)
#define ll long long
#define ull unsigned ll
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
#define debug 1
#define N 1005
#define H 999979 //大质数 
int n,x[N],y[N],ans;
int head[H],nxt[H],ecnt;
struct node
{
	int x,y;
} to[H];//储存参数 
int F(int x,int y) //自定义函数 
{
	return abs(x*x+y*y)%H;
}
void add(int h,int u,int v) //增加一个结点 
{
	to[++ecnt]=node{u,v};
	nxt[ecnt]=head[h];
	head[h]=ecnt;
}
void insert(int x,int y)
{
	int h=F(x,y);//获取Hash值（即下标） 
	for(int i=head[h]; i!=-1; i=nxt[i])
		if(to[i].x==x&&to[i].y==y) return;//已经有，不需要再添加 
	add(h,x,y);
}
int query(int x,int y)
{
	int h=F(x,y);
	for(int i=head[h]; i!=-1; i=nxt[i])
		if(to[i].x==x&&to[i].y==y) return 1;//存在 
	return 0;
}
int main()
{
	if(debug==-1)
	{
		freopen("Squares.in","r",stdin);
		freopen("Squares.out","w",stdout);
	}
	while(~scanf("%d",&n)&&n)
	{
		ans=0;ecnt=0;
		full(head,-1);
		for(int i=1; i<=n; i++)
			x[i]=read(),y[i]=read();
		for(int i=1; i<=n; i++)
			insert(x[i],y[i]);//添加hash值 
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(i!=j)
				{
					int lenx=x[j]-x[i],leny=y[j]-y[i];
					if(query(x[i]+leny,y[i]-lenx)&&query(x[j]+leny,y[j]-lenx)) ++ans;//询问点是否存在 
				}
		printf("%d\n",ans/4);
	}
	return 0;
}