c语言实现哈希表

最近在做FTP服务器项目的时候，需要统计服务器的最大连接数和每IP连接数。
每IP连接数：指的是服务器连接同一个IP地址的次数
最大连接数：服务器最多可以连接客户端的个数
其中前者需要用到哈希表。
c++中，我们可以直接使用map或者unordered_map来产生pair键值对，c语言中没有对应的库，所以需要自己实现一下hash表的结构。
如下图所示：

1. hash表中保存的是哈希函数，桶结点的个数，以及二级指针：存储的是桶结点的地址。
2. 每一个桶结点中存放的是哈希结点的地址，是一个一级指针，桶结点的个数为4个。
3. 每一个hash结点是由key指针，value指针，结点的前驱指针，后继指针构成的。这里之所以存放的是指针，是因为它可以接收任意类型的数据。

一般哈希函数选择的是除留余数法。
hash(key)=key%p,其中p≤buckets，取最接近于buckets的质数即可。
需要注意的是，由于经过哈希函数映射之后，关键码对应的位置对应滴位置可能是相同的，因此采用开散列的方法，使用链表的结构将所有相同位置的关键码串联起来。
如下图所示：为了方便起见，11，22，33处对应的是哈希结点的地址而不是key值。链表的插入采用的是头插，提升效率。
例如key=0,11,22,33对应的地址都是相同的，可以采用链表的方式将其连接。

1.hash_node的结构：

typedef struct hash_node
{
	void *key;
	void *node;
	struct hash_node* prev;
	struct hash_node* next;
}hash_node_t;
1
2
3
4
5
6
7

2.hash表的结构
//函数指针 对应的函数名是hashfunc_t:参数一个为int，一个为void。经过typedef之后，可以通过hashfunc_t来代表函数指针。

typedef unsigned int (*hashfunc_t)(unsigned int, void*);

1
2

struct hash
{
	unsigned int buckets; //对应的桶的大小
	hashfunc_t hash_func; //保存的hash函数的地址
	hash_node_t **nodes; //二级指针，存放桶结点的首地址
};
1
2
3
4
5
6

3.hash表的生成
类型的重定义

typedef struct hash hash_t; 将hash表重定义为hash_t
1

哈希表的初始化

hash_func是自己定义的，这里存放的是函数地址。定义的hash_func如下所示：

unsigned int hash_func(unsigned int bucket_size, void* key)
{
	return (*(unsigned int*)key) % bucket_size;
}
1
2
3
4

注意，这里结点的大小是桶结点的个数乘以每一个指针的内存大小，对hash_nodes所指的内存空间进行内存的初始化，指针置为NULL。

hash_t *hash_alloc(unsigned int buckets, hashfunc_t hash_func)
{
	hash_t *hash = (hash_t *)malloc(sizeof(hash_t));
	assert(hash != NULL);
	hash->buckets = buckets;
	hash->hash_func = hash_func;
	int size = buckets * sizeof(hash_node_t *);
	hash->nodes = (hash_node_t **)malloc(size);
	memset(hash->nodes, 0, size);
	return hash;
}
1
2
3
4
5
6
7
8
9
10
11

下面部分是获取关键码对应的桶结点的位置，通过hash函数映射之后计算出对应的bucket，将对应结点的地址返回。

hash_node_t** hash_get_bucket(hash_t* hash, void* key)
{
	unsigned int bucket = hash->hash_func(hash->buckets, key);
	if (bucket >= hash->buckets)
	{
		fprintf(stderr, "bad bucket lookup\n");
		exit(1);
	}
	return &(hash->nodes[bucket]);
}
1
2
3
4
5
6
7
8
9
10

下面部分是通过关键值key来查询对应的结点，例如我们需要查找key=22的结点，找到buckets的位置之后，链表向后遍历即可。
之前自己理解的时侯，总觉得桶结点已经找到了，为什么还需要向后遍历呢，其实是需要的，因为当前桶的头结点存储的key值可能不是我们需要找的，比如上面的例子中，buckets[0]存储的是key=0的元素的地址。

1. 获取当前key值对应的桶结点的地址。
2. node指向当前的桶结点的头部，依次向后寻找，直到node指向的key值和要寻找的key值相等时，代表找到了对应的结点，因此返回该结点即可。
3. memcmp（void * str1,void * str2,size_t n）用来对比str1和str2前n个字节大小是否相等。

hash_node_t* hash_get_node_by_key(hash_t* hash, void* key, unsigned int key_size)
{
	hash_node_t** bucket = hash_get_bucket(hash, key);
	hash_node_t* node = *bucket;
	if (node == NULL)
	{
		return NULL;
	}
	while (node != NULL && memcmp(node->key, key, key_size) != 0)
	{
		node = node->next;
	}
	return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

查询key值对应的value值

代码如下所示：如果找到key值，就返回当前key值对应的value值。否则返回NULL

void* hash_lookup_entry(hash_t* hash, void* key, unsigned int key_size)
{
	hash_node_t* node = hash_get_node_by_key(hash, key, key_size);
	if (node == NULL)
	{
		return NULL;
	}
	return node->value;
}
1
2
3
4
5
6
7
8
9

向哈希表中添加结点

需要给定key值的地址，对应的大小，value值的地址，对应的大小。

1. 首先查找，如果已经存在相同的key值，那么程序就会报错。
2. 其次申请新的hash结点，对前驱和后继赋空。将key和value的值拷贝到node->key和node->value中。
3. 获取当前key值对应的bucket的地址。
4. 如果为空，代表不存在，直接将结点插入，如果不为空，代表地址发生了冲突，因此需要将新的结点插入到头部。
   

void hash_add_entry(hash_t* hash, void* key, unsigned int key_size, void* value, unsigned int value_size)
{
	if (hash_lookup_entry(hash, key, key_size))
	{
		fprintf(stderr, "duplicate hash key\n");
		return;
	}
	hash_node_t* node = malloc(sizeof(hash_node_t));
	node->prev = NULL;
	node->next = NULL;
	node->key = malloc(key_size);
	memcpy(node->key, key, key_size);
	node->value = malloc(value_size);
	memcpy(node->value, value, value_size);
	hash_node_t** bucket = hash_get_bucket(hash, key);
	if (*bucket == NULL)
	{
		*bucket = node;
	}
	else
	{
		// 将新结点插入到链表头部
		// 当前结点的后继指向下一个结点。
		node->next = *bucket;
		// 
		(*bucket)->prev = node;
		*bucket = node;
	}
}
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

释放hash表中的结点

1. 检查key值是否存在，存在的话，释放对应的key和value。
2. 如果被释放的结点存在前驱指针，那么前驱指针的下一个指针指向当前被释放结点的下一个结点。如果不存在前驱指针，那么说明当前指针是头结点，故找到对应的桶结点的位置，将桶结点指向当前结点的下一个结点。
3. 当前结点下一个结点不为空，下一个结点的前驱结点指向当前结点的前驱结点。
   

void hash_free_entry(hash_t* hash, void* key, unsigned int key_size)
{
	hash_node_t* node = hash_get_node_by_key(hash, key, key_size);
	if (node == NULL)
	{
		return;
	}
	free(node->key);
	free(node->value);
	if (node->prev)
	{
	  // 第一步
		node->prev->next = node->next;
	}
	else
	{
		hash_node_t** bucket = hash_get_bucket(hash, key);
		*bucket = node->next;
	}
	// 后继结点的前驱连接被删除结点的前驱（第二步）
	if (node->next)
		node->next->prev = node->prev;
	// 释放结点
	free(node);
}
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

附录：假设给定的key值不是int值，要怎么处理呢？参考了一下别人的代码：将对应的字符串转为相对应的ASII值，再进行计算即可。

unsigned int hash_func_str(unsigned int bucket_size, char* key)
{
	int sum = 0;
	char* tmp = key;
	while (*tmp != '\0')
	{
		sum += *tmp;
		tmp++;
	}
	return sum % bucket_size;
}
1
2
3
4
5
6
7
8
9
10
11

打印hash表

1.key值为数字的时候

void printhash(hash_t* hash1)
{
	hash_node_t** z = hash1->nodes;
	int i = 0;
	for (i = 0; i < hash1->buckets; ++i)
	{
		if (z[i] == NULL)
			continue;
		while (z[i]!= NULL)
		{
			printf("key:%d,value:%d\n", *(int*)(z[i]->key), *(int*)(z[i]->value));
			z[i] = z[i]->next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.key值为字符串的时候

void printhash(hash_t* hash1)
{
	hash_node_t** z = hash1->nodes;
	int i = 0;
	for (i = 0; i < hash1->buckets; ++i)
	{
		if (z[i] == NULL)
			continue;
		while (z[i]!= NULL)
		{
			printf("key:%s,value:%d\n", (char*)z[i]->key, *(int*)(z[i]->value));
			z[i] = z[i]->next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

测试函数如下所示：

static struct hash* ip_count_hash;
int main()
{
	ip_count_hash = hash_alloc(17, hash_func_str);
	char key1[] = "ab";
	//printf("%d\n", sizeof(key1));
	int value1 = 100;
	char key2[] = "bc";
	int value2 = 20;
	char key3[] = "cde";
	int value3 = 30;
	hash_add_entry(ip_count_hash, &key1, sizeof(key1), &value1,sizeof(int));
	hash_add_entry(ip_count_hash, &key2, sizeof(key2), &value2, sizeof(int));
	hash_add_entry(ip_count_hash, &key3, sizeof(key3), &value3, sizeof(int));
	printhash(ip_count_hash);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

后续再研究闭散列吧，c语言和c++的实现差距还是挺大的，本篇主要是为了FTP服务器的IP数目限制所写的，比较简单一点，有兴趣的同学可以参考一下这篇博客哦
FTP项目第三部分