文章目錄

1 定義一個哈希表
- 鍵
- 值
- UT_hash_handle
2 哈希操作
- 聲明
- 添加
- 查找
- 刪除
- 獲取哈希表中元素個數
- 迭代
- 排序
3 案例
鍵的使用

官網解釋：https://troydhanson.github.io/uthash/userguide.html
在使用之前，我們必須包含uthash.h的頭文件，你需要將該頭文件加入到你的項目中

#include "uthash.h"

1 定義一個哈希表

我們直到，在哈希表中，最重要的就是鍵和值，在 utash 中，哈希表由結構體組成。每個結構體代表一個鍵值關聯。一個或多個結構體里的域構成鍵，該結構指針就是值。

我們定義一個my_struct 結構體，用id的值作為鍵值，my_struct 的實例指針作為值

#include "uthash.h"struct my_struct {int id;                    /* key */char name[10];UT_hash_handle hh;         /* makes this structure hashable */
};

鍵

鍵的數據類型或名稱沒有限制，可以具有任何名稱和數據類型。但是再把值添加到哈希表之前，必須保證鍵沒有被使用，保證鍵的唯一性。可以使用HASH_FIND檢查哈希表是否已存在該鍵。

值

值就是結構體實例的指針

UT_hash_handle

UT_hash_handle 字段必須要存在于你定義的結構體中，它不需要初始化，可以命名任何東西，比如hh，UT_hash_handle 用來標記該結構體是哈希表。

2 哈希操作

聲明

我們必須將聲明的哈希表結構體初始化為NULL指針

struct my_struct *users = NULL;    /* important! initialize to NULL */

添加

按照合適非方法分配和初始化結構體，初始化必須保證鍵是唯一值，然后調用HASH_ADD添加到哈希表中，這里我們使用便利宏 HASH_ADD_INT，它為 int 類型的鍵提供了簡化的用法。

void add_user(int user_id, char *name) {struct my_struct *s;s = malloc(sizeof *s);s->id = user_id;strcpy(s->name, name);HASH_ADD_INT(users, id, s);  /* id: name of key field */
}

HASH_ADD_INT 的第一個參數是哈希表，第二個參數是鍵的名稱。，在這里，這是 id。最后一個參數是指向要添加的結構指針。

將結構添加到哈希表后，不要更改其鍵的值。我們要從哈希中刪除該項目，更改鍵值，然后重新添加它。

在上面的示例中，我們沒有檢查 user_id 是否已經是哈希中某個現有項目的鍵值。如果你的程序有可能生成重復鍵，則必須在將鍵添加到散哈希表之前顯式檢查唯一性。如果鍵已經在散列中，可以簡單地修改散列中的現有結構，而不是添加項。 將具有相同鍵的兩個項目添加到哈希表是錯誤的。

讓我們重寫 add_user 函數來檢查 id 是否在哈希中。只有當 id 不存在于散列中時，我們才創建項目并添加它。否則我們只是修改已經存在的結構。

void add_user(int user_id, char *name) {struct my_struct *s;HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */if (s == NULL) {s = (struct my_struct *)malloc(sizeof *s);s->id = user_id;HASH_ADD_INT(users, id, s);  /* id: name of key field */}strcpy(s->name, name);
}

查找

要在哈希中查找結構體，你需要它的鍵。然后調用 HASH_FIND。（這里我們使用便利宏 HASH_FIND_INT 來處理 int 類型的鍵）。

struct my_struct *find_user(int user_id) {struct my_struct *s;HASH_FIND_INT(users, &user_id, s);  /* s: output pointer */return s;
}

這里，哈希表是users，&user_id 指向鍵（本例中為整數）。最后，s 是 HASH_FIND_INT 的輸出變量。最終結果是 s 指向具有給定鍵的結構，或者如果在散列中找不到鍵，則為 NULL。

刪除

要從哈希中刪除結構體，你必須有一個指向它的指針。（如果你只有鍵，首先做一個 HASH_FIND 來獲取結構指針）。

void delete_user(struct my_struct *user) {HASH_DEL(users, user);  /* user: pointer to deletee */free(user);             /* optional; it's up to you! */
}

同樣，users 是哈希表，user 是指向我們要從哈希中刪除的結構的指針。

刪除所有元素：HASH_ITER 宏是一個刪除安全的迭代構造，它擴展為一個簡單的 for 循環。

void delete_all() {struct my_struct *current_user, *tmp;HASH_ITER(hh, users, current_user, tmp) {HASH_DEL(users, current_user);  /* delete; users advances to next */free(current_user);             /* optional- if you want to free  */}
}

獲取哈希表中元素個數

可以使用 HASH_COUNT 獲取哈希表中的結構體數：

unsigned int num_users;
num_users = HASH_COUNT(users);
printf("there are %u users\n", num_users)

迭代

你可以通過從頭開始并跟隨 hh.next 指針來遍歷散列中的項目。

void print_users() {struct my_struct *s;for (s = users; s != NULL; s = s->hh.next) {printf("user id %d: name %s\n", s->id, s->name);}
}

排序

當你跟隨 hh.next 指針時，以“插入順序”訪問散列中的項目。你可以使用 HASH_SORT 將項目排序為新順序。

HASH_SORT(users, cmpfcn);

第二個參數是一個指向比較函數的指針。它必須接受兩個指針參數（要比較的項目），并且必須返回一個小于零、零或大于零的 int，如果第一項分別排序在第二項之前、等于或之后。（這與標準 C 庫中 strcmp 或 qsort 使用的約定相同）。

int sort_function(void *a, void *b) {/* compare a to b (cast a and b appropriately)* return (int) -1 if (a < b)* return (int)  0 if (a == b)* return (int)  1 if (a > b)*/
}

int by_name(const struct my_struct *a, const struct my_struct *b) {return strcmp(a->name, b->name);
}int by_id(const struct my_struct *a, const struct my_struct *b) {return (a->id - b->id);
}void sort_by_name() {HASH_SORT(users, by_name);
}void sort_by_id() {HASH_SORT(users, by_id);
}

3 案例

#include <stdio.h>   /* printf */
#include <stdlib.h>  /* atoi, malloc */
#include <string.h>  /* strcpy */
#include "uthash.h"struct my_struct {int id;                    /* key */char name[21];UT_hash_handle hh;         /* makes this structure hashable */
};struct my_struct *users = NULL;void add_user(int user_id, const char *name)
{struct my_struct *s;HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */if (s == NULL) {s = (struct my_struct*)malloc(sizeof *s);s->id = user_id;HASH_ADD_INT(users, id, s);  /* id is the key field */}strcpy(s->name, name);
}struct my_struct *find_user(int user_id)
{struct my_struct *s;HASH_FIND_INT(users, &user_id, s);  /* s: output pointer */return s;
}void delete_user(struct my_struct *user)
{HASH_DEL(users, user);  /* user: pointer to deletee */free(user);
}void delete_all()
{struct my_struct *current_user;struct my_struct *tmp;HASH_ITER(hh, users, current_user, tmp) {HASH_DEL(users, current_user);  /* delete it (users advances to next) */free(current_user);             /* free it */}
}void print_users()
{struct my_struct *s;for (s = users; s != NULL; s = (struct my_struct*)(s->hh.next)) {printf("user id %d: name %s\n", s->id, s->name);}
}int by_name(const struct my_struct *a, const struct my_struct *b)
{return strcmp(a->name, b->name);
}int by_id(const struct my_struct *a, const struct my_struct *b)
{return (a->id - b->id);
}const char *getl(const char *prompt)
{static char buf[21];char *p;printf("%s? ", prompt); fflush(stdout);p = fgets(buf, sizeof(buf), stdin);if (p == NULL || (p = strchr(buf, '\n')) == NULL) {puts("Invalid input!");exit(EXIT_FAILURE);}*p = '\0';return buf;
}int main()
{int id = 1;int running = 1;struct my_struct *s;int temp;while (running) {printf(" 1. add user\n");printf(" 2. add or rename user by id\n");printf(" 3. find user\n");printf(" 4. delete user\n");printf(" 5. delete all users\n");printf(" 6. sort items by name\n");printf(" 7. sort items by id\n");printf(" 8. print users\n");printf(" 9. count users\n");printf("10. quit\n");switch (atoi(getl("Command"))) {case 1:add_user(id++, getl("Name (20 char max)"));break;case 2:temp = atoi(getl("ID"));add_user(temp, getl("Name (20 char max)"));break;case 3:s = find_user(atoi(getl("ID to find")));printf("user: %s\n", s ? s->name : "unknown");break;case 4:s = find_user(atoi(getl("ID to delete")));if (s) {delete_user(s);} else {printf("id unknown\n");}break;case 5:delete_all();break;case 6:HASH_SORT(users, by_name);break;case 7:HASH_SORT(users, by_id);break;case 8:print_users();break;case 9:temp = HASH_COUNT(users);printf("there are %d users\n", temp);break;case 10:running = 0;break;}}delete_all();  /* free any structures */return 0;
}

鍵的使用

如果是字符串當鍵，有兩種，一種是char * ，使用XXX_XXX_KETPTR，兩一種是char [] ,比如char name[10]，使用XXX_XXX_STR
如果指針自己是鍵，使用XXX_XXX_PTR，如果指針指向的是鍵，比如char *，char *name = “aaa”，aaa作為鍵，則使用XXX_XXX_KEYPTR
如果是整數，使用XXX_XXX_INT
鍵可是是任何數據類型，任何數據類型可以使用通用宏HASH_ADD和HASH_FIND