告别数组模拟！用uthash在C语言里玩转结构体当Key的哈希表（附LeetCode实战）

告别数组模拟！用uthash在C语言里玩转结构体当Key的哈希表（附LeetCode实战）

当你在LeetCode上遇到需要统计单词频率或处理复杂数据结构的问题时，是否还在用数组模拟哈希表？这种传统方法在面对结构体、字符串等复杂Key时往往捉襟见肘。本文将带你突破这一限制，掌握uthash这一强大工具，让你的C语言编程能力更上一层楼。

1. 为什么需要uthash？

在算法竞赛和日常开发中，哈希表是最常用的数据结构之一。C语言标准库并未提供原生的哈希表实现，导致许多开发者不得不使用数组模拟。这种方法虽然简单，但存在三大致命缺陷：

1. Key类型受限：仅适用于整数型Key
2. 空间浪费严重：需要预先分配足够大的数组空间
3. 功能单一：缺乏动态扩容、冲突处理等高级特性

uthash完美解决了这些问题，它具有以下优势：

• 支持任意Key类型：结构体、字符串、指针等均可作为Key
• 动态内存管理：自动处理内存分配和释放
• 丰富的操作接口：查找、插入、删除、遍历一应俱全
• 高性能：基于宏实现，接近原生代码的执行效率

2. uthash快速入门

2.1 基本结构定义

使用uthash的第一步是定义包含UT_hash_handle的结构体：

#include "uthash.h" struct my_struct { int id; // 可以是任意类型的key char name[20]; UT_hash_handle hh; // 必须包含这个字段 };

2.2 核心API速查

uthash提供了多种操作宏，最常用的包括：

3. 实战：结构体作为Key

让我们通过一个具体案例来演示如何使用结构体作为Key。假设我们需要统计三维坐标点的出现次数：

struct Point { int x; int y; int z; }; struct PointHash { struct Point key; // 结构体作为Key int count; // 出现次数 UT_hash_handle hh; }; void add_point(struct PointHash **hash, struct Point p) { struct PointHash *s; // 查找是否已存在 HASH_FIND(hh, *hash, &p, sizeof(struct Point), s); if (s == NULL) { s = (struct PointHash*)malloc(sizeof(struct PointHash)); s->key = p; s->count = 1; HASH_ADD(hh, *hash, key, sizeof(struct Point), s); } else { s->count++; } }

注意：当使用结构体作为Key时，HASH_FIND需要传入Key的地址，且要确保结构体中的所有字段都正确初始化，因为它们都会参与哈希计算。

4. LeetCode实战解析

4.1 两数之和（#1）

这是最经典的哈希表应用题，uthash解法比数组模拟更通用：

struct num_hash { int key; // 数值本身作为Key int index; // 数组下标作为Value UT_hash_handle hh; }; int* twoSum(int* nums, int numsSize, int target, int* returnSize) { struct num_hash *hash = NULL, *tmp = NULL; int *result = malloc(2 * sizeof(int)); *returnSize = 2; for (int i = 0; i < numsSize; i++) { int complement = target - nums[i]; HASH_FIND_INT(hash, &complement, tmp); if (tmp) { result[0] = tmp->index; result[1] = i; break; } tmp = malloc(sizeof(struct num_hash)); tmp->key = nums[i]; tmp->index = i; HASH_ADD_INT(hash, key, tmp); } // 释放哈希表内存 struct num_hash *current, *temp; HASH_ITER(hh, hash, current, temp) { HASH_DEL(hash, current); free(current); } return result; }

4.2 前K个高频单词（#692）

这道题展示了如何处理字符串Key和复杂排序：

struct word_count { char *word; // 字符串指针作为Key int count; // 出现次数 UT_hash_handle hh; }; int compare_words(struct word_count *a, struct word_count *b) { if (a->count == b->count) { return strcmp(a->word, b->word); } return b->count - a->count; } char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize) { struct word_count *counts = NULL, *wc = NULL, *tmp = NULL; // 统计词频 for (int i = 0; i < wordsSize; i++) { HASH_FIND_STR(counts, words[i], wc); if (wc) { wc->count++; } else { wc = malloc(sizeof(struct word_count)); wc->word = words[i]; wc->count = 1; HASH_ADD_KEYPTR(hh, counts, wc->word, strlen(wc->word), wc); } } // 排序 HASH_SORT(counts, compare_words); // 提取前K个 char **result = malloc(k * sizeof(char *)); *returnSize = k; int i = 0; for (wc = counts; wc != NULL && i < k; wc = wc->hh.next) { result[i++] = wc->word; } // 注意：实际应用中应该深拷贝字符串而非直接返回指针 return result; }

5. 高级技巧与性能优化

5.1 自定义哈希函数

uthash允许自定义哈希函数来处理特殊需求：

unsigned int custom_hash_function(void *key, unsigned int hashv) { struct custom_key *ckey = (struct custom_key*)key; // 实现你自己的哈希逻辑 return hashv; } // 使用自定义哈希函数 HASH_FIND(hh, hash, &key, sizeof(key), tmp, custom_hash_function);

5.2 内存管理最佳实践

uthash不会自动释放内存，需要手动管理：

void free_hash(struct my_struct **hash) { struct my_struct *current, *tmp; HASH_ITER(hh, *hash, current, tmp) { HASH_DEL(*hash, current); free(current->key); // 如果key是动态分配的 free(current); } }

5.3 性能对比测试

我们对不同实现进行了性能测试（处理10万条数据）：

测试结果表明，uthash在查询性能上优势明显，且内存占用更优。