【C语言】动手写一个哈希表_c语言哈希表头文件

引言

近来无聊，决定动手写点程序练练手，所以从最基础的哈希表数据结构开始，全程参考的此处的GitHub项目

环境

• Window10 、nodepad++编辑器 、MinGW 编译器

第一次尝试搭建极简的C语言开发环境（对于编程小白不太友好，不建议），网上教程较多，不赘述，比如这、这

介绍

哈希表

哈希冲突是不可避免的，常用的解决方法有两种开放地址法、链表法
本文基于开放地址法，开放地址法中有三种方式来寻找其他的位置，分别是**「线性探测」、「二次探测」、「再哈希法」**。本文采用线性探测法，即若插入位置已经有值，则向下顺序寻找空位置进行插入。

哈希表应该具有的API接口

• search(a, k)：从哈希表a返回与 key 关联的值，或者如果该键不存在返回NULL。
• insert(a, k, v)：向哈希结构a里面插入一个键为k,值为v的元素
• delete(a, k)：删除键为k的元素，如果 不存在，则不执行任何操作。

构建数据结构

构建每个元素和和哈希表的数据结构

typedef struct {
    char* key;
    char* value;
} ht_item;
typedef struct {
    int size;
    int count;
    ht_item** items;
} ht_hash_table;
1
2
3
4
5
6
7
8
9

初始化和删除

初始化元素：malloc申请新元素的空间，并将key和value对应赋值。

#include <stdlib.h>
#include <string.h>
static ht_item* ht_new_item(const char* k, const char* v) {
    ht_item* i = malloc(sizeof(ht_item));
    i->key = strdup(k);
    i->value = strdup(v);
    return i;
}
1
2
3
4
5
6
7
8

初始化哈希表：malloc申请哈希表的空间，calloc申请存放元素地址的空间(与malloc不同的是申请的区域为初始化为0)，并将size和count对应赋值。

ht_hash_table* new_ht() {
    ht_hash_table* h = malloc(sizeof(ht_hash_table)) ;
	h->size = 53;
	h->count = 0;
	h->items = calloc((size_t)h->size, sizeof(ht_item*))
	return h;
}
1
2
3
4
5
6
7

删除：释放掉申请的内存，防止内存泄漏。注意释放的先后顺序，i和h最后才释放

static void ht_del_item(ht_item* i) {
    free(i->key);
    free(i->value);
    free(i);
}
void ht_del_hash_table(ht_hash_table* h)
{
    for(int i = 0;i <h->size;i++)
	{
		if(h->items[i] != NULL)
			ht_delete_item(h->items[i]);
	}
	free(h->items);
	free(h);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

使用static关键字修饰的静态函数不能被其它文件调用，作用于仅限于本文件
程序其中用到的基础C语言的库函数：

头文件：#include <stdlib.h>
定义函数：void* malloc (size_t size);
参数说明：size 为需要分配的内存空间的大小，以字节（Byte）计。
函数说明：malloc() 在堆区分配一块指定大小的内存空间，用来存放数据。这块内存空间在函数执行完成后不会被初始化，它们的值是未知的。如果希望在分配内存的同时进行初始化，请使用 calloc() 函数。
返回值：分配成功返回指向该内存的地址，失败则返回 NULL

头文件：#include <string.h>
定义函数：char * strdup(const char *s);
函数说明：strdup()会先用maolloc()配置与参数s 字符串相同的空间大小，然后将参数s 字符串的内容复制到该内存地址，然后把该地址返回。该地址最后可以利用free()来释放。
返回值：返回一字符串指针，该指针指向复制后的新字符串地址。若返回NULL 表示内存不足。

定义函数：void* calloc (size_t num, size_t size);
函数说明：calloc() 在内存中动态地分配 num 个长度为 size 的连续空间，并将每一个字节都初始化为 0。所以它的结果是分配了 num*size 个字节长度的内存空间，并且每个字节的值都是0。
返回值：分配成功返回指向该内存的地址，失败则返回 NULL。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

哈希函数

我们将使用一个通用字符串哈希函数
此哈希函数有两个步骤：

• 将字符串转换为大整数
• 通过取其余数将整数的大小减小到固定范围mod m
  该变量应为大于字母表大小的质数。我们正在对 ASCII 字符串进行哈希处理，其字母大小为 128，因此我们应该选择一个大于此值的素数a

哈希表的大小为何是素数？。

static int ht_hash(const char* s, const int a, const int m)
 {
    long hash = 0;
    const int len_s = strlen(s);
    for (int i = 0; i < len_s; i++) {
        hash += (long)pow(a, len_s - (i+1)) * s[i];
        hash = hash % m;
    }
    return (int)hash;
}
1
2
3
4
5
6
7
8
9
10

实现接口函数:插入/查询/删除

• 虽然代码不长，但还是调试了很久，一不小心就访问到空指针。
• 因为采用线性探测法，所示插入时当索引位置非空，就顺序向下一个位置寻找。
  搜索时，除了判定非NULL还需要比较键值，因为插入的位置是不确定的，需顺序向下寻找。删除同理。
• 插入和删除时要注意count的判别和修改。

int insert(ht_hash_table* h, const char* k, const char* v)
{
	ht_item* i = ht_new_item(k,v);
	int index = ht_hash(k,151,53);
	if(h->count >= h->size)
		return -1;
	h->count++;
	while(1)
	{
		if((h->items[index])==NULL)
		{
			h->items[index] = i;
			return index;
		}
		index++;
		if(index == h->size)
			index = 0;
	}
}
char* search(ht_hash_table* h, const char* k)
{
	int index = ht_hash(k,151,53);
	for (int i = 0; i < h->size;i++)
	{	
		if(h->items[index]!=NULL)
			if(strcmp(h->items[index]->key,k)==0)
				return h->items[index]->value;
		index++;
		if(index == h->size)
			index = 0;		
	}
	return NULL;	
}
void delete(ht_hash_table* h, const char* k)
{
	int index = ht_hash(k,151,53);
	for (int i = 0; i < h->size;i++)
	{	
		if(h->items[index]!=NULL)
			if(strcmp(h->items[index]->key,k) == 0)
				{
					ht_del_item(h->items[index]);
					h->items[index] = NULL;
					h->count--;
					return ;
				}
		index++;
		if(index == h->size)
			index = 0;
	}
	return ;	
}
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

主函数

int main(void)
{
	ht_hash_table* ht=new_ht();
	insert(ht,"niuniu","hahaha");
	insert(ht,"shuoshuo","xixixi");
	char* s = search(ht,"shuoshuo");
	if(s==NULL)
		printf("查找失败  %d\n",s);
	else
		printf(s);
	
	delete(ht,"shuoshuo");
	char* c = search(ht,"shuoshuo");
	if(c==NULL)
		printf("查找失败  %d\n",c);
	else
		printf(c);
	
	ht_del_hash_table(ht);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

自动修改桶的大小

未完待续。。。

---

完整代码

#include <stdlib.h>
#include <string.h>

#include "hash_table.h"
void ht_delete_item(ht_hash_table* h){}
static ht_item* ht_new_item(const char* k, const char* v) 
{
    ht_item* i = malloc(sizeof(ht_item));
    i->key = strdup(k);
    i->value = strdup(v);
    return i;
}
static void ht_del_item(ht_item* i)
 {
    free(i->key);
    free(i->value);
	free(i);
}
ht_hash_table* new_ht() 
{
    ht_hash_table* h = malloc(sizeof(ht_hash_table)) ;
	h->size = 53;
	h->count = 0;
	h->items = calloc((size_t)h->size, sizeof(ht_item*));
	return h;
}
void ht_del_hash_table(ht_hash_table* h)
{
    for(int i = 0;i <h->size;i++)
	{
		if(h->items[i] != NULL)
			ht_delete_item(h->items[i]);
	}
	free(h->items);
	free(h);
}
static int ht_hash(const char* s, const int a, const int m)
 {
    long hash = 0;
    const int len_s = strlen(s);
    for (int i = 0; i < len_s; i++) {
        hash += (long)pow(a, len_s - (i+1)) * s[i];
        hash = hash % m;
    }
    return (int)hash;
}
int insert(ht_hash_table* h, const char* k, const char* v)
{
	ht_item* i = ht_new_item(k,v);
	int index = ht_hash(k,151,53);
	if(h->count >= h->size)
		return -1;
	h->count++;
	while(1)
	{
		if((h->items[index])==NULL)
		{
			h->items[index] = i;
			return index;
		}
		index++;
		if(index == h->size)
			index = 0;
	}
}
char* search(ht_hash_table* h, const char* k)
{
	int index = ht_hash(k,151,53);
	for (int i = 0; i < h->size;i++)
	{	
		if(h->items[index]!=NULL)
			if(strcmp(h->items[index]->key,k)==0)
				return h->items[index]->value;
		index++;
		if(index == h->size)
			index = 0;
		
	}
	return NULL;
	
}
void delete(ht_hash_table* h, const char* k)
{
	int index = ht_hash(k,151,53);
	for (int i = 0; i < h->size;i++)
	{	
		if(h->items[index]!=NULL)
			if(strcmp(h->items[index]->key,k) == 0)
				{
					ht_del_item(h->items[index]);
					h->items[index] = NULL;
					h->count--;
					return ;
				}
		index++;
		if(index == h->size)
			index = 0;
	}
	return ;	
}
int main(void)
{
	ht_hash_table* ht=new_ht();
	insert(ht,"niuniu","hahaha");
	insert(ht,"shuoshuo","xixixi");
	char* s = search(ht,"shuoshuo");
	if(s==NULL)
		printf("查找失败  %d\n",s);
	else
		printf(s);
	
	delete(ht,"shuoshuo");
	char* c = search(ht,"shuoshuo");
	if(c==NULL)
		printf("查找失败  %d\n",c);
	else
		printf(c);
	
	ht_del_hash_table(ht);
	
	return 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