pat 1145:

Quadratic probing (with positive increments only) is used to solve the collisions.：平方探测法解决冲突

哈希表:H(key)求余数、二次平方探测法解决冲突、求平均查找长度AVL = 所有次数和/n

需要注意点：处理冲突统计查找次数时，如果查找到哈希表最后一个也失败了，那么次数要+1.

#include
    
     using namespace std;/*哈希表:H(key)求余数、二次平方探测法解决冲突、求平均查找长度AVL = All/n */ const int maxn = 1e5+5;int Tsize,n,m;int a[maxn];int b[maxn];int hashTable[maxn];bool isPrime(int x){    if(x < 2) return false;    for(int i=2;i<=sqrt(x);i++){        if(x%i == 0) return false;    }    return true;}int HashKey(int key){    return key%Tsize;}int main(){    memset(hashTable,-1,sizeof(hashTable));    cin>>Tsize>>n>>m;    while(isPrime(Tsize) == false) Tsize++;    for(int i=0;i
     
      >a[i];    for(int i=0;i
      
       >b[i];    //插入     for(int i=0;i
      
     
    

pat 1078 同上

数组存hash表、hash函数求余、平方探测法解决冲突，并且首先哈希表长度为素数。

#include
    
     using namespace std;int Tsize,n;const int maxn = 1e4+10;int a[maxn];int table[maxn];bool isPrime(int x){    if(x < 2) return false;    for(int i=2;i<=sqrt(x);i++){        if(x%i == 0) return false;    }    return true;}int getHash(int key){    return key%Tsize;}int main(){    cin>>Tsize>>n;    for(int i=1;i<=n;i++) cin>>a[i];    while(isPrime(Tsize) == false) Tsize++;    bool first = true;    for(int i=1;i<=n;i++){        bool search = false;        for(int j=0;j
    

另补充哈希冲突的处理方法 和 装填因子：