hash表又叫散列表，是一种用来存放数据的数据结构。用于快速查询

hash表就是一种数组，输入关键字，通过hash函数得到，对应数据的下标。（hash值就是下标）

hash函数根据关键字设计，主要原理：依据数组的大小求模运算

数组大小一般设计为质数，以便均匀散布。

解决hash冲突：关键在于找空位置

1. 链表：结构体内加入next指针。当取模结果相同，数据不同时（即哈希冲突），将数据存放于next里面。
2. 开发地址：1.线性探测法，当发生冲突时，往后面一个一个的找空位置+1+1。                                           2.平方探测法，发生冲突，往i的平方找，+i^2 ，相比线性减少了数据扎堆                               3.双hash，第二个hash的mod要取比数组大小要小的质数，hash2（key）  =mod-（key%mod），hash的结果不会等于0。往后移hash2。

hash表快满了，进行再hash，建一个新表，尺寸为2倍以上，并将数据迁移。

缺点：1.冲突   2.表越满，性能越差

---

P1102 A-B 数对 https://www.luogu.com.cn/problem/P1102

思路：建立hash表 ，存放数据还有它出现的次数，通过链表解决冲突。从第一个开始遍历，hash得出a[i]+c在表中的位置，得到出现次数。

代码实现

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull mod=200003;
ull a[200000+5];
ull hashh(ull num)
{return num%mod;
}
struct arr{ull num=0;ull time=0;arr* next;
}htable[200000+5];int main()
{int n;ull c;scanf("%d%lld",&n,&c);for(int i=0;i<n;i++){scanf("%lld",&a[i]);arr* p=htable+hashh(a[i]);//找到这个hash值对应的地址while(p->num!=a[i]&&p->time>0)//如果这个位置已经被占了即次数大于01也不等于a[i]{if(p->next==NULL) p->next=(arr*)malloc(sizeof(arr));p=p->next;p->next=NULL;}p->num=a[i];p->time++;}ull ans=0;ull t;for(int i=0;i<n;i++){t=c+a[i];//接下来看t出现的次数arr* p=htable+hashh(t);while(p->num!=t&&p->next!=NULL){p=p->next;			}if(p->num==t){ans+=p->time;}}printf("%lld",ans);return 0;
}

 本应通过链表解决冲突，但依据测试结果应该是没有完全解决，这里我不明白，或许是我链表写错了

然后就把数组开大一点，就过了

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull mod=1000003;
ull a[1000000+5];
ull hashh(ull num)
{return num%mod;
}
struct arr{ull num=0;ull time=0;arr* next;
}htable[1000000+5];int main()
{int n;ull c;scanf("%d%lld",&n,&c);for(int i=0;i<n;i++){scanf("%lld",&a[i]);arr* p=htable+hashh(a[i]);//找到这个hash值对应的地址while(p->num!=a[i]&&p->time>0)//如果这个位置已经被占了即次数大于01也不等于a[i]{if(p->next==NULL) p->next=(arr*)malloc(sizeof(arr));p=p->next;p->next=NULL;}p->num=a[i];p->time++;}ull ans=0;ull t;for(int i=0;i<n;i++){t=c+a[i];//接下来看t出现的次数arr* p=htable+hashh(t);while(p->num!=t&&p->next!=NULL){p=p->next;			}if(p->num==t){ans+=p->time;}}printf("%lld",ans);return 0;
}

---

P2580 于是他错误的点名开始了https://www.luogu.com.cn/problem/P2580

思路：和上面那题一样，建表。然后依据输入查表

代码实现

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
int base=131;
int mod=1000007;
int hashh(char* str)
{int len=strlen(str);int ans=0;for(int i=0;i<len;i++){ans=(ans*base+(int)str[i])%mod;}return ans;
}struct arr{char str[50]={'\0'};int time=0;arr* next;
}htable[1000006];
int main()
{int n;scanf("%d",&n);getchar();char str[55];for(int i=0;i<n;i++){scanf("%s",str);arr* p=htable+hashh(str);while(strcmp(p->str,str)!=0&&p->str[0]!='\0'){if(p->next==NULL) p->next=(arr*)malloc(sizeof(arr));p=p->next;p->next=NULL;}strcpy(p->str,str);}int m;scanf("%d",&m);getchar();for(int i=0;i<m;i++){scanf("%s",str);arr* p=htable+hashh(str);while(strcmp(p->str,str)!=0&&p->next!=NULL){p=p->next;}	if(strcmp(p->str,str)==0){if((p->time)++==0) printf("OK\n");else printf("REPEAT\n");}else printf("WRONG\n");}return 0;
}

---

二次编辑

上面链表的问题，我已经找到

就是在遍历链表的时候，遍历一个会将下一个地址赋为NULL，导致链断了。两道题目都有这个问题，这里就只放第一个的代码了

订正

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull mod=200003;
ull a[200000+5];
ull hashh(ull num)
{return num%mod;
}
struct arr{ull num=0;ull time=0;arr* next;
}htable[200000+5];int main()
{int n;ull c;scanf("%d%lld",&n,&c);for(int i=0;i<n;i++){scanf("%lld",&a[i]);arr* p=htable+hashh(a[i]);//找到这个hash值对应的地址while(p->num!=a[i]&&p->time>0)//如果这个位置已经被占了即次数大于01也不等于a[i]{if(p->next==NULL) p->next=(arr*)malloc(sizeof(arr));p=p->next;}p->next=NULL;p->num=a[i];p->time++;}ull ans=0;ull t;for(int i=0;i<n;i++){t=c+a[i];//接下来看t出现的次数arr* p=htable+hashh(t);while(p->num!=t&&p->next!=NULL){p=p->next;			}if(p->num==t){ans+=p->time;}}printf("%lld",ans);return 0;
}