首页 > 代码库 > 哈希表之分离链接
哈希表之分离链接
哈希表即散列表，用于存储ｋｅｙ－ｖａｌｕｅ对，ｋｅｙ作用和数组下标相似，只是其ｋｅｙ是经过一定加工（ｈａｓｈｆｕｎｃｔｉｏｎ）之后得出的。其目的主要是加速查找，也可以认为以散列函数的时间消耗换取了对数组空间的紧缩。一般说来，设计一个合理的散列函数是关键——好的散列函数可以使得存储空间被充分利用，亦即减少冲突的发生。但无论如何，冲突都是存在的，多数情况下，我们需要检测并处理冲突。处理方法是多种多样的，可以沿着ｋｅｙ＋ｎ的方向继续查找空的位置，也可以另开一个哈希表采用不同的散列函数，也可以在当前位置保存一个链表。相对于安全性和编码而言，在当前位置使用链表更突出，但其效率相对低一些。这里，以一个ＮＯＩ题目为例，介绍分离链接法解决哈希表冲突：
1807:正方形查看 提交 统计 提问总时间限制: 8000ms 单个测试点时间限制: 4000ms 内存限制: 65536kB描述给出平面上一些点的坐标，统计由这些点可以组成多少个正方形。注意：正方形的边不一定平行于坐标轴。输入输入包括多组测试数据。每组的第一行是一个整数n (1 <= n <= 1000)，表示平面上点的数目，接下来n行，每行包括两个整数，分别给出一个点在平面上的x坐标和y坐标。输入保证：平面上点的位置是两两不同的，而且坐标的绝对值都不大于20000。最后一组输入数据中n = 0，这组数据表示输入的结束，不用进行处理。输出对每组输入数据，输出一行，表示这些点能够组成的正方形的数目。样例输入41 00 11 10 090 01 02 00 21 22 20 11 12 14-2 53 70 05 20样例输出161
这个题目要求我们查找正方形，方法也是多种多样的。但是效率较高的算法是这样的：取任意两点作为正方形对角线ＡＣ，则若另一条对角线的两个端点Ｂ、Ｄ也在给定数据中，则找到一个正方形。这样，问题就变为：遍历点集中每两点Ａ，Ｃ，求Ｂ，Ｄ坐标，在点集中查找Ｂ，Ｄ；若Ｂ、Ｄ均在点集中，则找到一个正方形。遍历两点的方法和冒泡排序一样，剩下的问题就是查找另外两点，如果可以用一个桶来标记点的存在就好了，但是题目数据很大，即使使用ＢＩＴＡＲＲＡＹ也难于达到要求，所以我们需要把点集散列存储。需要注意的是，每个正方形的两条对角线如果我们不做限制，则都可用作确定正方形，即得到的正方形个数为两倍。因为代码已经达到３００ｍｓ完成测试，所以此处没有进行限定对角线的角度：
#include<iostream>#include<cstring>using namespace std;const int htsize=(1<<20);struct point{ int x; int y; point *next; //用于分离链接}ps[1005];point* ht[htsize];int hsfunc(point p){ return ((p.x+1)*17 + p.y )&(htsize-1);}void writehash(point *p){ int hash=hsfunc(*p); if(ht[hash]==0){ ht[hash]=p; }else{ point *cp=ht[hash]; while(cp->next!=0){ cp=cp->next; } cp->next=p; }}bool readhash(point* p){ int hash=hsfunc(*p); if(0<=p->x && p->x<=80000 && 0<=p->y && p->y<=80000 && ht[hash]>0){ point *cp=ht[hash]; while(cp!=0){ if(cp->x==p->x&&cp->y==p->y){ return true; } cp=cp->next; } } return false;}int rectcnt(int pointcnt){ int i,j,rectcnt=0; point p1,p2; for(i=0;i<pointcnt;i++){ for(j=i+1;j<pointcnt;j++){ //做对角线看待，计算另外两点。此时一个正方形只有两条对角线被计算。 p1.x=(ps[i].x+ps[j].x+ps[j].y-ps[i].y)/2; p1.y=(ps[i].y+ps[j].y+ps[i].x-ps[j].x)/2; p2.x=(ps[i].x+ps[j].x-ps[j].y+ps[i].y)/2; p2.y=(ps[i].y+ps[j].y-ps[i].x+ps[j].x)/2; if(readhash(&p1)&&readhash(&p2)){ rectcnt++; } } } return rectcnt/2;}int main(){ int i,cnt; cin>>cnt; while(cnt!=0){ memset(ht,0,sizeof(ht)); for(i=0;i<cnt;i++){ cin>>ps[i].x>>ps[i].y; ps[i].x=(ps[i].x+20000)*2; //增加哈希表覆盖率，避免对角线计算时出现小数 ps[i].y=(ps[i].y+20000)*2; ps[i].next=0; writehash(&ps[i]); } cout<<rectcnt(cnt)<<endl; cin>>cnt; }}
代码中有几处小技巧：
１、ｍａｉｎ函数中对ｐ．ｘ，ｐ．ｙ进行处理，因为求对角线ＢＤ的时候需要／２，为了避免浮点数计算先＊２。
２、ｒｅａｄｈａｓｈ函数中限定了点在（０，０），（８００００，８００００）矩形范围内减少不必要的查找。
３、设定哈希表大小ｈａｓｈｓｉｚｅ和计算哈希值时的＆运算。避免求余运算符，直接用位运算截取低位。
哈希表之分离链接