参考：https://troydhanson.github.io/uthash/userguide.html

https://blog.csdn.net/lovemust/article/details/105208408

参考练习：https://leetcode-cn.com/circle/article/y7G2Gq/

1. 两数之和

struct hashTable {
int key;
int val;
UT_hash_handle hh;
};

struct hashTable *hashtable;

struct hashTable* FindVal(int ikey)
{
struct hashTable* tmp;
HASH_FIND_INT(hashtable, &ikey, tmp);
return tmp;
}

void AddNode(int ikey, int ival)
{
struct hashTable* it = FindVal(ikey);
if (it == NULL) {
struct hashTable* tmp = (struct hashTable *)malloc(sizeof(struct hashTable));
tmp->key = ikey;
tmp->val = ival;
HASH_ADD_INT(hashtable, key, tmp);
} else {
it->val = ival;
}
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
hashtable = NULL;
for (int i = 0; i < numsSize; i++) { struct hashTable *it = FindVal(target - nums[i]); if (it != NULL) { int *res = (int *)malloc(sizeof(int) * 2); *returnSize = 2; res[0] = it->val;
res[1] = i;
return res;
}
AddNode(nums[i], i);
}
*returnSize = 0;
return NULL;
}

49. 字母异位词分组

#include
#include
#include
#include
#include

#define MAXLENGTH 10000
struct hashTable {
char keyStr[MAXLENGTH]; // key值为排序后的字符串
int id; // 记录在res中的位置
int count; // 记录分组中元素的个数
UT_hash_handle hh;
};

int com(const void *a_, const void *b_){
char *a = (char *)a_;
char *b = (char *)b_;
return *a - *b;
}

char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
if (strsSize == 0) return NULL;
char ***res = (char ***)malloc(sizeof(char **) * strsSize);
*returnColumnSizes = (int *)malloc(sizeof(int) * strsSize);
*returnSize = 0;
struct hashTable *hashtable = NULL;
for(int i=0; ikeyStr, 0, sizeof(char) * MAXLENGTH);
memcpy(tmpHash->keyStr, tmp, sizeof(char) * len);
tmpHash->id = *returnSize;
tmpHash->count = 1;
HASH_ADD_STR(hashtable, keyStr, tmpHash);

        res\[\*returnSize\] = (char \*\*)malloc(sizeof(char \*) \* strsSize);  
        res\[\*returnSize\]\[tmpHash->count-1\] = (char \*)malloc(sizeof(char) \* (len + 1));

        memset(res\[\*returnSize\]\[tmpHash->count-1\], 0, sizeof(char) \* (len + 1));  
        memcpy(res\[\*returnSize\]\[tmpHash->count-1\], strs\[i\], sizeof(char) \* len);  
        (\*returnColumnSizes)\[\*returnSize\] = tmpHash->count;  
        (\*returnSize)++;  
    }  
    else {  
        // HASH表中有记录  
        res\[tmpHash->id\]\[tmpHash->count\] = (char \*)malloc(sizeof(char) \* (len + 1));  
        memset(res\[tmpHash->id\]\[tmpHash->count\], 0, sizeof(char) \* (len + 1));  
        memcpy(res\[tmpHash->id\]\[tmpHash->count\], strs\[i\], sizeof(char) \* len);  
        (\*returnColumnSizes)\[tmpHash->id\] = tmpHash->count + 1;  
        tmpHash->count = tmpHash->count + 1;

    }  
}

return res;

}

代码示例：

#include
#include
#include
#include
#include

typedef struct MyStruct {
int key;
int val1;
int val2;
UT_hash_handle hh;
} Hash;

int cmpFunc(const void *_a, const void *_b)
{
Hash *a = (Hash *)_a;
Hash *b = (Hash *)_b;
return a->val1 - b->val1;
}

int main(int argc, const char *argv[])
{

Hash \*hashTbl = NULL;  
Hash \*hashNode = NULL;  
Hash \*hashTmp = NULL;

for (int i = 0; i < 10; i++) {  
    hashNode = (Hash \*)malloc(sizeof(Hash));  
    hashNode->key = i;  
    hashNode->val1 = 1;  
    hashNode->val2 = 2;  
    HASH\_ADD\_INT(hashTbl, key, hashNode);  
}  
int a = 8;  
HASH\_FIND\_INT(hashTbl, &a, hashTmp);  
printf("%d\\n", hashTmp->val1);  
hashTmp->val1 = 100;

for (Hash \*s = hashTbl; s != NULL; s = s->hh.next) {  
    printf("%d,", s->val1);  
}  
printf("\\n");  
HASH\_SORT(hashTbl, cmpFunc);  
for (Hash \*s = hashTbl; s != NULL; s = s->hh.next) {  
    printf("%d,", s->val1);  
}

printf("\\n%d",HASH\_COUNT(hashTbl));  
return 0;  

}

面试题 16.02. 单词频率

typedef struct {
char name[20];
int count;
UT_hash_handle hh;
} WordsFrequency;

WordsFrequency *g_word = NULL;

void AddWord(char *iname)
{
WordsFrequency *tmp = NULL;
HASH_FIND_STR(g_word, iname, tmp);
if (tmp == NULL) {
tmp = malloc(sizeof(WordsFrequency));
// 下面三种方式都可以
// memcpy(tmp->name, iname, strlen(iname) + 1);
// strcpy(tmp->name, iname);
sprintf(tmp->name, "%s", iname);
tmp->count = 1;
HASH_ADD_STR(g_word, name, tmp);
} else {
tmp->count++;
}
}

WordsFrequency* wordsFrequencyCreate(char** book, int bookSize)
{
for (int i = 0; i < bookSize; i++) {
AddWord(book[i]);
}

return NULL;  

}

int wordsFrequencyGet(WordsFrequency* obj, char* word)
{
WordsFrequency *tmp = NULL;
HASH_FIND_STR(g_word, word, tmp);
if (tmp == NULL) {
return 0;
} else {
return tmp->count;
}
}

void wordsFrequencyFree(WordsFrequency* obj)
{
HASH_CLEAR(hh, g_word);
/*
WordsFrequency *cur = NULL;
WordsFrequency *tmp = NULL;
HASH_ITER(hh, g_word, cur, tmp) {
if (cur != NULL) {
HASH_DEL(g_word, cur);
free(cur);
}
}
*/
}

347. 前 K 个高频元素

typedef struct {
int key;
int value;
UT_hash_handle hh;
} hashTable;

hashTable *g_hash = NULL;

hashTable* FindNode(int ikey)
{
hashTable *tmp = NULL;
HASH_FIND_INT(g_hash, &ikey, tmp);
return tmp;
}

void AddNode(int ikey)
{
hashTable *tmp = FindNode(ikey);
if (tmp == NULL) {
tmp = malloc(sizeof(hashTable));
tmp->key = ikey;
tmp->value = 1;
HASH_ADD_INT(g_hash, key, tmp);
} else {
tmp->value++;
}
}

int Cmp(hashTable *a, hashTable *b)
{
return b->value - a->value;
}

int Sort()
{
HASH_SORT(g_hash, Cmp);
return 0;
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize)
{
*returnSize = 0;
if (nums == NULL || k > numsSize) {
return NULL;
}

for (int i = 0; i < numsSize; i++) {  
    AddNode(nums\[i\]);  
}

int \*res = malloc(sizeof(int) \* k);  
\*returnSize = k;

// 排序  
Sort();

// 遍历  
hashTable \*curr, \*tmp;  
int count = 0;  
HASH\_ITER(hh, g\_hash, curr, tmp) {  
    res\[count++\] = curr->key;  
    if (count == k) {  
        break;  
    }  
}

// 释放内存  
HASH\_ITER(hh, g\_hash, curr, tmp) {  
    HASH\_DEL(g\_hash, curr);  
    free(curr);  
}

return res;  

}

692. 前K个高频单词

typedef struct {
char key[20];
int value;
UT_hash_handle hh;
} hashTble;

hashTble *g_hash = NULL;

hashTble* FindNode(char *w)
{
hashTble *tmp = NULL;
HASH_FIND_STR(g_hash, w, tmp);
return tmp;
}

void AddNode(char *w)
{
hashTble *tmp = FindNode(w);
if (tmp == NULL) {
tmp = malloc(sizeof(hashTble));
memcpy(tmp->key, w, strlen(w) + 1);
tmp->value = 1;
HASH_ADD_STR(g_hash, key, tmp);
} else {
tmp->value++;
}
}

/*
* 两次排序：
* 1.先排序字母
* 2.再排序出现次数
*/
int CmpAlpha(hashTble *a, hashTble *b)
{
return strcmp(a->key, b->key);
}

void SortAlpha()
{
HASH_SORT(g_hash, CmpAlpha);
}

int CmpCount(hashTble *a, hashTble *b)
{
return b->value - a->value;
}

void SortCount()
{
HASH_SORT(g_hash, CmpCount);
}

char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize)
{
*returnSize = 0;
if (words == NULL || k > wordsSize) {
return NULL;
}

\*returnSize = k;  
char \*\*res = malloc(sizeof(char \*) \* k);

// 添加节点  
for (int i = 0; i < wordsSize; i++) {  
    AddNode(words\[i\]);  
}

// 排序  
SortAlpha();  
SortCount();

// 遍历  
hashTble \*cur, \*tmp;  
int count = 0;  
HASH\_ITER(hh, g\_hash, cur, tmp) {

    // 注意char \*\* 里面一层的内存要先申请，才能使用  
    res\[count\] = malloc(sizeof(char) \* (strlen(cur->key) + 1));  
    strcpy(res\[count++\], cur->key);

    if (count == k) {  
        break;  
    }  
}

// 释放内存  
HASH\_ITER(hh, g\_hash, cur, tmp) {  
    HASH\_DEL(g\_hash, cur);  
    free(cur);  
}

return res;  

}