除留余数法设计哈希表 :
由该式子得到value在哈希表中的存储位置:index = value % p;这里为了尽量的减少冲突,而且让value在哈希表中尽可能的均匀分布,p的选择就至关重要了。而合理选择p的经验是:若散列表表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。
平方探测法:
冲突是不可避免的,本题中提到的解决冲突的平方探测法:
- 当index的位置已经没有被占用,则index就是hash值。如果已经别占用,则进行步骤2.
- 看ans = index+k*k(k从1开始)是不是被占用,如果没有被占用,则ans为hash值,否则就进行步骤3.
- 看ans = index-k*k(k从1开始)是不是别占用,如果没有被占用,则ans为hash值,否则就k++,进行步骤2.
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <queue> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 #include <cstring> 7 #include <map> 8 #define INF 0x3f3f3f3f 9 #define FRE() freopen("in.txt","r",stdin) 10 11 using namespace std; 12 typedef long long ll; 13 typedef pair<int,int> P; 14 const int maxn = 50010; 15 map<string,int> mp; 16 string str; 17 int vis[maxn]; 18 19 int Judge(int sum, int p){ 20 sum %= p; 21 if(mp.count(str)){//重复出现 22 return sum; 23 } 24 if(vis[sum] && mp[str] == 0){//发生冲突 25 int k = 1,tmp = sum; 26 while(vis[sum]){ 27 sum = (tmp+k*k)%p; 28 if(!vis[sum])break; 29 sum = (tmp-k*k+p)%p; 30 k++; 31 } 32 vis[sum] = 1; 33 mp[str] = sum; 34 return sum; 35 } 36 else if(!vis[sum] && mp[str] == 0){ 37 vis[sum] = 1; 38 mp[str] = sum; 39 return sum; 40 } 41 } 42 43 44 45 int main() { 46 //FRE(); 47 int n,p; 48 cin>>n>>p; 49 memset(vis,0,sizeof(vis)); 50 for(int i = 0; i<n; i++) { 51 cin>>str; 52 int len = str.size(),sum = 0; 53 if(len>3) { 54 for(int j = len-3; str[j]; j++) { 55 int temp = str[j]-'A'; 56 sum = sum*32 + temp; 57 } 58 } else { 59 for(int j = 0; str[j]; j++) { 60 int temp = str[j] - 'A'; 61 sum = sum*32 + temp; 62 } 63 } 64 int tt = Judge(sum, p); 65 if(i == 0) 66 cout<<tt; 67 else 68 cout<<" "<<tt; 69 } 70 cout<<endl; 71 return 0; 72 } 73 /* 74 输入1: 75 4 11 76 HELLO ANNK ZOE LOLI 77 输出1: 78 3 10 4 0 79 输入2: 80 6 11 81 LLO ANNA NNK ZOJ INNK AAA 82 输出2: 83 3 0 10 9 6 1 84 */