要求

比较线性探测、平方探测和立方探测产生的冲突数量

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cmath>
#include<vector>
#include<ctime>
using namespace std;

const int SIZE = 9001;//大于9000的最小素数
const int MAX = 4500;//放入的数据数量
int lCollision = 0;
int qCollision = 0;
int cCollision = 0;

int main()
{
	vector<int>linear(SIZE, -1);
	vector<int>quadratic(SIZE, -1);
	vector<int>cubic(SIZE, -1);//-1表示没有数据，1表示有数据

	
	//线性探测
	srand(time(NULL));
	for (int i = 0; i < MAX; i++)
	{
		int hashCode = rand() % SIZE;
		int offset = 0;//插入单个数据的冲突次数
		int temp = hashCode;
		while (linear[temp] == 1)
		{
			temp = hashCode;
			lCollision++;
			offset++;
			temp += offset;
			temp %= SIZE;
			if (linear[temp] == -1)hashCode = temp;
		}
		linear[hashCode] = 1;
	}

	//平方探测
		srand(time(NULL));
	for (int i = 0; i < MAX; i++)
	{
		int hashCode = rand() % SIZE;
		int offset = 0;
		int temp = hashCode;
		while (quadratic[temp] == 1)
		{
			temp = hashCode;
			qCollision++;
			offset++;
			temp += offset * offset;
			temp %= SIZE;
			if (quadratic[temp] == -1)hashCode = temp;
		}
		quadratic[hashCode] = 1;
	}
	//立方探测(f(i)=i*i*i)
		srand(time(NULL));
	for (int i = 0; i < MAX; i++)
	{
		int hashCode = rand() % SIZE;
		int offset = 0;
		int temp = hashCode;
		while (cubic[temp] == 1)
		{
			temp = hashCode;
			cCollision++;
			offset++;
			temp +=offset*offset*offset;
			temp%= SIZE;
			if (cubic[temp] == -1)hashCode = temp;
		}
		cubic[hashCode] = 1;
	}
	
	//输出结果
	cout << "线性探测的冲突次数：" << lCollision << endl;
	cout << "平方探测的冲突次数：" << qCollision << endl;
	cout << "立方探测的冲突次数：" << cCollision << endl;

	return 0;
}

运行结果