开放定址法解决散列冲突时主要有线性探测法，平方探测法和双散列法，以下代码通过插入大量随机数，来统计几种探测法产生冲突的次数。
#includeusing namespace std;#define MinTablesize 10#define Num 3000typedef unsigned int Index;typedef Index Position;struct Hashtal;typedef struct Hashtal *Hashtable; int num_quadratic_probing = 0;int num_liner_probing = 0;int num_double_probing = 0;int array_rand[Num]; //大小为1000的随机数组enum KindOfEntry //枚举类型，只能是其中的一个值{ Legitimate,Empty,Delete}; struct HashEntry{ int Element; enum KindOfEntry Info;}; typedef struct HashEntry Cell; struct Hashtal{ int TableSize; int Insert_num; //记录插入的个数 Cell *Thecells;}; Hashtable Rehash (Hashtable H,int ty);Hashtable Insert(int Key,Hashtable H,int ty);int Hash (int x,Hashtable H) //散列函数{ return x % H->TableSize;} int NextPrime (int Key) // 寻找Key后的第一个素数{ if(Key == 1 || Key == 2) return Key; bool flag = 0; int pre_Key; while(!flag) { pre_Key = Key; for(int i = 2; i != Key; ++i) { if(Key % i == 0) //Key不是素数 { Key++; break; } } if(pre_Key == Key) //说明Key没有改变 flag = 1; else flag = 0; } return Key;}Hashtable InitTable(int Tablesize) //创建一个散列表{ Hashtable H; if(Tablesize < MinTablesize) { cout << "Table is too small" << endl; return NULL; } //创建散列表 H = (Hashtable)malloc(sizeof(struct Hashtal)); if(H == NULL) cout << "out of space " << endl; H->TableSize = NextPrime(Tablesize); //大小为H->TableSize后的第一个素数 H->Thecells = (Cell*)malloc(sizeof(Cell) * H->TableSize ); if(H->Thecells == NULL) cout << "out of space " << endl; H->Insert_num = 0; for (int i = 0; i != H->TableSize; ++i) H->Thecells[i].Info = Empty; //每个元素都标记为空 return H;}Position Find_linear_probing (int Key , Hashtable H) //使用线性探测散列{ Position CurrPos; int CollNum; CollNum = 0; CurrPos = Hash(Key,H); while(H->Thecells[CurrPos].Info != Empty && H->Thecells[CurrPos].Element != Key) //找不到时返回一个空单元 { CurrPos = (CurrPos + (++CollNum)) % H->TableSize; //使用线性探测散列法 ++num_liner_probing; //冲突次数加1 if((int)CurrPos >= H->TableSize ) CurrPos -= H->TableSize; } return CurrPos;}Position Find_quadratic_probing (int Key , Hashtable H) //使用平方探测散列{ Position CurrPos; int CollNum; CollNum = 0; CurrPos = Hash(Key,H); while(H->Thecells[CurrPos].Info != Empty && H->Thecells[CurrPos].Element != Key) //找不到时返回一个空单元 { ++CollNum; CurrPos = (CurrPos + CollNum * CollNum) % H->TableSize; //使用平方探测散列法 ++num_quadratic_probing; //冲突次数加1 if((int)CurrPos >= H->TableSize ) CurrPos -= H->TableSize; } return CurrPos;}Position Find_double (int Key , Hashtable H) //使用双散列{ Position CurrPos; int CollNum; CollNum = 0; CurrPos = Hash(Key,H); while(H->Thecells[CurrPos].Info != Empty && H->Thecells[CurrPos].Element != Key) //找不到时返回一个空单元 { CurrPos = (CurrPos + (++CollNum) * (7 - (Key % 7 ))) % H->TableSize; //使用双散列探测 ++num_double_probing; //冲突次数加1 if((int)CurrPos >= H->TableSize ) CurrPos -= H->TableSize; } return CurrPos;}Hashtable Insert(int Key,Hashtable H,int ty){ if(((double)H->Insert_num /H->TableSize) > 0.5) //如果装填因子大于0.5，就再散列， H = Rehash(H,ty); Position Pos; switch (ty) { case 1: Pos = Find_quadratic_probing(Key,H); break; case 2: Pos = Find_linear_probing(Key,H); break; case 3: Pos = Find_double(Key,H); break; default: cout << "Insert type error" << endl; } if(H->Thecells[Pos].Info != Legitimate) // { H->Thecells[Pos].Element = Key; H->Thecells[Pos].Info = Legitimate; H->Insert_num++; //插入的元素个数加1 } return H;} Hashtable Rehash (Hashtable H,int ty) //再散列，把表的大小放大到原来的2倍，再把原来的元素插入到新散列表中{ int Oldsize; Cell *Oldcells; Oldcells = H->Thecells; Oldsize = H->TableSize; H = InitTable(2 * Oldsize); for (int i = 0; i != Oldsize; ++i) { if(Oldcells[i].Info == Legitimate) Insert(Oldcells[i].Element, H,ty); } free(Oldcells); return H;}void destroyTable(Hashtable H) { free(H->Thecells ); free(H); } int main (){ for (int i = 0; i != Num; ++i) { array_rand[i] = rand(); //产生随机数 } Hashtable H1 = InitTable(200); //200大小的散列表 for(int i = 0; i != Num; ++i) { H1 = Insert(array_rand[i],H1,1); } cout << num_quadratic_probing << endl; destroyTable(H1); Hashtable H2 = InitTable(200); //200大小的散列表 for(int i = 0; i != Num; ++i) { H2 = Insert(array_rand[i],H2,2); } cout << num_liner_probing << endl; destroyTable(H2); Hashtable H3 = InitTable(200); //200大小的散列表 for(int i = 0; i != Num; ++i) { H3 = Insert(array_rand[i],H3,3); } cout << num_double_probing << endl; destroyTable(H3); return 0;}
通过改变随机数组的大小，可以多次观察结果，发现每次都是双散列产生的冲突次数最少，但是也少不了多少。
夜深了，，，
好像是陷入死循环，希望后面的代码有个break。
