哈希表，哈希算法（C语言）
哈希表
哈希表，又称散列表，常用于在海量数据中查找数据
哈希表中元素是由哈希函数确定的。将数据元素的关键字key作为自变量，通过一定的函数关系H(称为哈希函数)，计算出的值，即为该元素的存储地址。其优点是：运算速度快；缺点是：基于数组、难于扩展，不可遍历。
在建立一个哈希表之前需要解决两个主要问题:
- 构造均匀的哈希函数 使H(key)均匀分布在哈希表中，以提高地址计算的速度。 构造哈希函数的方法：直接定址法，数字分析法，平法折中法，折叠法，除留余数法，随机数法等。
- 处理冲突 冲突是指在哈希表中，不同的关键字值对应到同一个存储位置的现象。即存在K1≠K2，但H(K1)=H(K2)。 再均匀的哈希函数都只能可减少冲突，但不可能避免冲突。 发生冲突后，必须解决，即必须寻找下一个可用地址。 解决冲突的方法:开放地址法（包括线性探测，二次探测，随机探测），再哈希法，链地址法，建立公共溢出区等。
C语言实现
哈希表的数据结构
1
2
3
4
5
6typedef struct HashNode_Struct HashNode;
struct HashNode_Struct {
char* sKey;//键值指针
int nValue; //键值
HashNode* pNext; //指向下一个哈希结构
};
定义最大哈希长度及哈希数组
1
2
3#define HASH_TABLE_MAX_SIZE 10000
HashNode* hashTable[HASH_TABLE_MAX_SIZE]; //哈希数组
int hash_table_size; //当前哈希长度
哈希表初始化函数
1
2
3
4
5
6
7
8void hash_table_init()
{
hash_table_size = 0;
memset(hashTable, 0 , sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);
//memset(void *s,int c,size_t n);
//将s中后n个字节换成c所代表的内容
//该函数是对较大结构体或数组进行清零操作的一种最快的方法
}
去符号化函数
1
2
3
4
5
6
7
8
9
10
11unsigned int hash_table_hash_str(const char* skey)
{ //无符号unsigned能保存2倍与有符号类型的正整型数据
const signed char *p = (const signed char*)skey; //常量
unsigned int h = *p;
if(h)
{
for(p += 1; *p != '\0'; ++p)
h = (h << 5) - h + *p;
}
return h;
}
插入函数
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
33void hash_table_insert(const char* skey, int nvalue)
{
if(hash_table_size >= HASH_TABLE_MAX_SIZE) //如果定义的哈希表长度大于等于最大长度
{
printf("内存溢出!\n");
return;
}
unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;
//用于解决冲突，pos为哈希函数
HashNode* pHead = hashTable[pos];
while(pHead)
{
if(strcmp(pHead->sKey, skey) == 0)
{
printf("%s发生冲突!\n", skey);
return ;
}
pHead = pHead->pNext;
}
//动态建立结点，初始化，分配内存空间
HashNode* pNewNode = (HashNode*)malloc(sizeof(HashNode));
memset(pNewNode, 0, sizeof(HashNode));
pNewNode->sKey = (char*)malloc(sizeof(char) * (strlen(skey) + 1));
strcpy(pNewNode->sKey, skey);
pNewNode->nValue = nvalue;
//指针后移
pNewNode->pNext = hashTable[pos];
hashTable[pos] = pNewNode;
//表长增加
hash_table_size++;
}
删除函数
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
33void hash_table_remove(const char* skey)
{
unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;
if(hashTable[pos])
{
HashNode* pHead = hashTable[pos];
HashNode* pLast = NULL;
HashNode* pRemove = NULL;
while(pHead)
{
if(strcmp(skey, pHead->sKey) == 0)
{ //若str1==str2，则返回零;
//若str1>str2，则返回正数;
//若str1<str2，则返回负数。
pRemove = pHead;//若相等，用pRemove记录
break;
}
pLast = pHead; //若不相等，不断后移
pHead = pHead->pNext;
}
if(pRemove)
{
if(pLast)
pLast->pNext = pRemove->pNext;//实现删除1
else
hashTable[pos] = NULL;//实现删除2
free(pRemove->sKey);
free(pRemove);
}
}
}
查找函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17HashNode* hash_table_lookup(const char* skey)
{
unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;
if(hashTable[pos])
{
HashNode* pHead = hashTable[pos];
while(pHead)
{
if(strcmp(skey, pHead->sKey) == 0)
return pHead;//查找成功
pHead = pHead->pNext;
}
}
return NULL;
}
打印哈希表函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void hash_table_print()
{
int i;
for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)
if(hashTable[i])//表不空
{
HashNode* pHead = hashTable[i];
printf("%d=>", i);
while(pHead)
{
printf("%s:%d ", pHead->sKey, pHead->nValue);
pHead = pHead->pNext;
}
printf("\n");
}
}
释放内存函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22void hash_table_release()
{
int i;
for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)
{
if(hashTable[i])
{
HashNode* pHead = hashTable[i];
while(pHead)
{
HashNode* pTemp = pHead;
pHead = pHead->pNext;
if(pTemp)
{
free(pTemp->sKey);
free(pTemp);
}
//逐个释放
}
}
}
}
随机生成函数
1
2
3
4
5
6
7
8
9
10#define MAX_STR_LEN 20
#define MIN_STR_LEN 10
void rand_str(char r[])
{
int i;
int len = MIN_STR_LEN + rand() % (MAX_STR_LEN - MIN_STR_LEN);
for(i = 0; i < len - 1; ++i)
r[i] = 'a' + rand() % ( 'z' - 'a');
r[len - 1] = '\0';
}
具体代码如下：
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define HASH_TABLE_MAX_SIZE 10000
typedef struct HashNode_Struct HashNode;
struct HashNode_Struct {
char* sKey;
int nValue;
HashNode* pNext;
}; //哈希表数据结构
HashNode* hashTable[HASH_TABLE_MAX_SIZE];
int hash_table_size; //哈希表中键值对的数量
//初始化哈希表
void hash_table_init()
{
hash_table_size = 0;
memset(hashTable, 0, sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);
//memset(void *s,int c,size_t n);
//将s中后n个字节换成c所代表的内容
//该函数是对较大结构体或数组进行清零操作的一种最快的方法
}
//去符号化哈希表
unsigned int hash_table_hash_str(const char* skey)
{ //无符号unsigned能保存2倍与有符号类型的正整型数据
const signed char *p = (const signed char*)skey; //常量
unsigned int h = *p;
if(h)
{
for(p += 1; *p != '\0'; ++p)
h = (h << 5) - h + *p;
}
return h;
}
//插入
void hash_table_insert(const char* skey, int nvalue)
{
if(hash_table_size >= HASH_TABLE_MAX_SIZE) //如果定义的哈希表长度大于等于最大长度
{
printf("内存溢出!\n");
return;
}
unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;
//用于解决冲突，pos为哈希函数
HashNode* pHead = hashTable[pos];
while(pHead)
{
if(strcmp(pHead->sKey, skey) == 0)
{
printf("%s发生冲突!\n", skey);
return ;
}
pHead = pHead->pNext;
}
//动态建立结点，初始化，分配内存空间
HashNode* pNewNode = (HashNode*)malloc(sizeof(HashNode));
memset(pNewNode, 0, sizeof(HashNode));
pNewNode->sKey = (char*)malloc(sizeof(char) * (strlen(skey) + 1));
strcpy(pNewNode->sKey, skey);
pNewNode->nValue = nvalue;
//指针后移
pNewNode->pNext = hashTable[pos];
hashTable[pos] = pNewNode;
//表长增加
hash_table_size++;
}
//删除
void hash_table_remove(const char* skey)
{
unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;
if(hashTable[pos])
{
HashNode* pHead = hashTable[pos];
HashNode* pLast = NULL;
HashNode* pRemove = NULL;
while(pHead)
{
if(strcmp(skey, pHead->sKey) == 0)
{ //若str1==str2，则返回零;
//若str1>str2，则返回正数;
//若str1<str2，则返回负数。
pRemove = pHead;//若相等，用pRemove记录
break;
}
pLast = pHead; //若不相等，不断后移
pHead = pHead->pNext;
}
if(pRemove)
{
if(pLast)
pLast->pNext = pRemove->pNext;//实现删除1
else
hashTable[pos] = NULL;//实现删除2
free(pRemove->sKey);
free(pRemove);
}
}
}
//查找
HashNode* hash_table_lookup(const char* skey)
{
unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;
if(hashTable[pos])
{
HashNode* pHead = hashTable[pos];
while(pHead)
{
if(strcmp(skey, pHead->sKey) == 0)
return pHead;//查找成功
pHead = pHead->pNext;
}
}
return NULL;
}
//打印
void hash_table_print()
{
int i;
for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)
if(hashTable[i])//表不空
{
HashNode* pHead = hashTable[i];
printf("%d=>", i);
while(pHead)
{
printf("%s:%d ", pHead->sKey, pHead->nValue);
pHead = pHead->pNext;
}
printf("\n");
}
}
//释放内存
void hash_table_release()
{
int i;
for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)
{
if(hashTable[i])
{
HashNode* pHead = hashTable[i];
while(pHead)
{
HashNode* pTemp = pHead;
pHead = pHead->pNext;
if(pTemp)
{
free(pTemp->sKey);
free(pTemp);
}
//逐个释放
}
}
}
}
/* ============================主测试函数============================*/
#define MAX_STR_LEN 20
#define MIN_STR_LEN 10
void rand_str(char r[])
{
int i;
int len = MIN_STR_LEN + rand() % (MAX_STR_LEN - MIN_STR_LEN);
for(i = 0; i < len - 1; ++i)
r[i] = 'a' + rand() % ( 'z' - 'a');
r[len - 1] = '\0';
}
int main(int argc, char** argv)
{
srand(time(NULL));
hash_table_init();
int n = 10;
char str[MAX_STR_LEN + 1];
const char *key1 = "aaa111";
const char *key2 = "bbb222";
const char *key3 = "ccc333";
while(n--)
{
rand_str(str);
hash_table_insert(str, n);
}
printf("插入前\n");
hash_table_print();
hash_table_insert(key1, 1);
hash_table_insert(key2, 2);
hash_table_insert(key3, 2);
printf("插入后\n");
hash_table_print();
HashNode* pNode = hash_table_lookup(key1);
printf("查找结果:%d\n", pNode->nValue);
pNode = hash_table_lookup(key2);
printf("查找结果:%d\n", pNode->nValue);
printf("删除之前:\n");
hash_table_print();
hash_table_remove(key3);
printf("删除之后:\n");
hash_table_print();
hash_table_release();
return 0;
}