目录
前言
一、创建结构体
二、定义哈希表指针
三、函数操作
1. HASH_ADD
2. HASH_FIND
四、运用
剑指 Offer 52. 两个链表的第一个公共节点
两数之和
692. 前K个高频单词
前言
很早之前，在我刷leetcode的时候遇见使用哈希表的题目，我怀着好奇心去搜索，发现C语言可以用数组简单模拟（但是key值超过数组最大范围那就不行了），但是写了一篇关于简单哈希表运用的文章
数组模拟哈希表的简单运用https://blog.csdn.net/Dusong_/article/details/127257647?spm=1001.2014.3001.5502
但是用数组仅限于key为整型(int)，但是如果key是一个自定义类型，就不能用数组模拟了
头文件：
#include "uthash.h"uthash是一个C语言的hash表实现。它以宏定义的方式实现hash表，不仅加快了运行的速度，而且与key类型无关的优点
一、创建结构体
在使用之前需要定义这样一个结构体：
struct HashTable {
struct ListNode *key; /*以链表一节点为例*/
int value;
UT_hash_handle hh;
};• hh是内部使用的hash处理句柄，在使用过程中，只需要在结构体中定义一个UT_hash_handle类型的变量即可，不需要为该句柄变量赋值，但必须在该结构体中定义该变量。
• Uthash所实现的hash表中，可以通过结构体成员hh的hh.prev和hh.next获取当前节点的上一个节点和下一个节点
二、定义哈希表指针
struct HashTable* hash;
hash = NULL;三、函数操作
1. HASH_ADD
struct ListNode *node= head;
hash = (struct HashTable*)malloc(sizeof(struct HashTable));
hash->key = node;
HASH_ADD(hh, hashTable, key, sizeof(struct HashTable *), hash);
hh: 可以将其理解为固定参数
hashTable: 最开始初始化的哈希表指针
key: 自定义的结构体中的key
sizeof(struct HashTable *) : 计算哈希结构体大小即一个键值对的大小
hash: 新创建的键值对，将其加入hashTable中
2. HASH_FIND
struct ListNode *node= head; /*在哈希表中查找node节点*/
struct HashTable *ret = NULL; /*用于接收函数返回的指针*/
HASH_FIND(hh, hashTable, &node, sizeof(struct HashTable *), ret);
if (ret != NULL) {
/*已找到*/
}&node: 该参数及作为key，在hashTable中查找这个节点，需要查找key的地址，所以需要用&。
ret: 如果查找到，则将指向这个键值对的指针返回到ret中，如果没有查找到则返回NULL；
四、运用
剑指 Offer 52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
特别注意：这道题中所说的相交并不能仅用两链表节点的值相等来判断，这样是错的，相交是指节点的地址相同。
直接将链表A中的所有结点存入哈希表中，在从头到尾遍历链表B，查找哈希表中对应的结点即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct HashTable {
struct ListNode* key;
UT_hash_handle hh;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
struct HashTable* hashTable = NULL;
struct ListNode* tmp = headA;
//将链表A的结点加入哈希表
while (tmp) {
struct HashTable* k_v = (struct HashTable*)malloc(sizeof(struct HashTable));
k_v->key = tmp;
HASH_ADD(hh, hashTable, key, sizeof(struct HashTable*), k_v);
tmp = tmp->next;
}
//在哈希表中查找结点
tmp = headB;
while (tmp) {
struct HashTable* ret = NULL;
HASH_FIND(hh, hashTable, &tmp, sizeof(struct HashTable*), ret);
if (ret) {
return tmp;
}
tmp = tmp->next;
}
return NULL;
}两数之和
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：文章来源：https://www.toymoban.com/news/detail-417357.html
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
思路：
本题需要返回两个能凑成target的数的下标，用双指针是很容易想到的但是时间复杂度为O(n^2)，
跟着代码注释走，你会发现用哈希表非常巧妙，时间复杂度为O(n);
struct HashTable {
int key; /*数值作为key*/
int value; /*数的下标作为value*/
UT_hash_handle hh;
};
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
struct HashTable* hash = NULL; /*创建哈希表指针*/
int* res = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
for (int i = 0; i < numsSize; i++) { /*遍历整个数组*/
struct HashTable* ret = NULL; /*接收查找后的返回值*/
int key = target - nums[i];
HASH_FIND_INT(hash, &key, ret); /*在哈希表中查找target - nums[i]*/
//如果没有查找到，则将nums[i]作为key加入哈希表中
if (ret == NULL) {
struct HashTable* num = (struct HashTable*)malloc(sizeof(struct HashTable));
num->key = nums[i];
num->value = i;
HASH_ADD_INT(hash, key, num);
//如果找到，则找到这两个数
} else {
res[0] = ret->value;
res[1] = i;
}
}
return res;
}总结下来就是，在哈希表中查找target - nums[i] 的数是否存在
692. 前K个高频单词
该题查找的是指针形式的字符串，需要用HASH_FIND_KEYPTR，形如
struct HashTable {
char* key;
int val;
UT_hash_handle hh;
};若key是字符数组，查找则用HASH_FIND_STR
struct HashTable {
char key[20];
int val;
UT_hash_handle hh;
};leetcode传送➡️https://leetcode.cn/problems/top-k-frequent-words/description/?envType=study-plan&id=leetcode_75_level_1&plan=leetcode_75&plan_progress=bxag2sm
给定一个单词列表
words和一个整数k，返回前k个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"] 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 "i" 在 "love" 之前。
struct HashTable {
char* key;
int val;
UT_hash_handle hh;
};
struct HashTable* hash;
int FindVal (struct HashTable* hash, char* s) { //排序时，找到字符串在哈希表中对应的val
struct HashTable* tmp = NULL;
HASH_FIND_STR(hash, s, tmp);
return tmp == NULL ? 0 : tmp->val;
}
int cmp(char** s1, char** s2) {
int val1 = FindVal(hash, *s1);
int val2 = FindVal(hash, *s2);
if (val1 == val2) {
return strcmp(*s1,*s2); //出现次数相等时，按字典序排
} else {
return val2 -val1; //排倒序
}
}
char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize){
hash = NULL;
for (int i = 0; i < wordsSize; i++) { //遍历words
struct HashTable* tmp = NULL;
HASH_FIND_STR(hash, words[i], tmp); //查找字符串key
if (tmp) {
tmp-> val++;
} else {
struct HashTable* word = (struct HashTable*)malloc(sizeof(struct HashTable));
word->key = words[i];
word->val = 1;
/*当结构体中的键值为字符串数组时，使用HASH_ADD_STR。键值为字符串指针时使用HASH_ADD_KEYPTR*/
HASH_ADD_KEYPTR(hh, hash, word->key, strlen(word->key), word); //添加键值对
}
}
char** ret = (char**)malloc(sizeof(char*)*HASH_COUNT(hash)); //HASH_COUNT计算键值对的个数
*returnSize = 0;
struct HashTable* tmp = NULL;
for (tmp = hash; tmp != NULL; tmp = tmp->hh.next) { //遍历哈希表
ret[(*returnSize)++] = tmp->key;
}/*
struct HashTable *iter, *tmp;
HASH_ITER(hh, cnt, iter, tmp) {
ret[(*returnSize)++] = iter->key;
}*/
qsort(ret, *returnSize, sizeof(char*), cmp); //将整个数组排倒序，结果返回前k个
*returnSize = k;
return ret;
}更多相关知识参考https://bbs.huaweicloud.com/blogs/342451文章来源地址https://www.toymoban.com/news/detail-417357.html
到了这里，关于⌈C⌋哈希表UT_hash_handle——如何将结构体类型作为key的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
