简介
本文主要介绍哈希算法，哈希表的创建与检索，如何解决哈希冲突。
代码
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
83
84
85
86
87
88
89
90
91
92
93
| #include <iostream>
using namespace std;
#define NULLKEY -1
#define DELKEY -2
#define N 100
#define M 110
//定义哈希表结构
typedef struct _Node{
int key;
int num;
_Node()
{
num = 0;
key = NULLKEY;
}
} Node;
//创建哈希表，先将数据对M求余得到一个哈希下标，如果有冲突，则使用开放定址法，将下标移到下一个哈希单元。
void createHash(unsigned int *data, Node *hash)
{
for(int i = 0; i < N; i++)
{
int k = data[i] % M;
int num = 0;
while(true)
{
if(hash[k].key == NULLKEY || hash[k].key == DELKEY)
{
hash[k].key = data[i];
hash[k].num = num;
cout << "hash[" << k << "] = " << data[i] <<endl;
break;
}
else
{
cout << "hash cash, data = " << data[i] << ", key = " << k << endl;
k = (k + 1) % M;
num++;
}
}
}
}
//查找数据，如果检索到的数据跟源数据不符，说明之前这里存在哈希冲突，坐标往下加一，继续找。
int searchHash(unsigned int data, Node *hash)
{
int p = data % M;
while(hash[p].key != NULLKEY && hash[p].key != DELKEY && hash[p].key != data)
{
p = (p + 1) % M;
}
if(hash[p].key == data)
{
return p;
}
else
{
return -1;
}
}
//测试函数
int main()
{
Node hash[M];
unsigned int data[N];
for(int i = 0; i < N; i++)
{
data[i] = rand() % (M * N);
//data[i] = rand() % M;
//data[i] = i;
}
createHash(data, hash);
for(int i = 0; i < N; i++)
{
//unsigned int temp = data[rand() % N];
unsigned int temp = data[i];
int p = searchHash(temp, hash);
if(p != -1)
{
cout << "find data: " << temp << " in hash table: " << p << ", hash[" << p << "] = " << hash[p].key << endl;
}
else
{
cout << "can't find "<< temp << " in hash table" <<endl;
}
}
}
|
测试结果
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
| lin@lin-K40IE:~/Dropbox/recruit/C_C++基础知识/hash$ g++ hash_table.cpp -o hash_table -std=c++11
lin@lin-K40IE:~/Dropbox/recruit/C_C++基础知识/hash$ ./hash_table
hash[83] = 3383
hash[76] = 7886
hash[17] = 1777
hash[35] = 915
hash[23] = 793
hash[15] = 1335
hash[66] = 1386
hash[72] = 2492
hash[69] = 8649
hash[1] = 2421
hash[52] = 2362
hash[7] = 9027
hash[60] = 3690
hash cash, data = 1059, key = 69
hash[70] = 1059
hash[73] = 8763
hash[26] = 9926
hash[20] = 3540
hash cash, data = 9426, key = 76
hash[77] = 9426
hash[2] = 5172
hash cash, data = 10736, key = 66
...
...
hash cash, data = 2539, key = 39
hash[40] = 2539
find data: 3383 in hash table: 83, hash[83] = 3383
find data: 7886 in hash table: 76, hash[76] = 7886
find data: 1777 in hash table: 17, hash[17] = 1777
find data: 915 in hash table: 35, hash[35] = 915
find data: 793 in hash table: 23, hash[23] = 793
find data: 1335 in hash table: 15, hash[15] = 1335
|
请参考：
查找算法–哈希表查找
打造最快的Hash表
Hash表（C++实现）
The very simple hash table example