＜C＞ C语言哈希表使用

C语言哈希表使用实例

一、头文件

1. #include "uthash.h"

复制代码

二、API

结构体形式

1. struct HashTable_t {
2. int key;
3. int value;
4. UT_hash_handle hh;
5. }

复制代码

• key的类型可以为char *、char []、int、void* 四种， value可以为任意类型。
• UT_hash_handle 结构体为hash API使用，可以不用关注。

HASH_ADD_INT()

添加int参数至哈希表，HASH_ADD_INT(hash， key， value)

HASH_FIND_INT()

从哈希表中查找int参数，HASH_FIND_INT(hash， &key， value)
与HASH_ADD_INT不同，FIND API中的key需要取地址。

HASH_DEL（）

从哈希表中删除节点。

HASH_COUNT()

统计哈希表中存在的节点数。

三、示例代码

代码为leetcode题目， 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. /**
2. * Note: The returned array must be malloced, assume caller calls free().
3. */
4. struct hashTable { //HASH表结构体定义
5. int key;
6. int value;
7. UT_hash_handle hh;
8. };
10. struct hashTable *Hash; //哈希表全局标量
12. struct hashTable *find(int key) //查找哈希表中是否存在
13. {
14. struct hashTable *tmp = (struct hashTable *)malloc(sizeof(struct hashTable));
15. HASH_FIND_INT(Hash, &key, tmp);
17. if(tmp)
18. return tmp;
19. else
20. return NULL;
21. }
23. void insert(int key, int value)
24. {
25. struct hashTable *tmp = find(key); //插入前，查找是否有相同key
27. if(tmp == NULL) { //不相同
28. struct hashTable *node = (struct hashTable *)malloc(sizeof(struct hashTable));
29. node->key = key;
30. node->value = value;
31. HASH_ADD_INT(Hash, key, node); //创建新的哈希节点，插入数据。
32. } else
33. tmp->value = value //存在相同，更新数据。
34. }
36. int* twoSum(int* nums, int numsSize, int target, int* returnSize){
37. int *result = (int *)malloc(sizeof(int) * 2);
38. struct hashTable *ret = NULL;
39. Hash = NULL;
41. for(int i = 0 ; i < numsSize; i++){
42. ret = find(target - nums[i]);
43. if(ret) {
44. result[0] = ret->value;
45. result[1] = i;
46. *returnSize = 2;
47. return result;
48. }
49. insert(nums[i], i);
50. }
51. *returnSize = 0;
52. return NULL;
53. }

复制代码

总结

1、熟悉C库哈希表的使用
2、两数之和，如何转化为哈希表的思路。需要重复遍历的同一个数组，可以考虑使用哈希表，减少时间复杂度，但哈希表的使用是提高了空间复杂度。牺牲空间，提升速度。