當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

开源库uthash第一弹uthash.h

發布時間：2023/12/14 编程问答 33 豆豆

生活随笔收集整理的這篇文章主要介紹了开源库uthash第一弹uthash.h 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

一、簡介
- 1.1 uthash介紹
- 1.2 uthash能做什么
- 1.3 uthash效率
- 1.4 源碼獲取
二、簡單使用
- 2.1 定義hash數據結構
- 2.2 從hash表查找item
- 2.3 向hash表添加item
- 2.4 從hash刪除item
三、詳細介紹
- 3.1 常用操作
- - 3.1.1 聲明hash表
  - 3.1.2 添加item
  - 3.1.3 替換item
  - 3.1.4 查找item
  - 3.1.5 刪除item
  - 3.1.6 統計item
  - 3.1.7 迭代hash表
  - 3.1.8 排序hash表
  - 3.1.9 一個完整的實例
- 3.2 標準key類型
- - 3.2.1 整型key
  - 3.2.2 字符串key
  - 3.2.3 指針key
  - 3.2.4 結構體key
- 3.3 高級用法
- - 3.3.1 組合keys
  - 3.3.2 多層次hash表
  - 3.3.3 多個hash表包含相同的item
  - 3.3.4 每個item有多個key
  - 3.3.5 插入有序的hash表
  - 3.3.6 多個排序需求
  - 3.3.7 Bloom過濾器
  - 3.3.8 篩選SELECT
  - 3.3.9 指定備用key比較函數
  - 3.3.10 內置hash函數
四、附錄宏定義快速查詢表
- Convenience macros
- General macros

一、簡介

[外鏈圖片轉存失敗(img-27kNHnPB-1565700105635)(https://note.youdao.com/yws/api/personal/file/8890D964F4D7432E98496BC35E03362A?method=download&shareKey=65db05cc5d9acbc5b23a3f8a176164e0)]

1.1 uthash介紹

uthash是C的比較優秀的開源代碼，它實現了常見的hash操作函數，例如查找、插入、刪除等待。該套開源代碼采用宏的方式實現hash函數的相關功能，支持C語言的任意數據結構最為key值，甚至可以采用多個值作為key，無論是自定義的struct還是基本數據類型，需要注意的是不同類型的key其操作接口方式略有不通。官方原文說明如下：

Any C structure can be stored in a hash table using uthash. Just add a UT_hash_handle to the structure and choose one or more fields in your structure to act as the key. Then use these macros to store, retrieve or delete items from the hash table.

使用uthash代碼時只需要包含頭文件"uthash.h"即可。由于該代碼采用宏的方式實現，所有的實現代碼都在uthash.h文件中，因此只需要在自己的代碼中包含該頭文件即可。

1.2 uthash能做什么

通過uthash軟件，支持對hash表的item進行如下操作：

添加/替換（add/replace）
查找（find）
刪除（delete）
統計（count）
迭代器（iterate）
排序（sort）

1.3 uthash效率

uthash的插入、查找、刪除的操作時間都是常量，當然這個常量的值受到key以及所選擇的hash函數的影響。

uthash共提供了7種函數函數，一般情況下選擇默認的即可。如果對效率要求特別高時，可以再根據自己的需求選擇適合自己的hash函數。

1.4 源碼獲取

官方GitHub地址是：

https://github.com/troydhanson/uthash

uthash的英文使用文檔介紹可從下面網址獲得：

http://troydhanson.github.io/uthash/
http://troydhanson.github.io/uthash/userguide.html

接下來介紹uthash的使用，大部分都是來自于如上鏈接的翻譯，部分加入了自己使用過程中的總結。

英語能力有限，翻譯不對的地方多多諒解，也可通過konishi5202@163.com聯系我。

二、簡單使用

2.1 定義hash數據結構

在自己的數據結構中添加UT_hash_handle的支持：

#include "uthash.h"struct my_struct {int id; /* we'll use this field as the key */char name[10];UT_hash_handle hh; /* makes this structure hashable */ };struct my_struct *g_users = NULL;

id是鍵（key）；
name是值（value），即自己要保存的數據域，這里可以根據自己的需要讓它變成結構體指針或者其他類型都可以；
hh是內部使用的hash處理句柄，在使用過程中，只需要在結構體中定義一個UT_hash_handle類型的變量即可，不需要為該句柄變量賦值，但必須在該結構體中定義該變量；
Uthash所實現的hash表中可以提供類似于雙向鏈表的操作，可以通過結構體成員hh的hh.prev和hh.next獲取當前節點的上一個節點或者下一個節點。

注意：在uthash中，當您的結構添加到hash表中時，并不會被移動或拷貝到其他位置。這意味著在程序運行過程中，無論是對hash表進行添加或刪除操作，都可以保證您數據結構的安全性。

2.2 從hash表查找item

struct my_struct *find_user(int user_id) {struct my_struct *s = NULL;HASH_FIND_INT(g_users, &user_id, s);return s; }

2.3 向hash表添加item

void add_user(struct my_struct *s) {HASH_ADD_INT(g_users, id, s ); }

2.4 從hash刪除item

void delete_user(struct my_struct *user) {HASH_DEL(g_users, user); }

在實際操作時，需要特別注意以下三點：

與任何hash表一樣，每個item都必須有唯一的key，因此uthash也要求key具有唯一性；
插入時，先查找，當鍵不在當前的hash表中時再進行插入，以確保鍵的唯一性；
需調用插入接口函數時需要明確告訴接口函數，自己定義的鍵變量的名字是什么。

三、詳細介紹

3.1 常用操作

基于第二章定義的數據結構進行介紹：

#include "uthash.h"struct my_struct {int id; /* we'll use this field as the key */char name[10];UT_hash_handle hh; /* makes this structure hashable */ };

3.1.1 聲明hash表

必須將你的結構體指針初始化為空指針：

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

3.1.2 添加item

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

一旦結構的item添加到了hash表，就不要試圖去修改對應item的key值，除非你已經把它從hash表刪除。

如果我們想將g_users的全局鏈表暴露給應用者來制定，從而可以在一個應用中使用多個鏈表，那需要注意正確的使用是采用二級指針（因為宏修改的是指針本身，而不僅僅是它所指向的內容）：

void add_user(struct my_struct **users, int user_id, char *name) {...HASH_ADD_INT( *users, id, s ); }

3.1.3 替換item

HASH_REPLACE宏等價于HASH_ADD宏，只是它們首先嘗試查找和刪除項。如果它發現并刪除一個項，它還將返回該項指針作為輸出參數。

3.1.4 查找item

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

中間的參數是指向key的指針。

3.1.5 刪除item

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

g_users是hash表，user指向用戶自己的結構體。

注意：uthash永遠不會去釋放使用者的結構體。HASH_DEL只是從hash表中刪除節點，但并不會幫使用者釋放結構體所占用的內存。

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

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

如果你僅僅想刪除hash鏈表中的所有item節點，而不對item節點所占內存進行釋放（或者不需要進行釋放），則可以使用如下宏：

HASH_CLEAR(hh, g_users);

需要注意：HASH_CLEAR宏不會釋放使用者結構體，并將hash表頭（這里是g_users）設置為NULL。

3.1.6 統計item

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

當hash表g_users為NULL時，將得到0。

3.1.7 迭代hash表

你可以通過hh.next指針遍歷hash表中所有items。

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);} }

如果要循環刪除item和釋放結構體的話，上面的例子并不安全（因為s是臨時變量，每次遍歷都會改變）。當然，你可以通過定義一個臨時變量用于保存s->hh.next取到的item。由于這種情況比較常見，uthash作者定義了一個HASH_ITER宏來簡化這種情況的使用：

struct my_struct *s, *tmp; HASH_ITER(hh, g_users, s, tmp) {printf("user id %d: name %s\n", s->id, s->name);/* ... it is safe to delete and free s here */ }

3.1.8 排序hash表

默認情況下，hash表的順序與你插入的順序是一致的。你可以通過HASH_SORT宏對整個hash表進行排序：

HASH_SORT(g_users, name_sort);

name_sort是你自己提供的比較算法。他必須接受兩個items作為參數，且返回值為int，返回值規則與標準C的strcmp和qsort一致：小于時返回負數，相等返回0，大于則返回正數。

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 name_sort(struct my_struct *a, struct my_struct *b) {return strcmp(a->name,b->name); }int id_sort(struct my_struct *a, struct my_struct *b) {return (a->id - b->id); }void sort_by_name() {HASH_SORT(users, name_sort); }void sort_by_id() {HASH_SORT(users, id_sort); }

3.1.9 一個完整的實例

下面是一個使用uthash.h的完整實例，你可以這樣使用（請將example.c和uthash.h放在同一個位置）：

cc -o example example.c ./example

接下來是完整的源碼：

// 詳見官方代碼tests/example.c #include <stdio.h> /* gets */ #include <stdlib.h> /* atoi, malloc */ #include <string.h> /* strcpy */ #include "uthash.h"struct my_struct {int id; /* key */char name[10];UT_hash_handle hh; /* makes this structure hashable */ };struct my_struct *users = NULL;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); }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, *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 name_sort(struct my_struct *a, struct my_struct *b) {return strcmp(a->name,b->name); }int id_sort(struct my_struct *a, struct my_struct *b) {return (a->id - b->id); }void sort_by_name() {HASH_SORT(users, name_sort); }void sort_by_id() {HASH_SORT(users, id_sort); }int main(int argc, char *argv[]) {char in[10];int id=1, running=1;struct my_struct *s;unsigned num_users;while (running) {printf(" 1. add user\n");printf(" 2. add/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");gets(in);switch(atoi(in)) {case 1:printf("name?\n");add_user(id++, gets(in));break;case 2:printf("id?\n");gets(in); id = atoi(in);printf("name?\n");add_user(id, gets(in));break;case 3:printf("id?\n");s = find_user(atoi(gets(in)));printf("user: %s\n", s ? s->name : "unknown");break;case 4:printf("id?\n");s = find_user(atoi(gets(in)));if (s) delete_user(s);else printf("id unknown\n");break;case 5:delete_all();break;case 6:sort_by_name();break;case 7:sort_by_id();break;case 8:print_users();break;case 9:num_users=HASH_COUNT(users);printf("there are %u users\n", num_users);break;case 10:running=0;break;}}delete_all(); /* free any structures */return 0; }

3.2 標準key類型

本節介紹如何在不同類型的key下使用uthash。你可以使用的key類型包括：integers、strings、pointers、structures等。

注意：你可以使用float或double作為key，但由于精度的問題，uthash可能將兩個非常相近的兩個key認為是同一個值。

3.2.1 整型key

當你的key是整型時，可以直接使用HASH_ADD_INT、HASH_FIND_INT操作，HASH_DELETE與HASH_SORT對所有類型key都是一樣的。

3.2.2 字符串key

如果您定義的結構體key的類型是string，那么使用的方法依賴于你定義key的方法：指針的方式（char *）還是數組的方式（char a[10]）。這個差異是非常重要的。當你的結構體使用的是指針方式，那么你應當使用HASH_ADD_KEYPTR方法；當你使用的數組方式，則需要使用HASH_ADD_STR方法。

實際上數組方式的char [10]，key是存儲在結構體內部的；而指針方式的char *，key是存儲在結構體外部的。因此char [10]應該使用HASH_ADD_STR，而char *應該使用HASH_ADD_KEYPTR。

下面是一個數組形式的hash實例（對應tests/test15.c）：

#include <string.h> /* strcpy */ #include <stdlib.h> /* malloc */ #include <stdio.h> /* printf */ #include "uthash.h"struct my_struct {char name[10]; /* key (string is WITHIN the structure) */int id;UT_hash_handle hh; /* makes this structure hashable */ };int main(int argc, char *argv[]) {const char *names[] = { "joe", "bob", "betty", NULL };struct my_struct *s, *tmp, *users = NULL;for (int i = 0; names[i]; ++i) {s = (struct my_struct *)malloc(sizeof *s);strcpy(s->name, names[i]);s->id = i;HASH_ADD_STR( users, name, s );}HASH_FIND_STR( users, "betty", s);if (s) printf("betty's id is %d\n", s->id);/* free the hash table contents */HASH_ITER(hh, users, s, tmp) {HASH_DEL(users, s);free(s);}return 0; }

編譯執行，輸入結構：

betty's id is 2

若將上面實例修改為指針方式：

#include <string.h> /* strcpy */ #include <stdlib.h> /* malloc */ #include <stdio.h> /* printf */ #include "uthash.h"struct my_struct {const char *name; /* key */int id;UT_hash_handle hh; /* makes this structure hashable */ };int main(int argc, char *argv[]) {const char *names[] = { "joe", "bob", "betty", NULL };struct my_struct *s, *tmp, *users = NULL;for (int i = 0; names[i]; ++i) {s = (struct my_struct *)malloc(sizeof *s);s->name = names[i];s->id = i;HASH_ADD_KEYPTR( hh, users, s->name, strlen(s->name), s );}HASH_FIND_STR( users, "betty", s);if (s) printf("betty's id is %d\n", s->id);/* free the hash table contents */HASH_ITER(hh, users, s, tmp) {HASH_DEL(users, s);free(s);}return 0; }

詳見實例：tests/test40.c

3.2.3 指針key

你可以使用指針（地址）作為key，也就是說指針（地址）本身也可以作為key來使用。也對應HASH_ADD_KEYPTR相關方法。下面是一個實例：

#include <stdio.h> #include <stdlib.h> #include "uthash.h"typedef struct {void *key;int i;UT_hash_handle hh; } el_t;el_t *hash = NULL; char *someaddr = NULL;int main() {el_t *d;el_t *e = (el_t *)malloc(sizeof *e);if (!e) return -1;e->key = (void*)someaddr;e->i = 1;HASH_ADD_PTR(hash,key,e);HASH_FIND_PTR(hash, &someaddr, d);if (d) printf("found\n");/* release memory */HASH_DEL(hash,e);free(e);return 0; }

詳見tests/test57.c。

3.2.4 結構體key

你也可以指定你的key為自定義的結構體，這對于uthash來說，只是一些列連續的bytes值。因此，即使是嵌套的結構，也可以作為key來使用。我們將使用通用的HASH_ADD和HASH_FIND來使用hash。下面是使用結構體的一個實例：

#include <stdlib.h> #include <stdio.h> #include "uthash.h"typedef struct {char a;int b; } record_key_t;typedef struct {record_key_t key;/* ... other data ... */UT_hash_handle hh; } record_t;int main(int argc, char *argv[]) {record_t l, *p, *r, *tmp, *records = NULL;r = (record_t *)malloc(sizeof *r);memset(r, 0, sizeof *r);r->key.a = 'a';r->key.b = 1;HASH_ADD(hh, records, key, sizeof(record_key_t), r);memset(&l, 0, sizeof(record_t));l.key.a = 'a';l.key.b = 1;HASH_FIND(hh, records, &l.key, sizeof(record_key_t), p);if (p) printf("found %c %d\n", p->key.a, p->key.b);HASH_ITER(hh, records, p, tmp) {HASH_DEL(records, p);free(p);}return 0; }

3.3 高級用法

3.3.1 組合keys

你可以使用結構體中連續域的成員作為組合key。下面是multi-field key的例子：

#include <stdlib.h> /* malloc */ #include <stddef.h> /* offsetof */ #include <stdio.h> /* printf */ #include <string.h> /* memset */ #include "uthash.h"#define UTF32 1typedef struct {UT_hash_handle hh;int len;char encoding; /* these two fields */int text[]; /* comprise the key */ } msg_t;typedef struct {char encoding;int text[]; } lookup_key_t;int main(int argc, char *argv[]) {unsigned keylen;msg_t *msg, *tmp, *msgs = NULL;lookup_key_t *lookup_key;int beijing[] = {0x5317, 0x4eac}; /* UTF-32LE for 北京 *//* allocate and initialize our structure */msg = (msg_t *)malloc( sizeof(msg_t) + sizeof(beijing) );memset(msg, 0, sizeof(msg_t)+sizeof(beijing)); /* zero fill */msg->len = sizeof(beijing);msg->encoding = UTF32;memcpy(msg->text, beijing, sizeof(beijing));/* calculate the key length including padding, using formula */keylen = offsetof(msg_t, text) /* offset of last key field */+ sizeof(beijing) /* size of last key field */- offsetof(msg_t, encoding); /* offset of first key field *//* add our structure to the hash table */HASH_ADD( hh, msgs, encoding, keylen, msg);/* look it up to prove that it worked :-) */msg=NULL;lookup_key = (lookup_key_t *)malloc(sizeof(*lookup_key) + sizeof(beijing));memset(lookup_key, 0, sizeof(*lookup_key) + sizeof(beijing));lookup_key->encoding = UTF32;memcpy(lookup_key->text, beijing, sizeof(beijing));HASH_FIND( hh, msgs, &lookup_key->encoding, keylen, msg );if (msg) printf("found \n");free(lookup_key);HASH_ITER(hh, msgs, msg, tmp) {HASH_DEL(msgs, msg);free(msg);}return 0; }

如果使用多字段key，編譯器會填充相鄰字段（通過在他們之間插入未使用的空間），以滿足每個字段的對其要求。例如，一個結構包含一個char后面跟一個int，通常在char之后插入3個“浪費”的填充字節，以便使int字段是開始于4字節對齊的地址。

計算組合key的長度方法：如前面所述，在使用組合（多字段）key時，必須包含編譯器為對齊目的添加的中間填充結構。那么key就不是結構體所顯示聲明的長度了。一個簡單的計算組合key長度的方法是使用<stddef.h>中的offsetof宏：

key length = offsetof(last_key_field)+ sizeof(last_key_field)- offsetof(first_key_field)

在處理組合key時，必須在HASH_ADD和HASH_FIND之前對結構體進行0填充。

3.3.2 多層次hash表

多層次hash表意味著hash表的每個元素都可能包含自己的輔助hash表，這可以是任意數量的級別。下面是多級hash表的偽代碼：

$items{bob}{age} = 37

上面的含義是有一個名為items的hash表，包含bob元素，bob元素也是一個hash表，包含age元素，并且age元素的值為37。下面是一個多層次hash表的實例：

#include <stdio.h> #include <string.h> #include <stdlib.h> #include "uthash.h"/* hash of hashes */ typedef struct item {char name[10];struct item *sub;int val;UT_hash_handle hh; } item_t;item_t *items=NULL;int main(int argc, char *argvp[]) {item_t *item1, *item2, *tmp1, *tmp2;/* make initial element */item_t *i = malloc(sizeof(*i));strcpy(i->name, "bob");i->sub = NULL;i->val = 0;HASH_ADD_STR(items, name, i);/* add a sub hash table off this element */item_t *s = malloc(sizeof(*s));strcpy(s->name, "age");s->sub = NULL;s->val = 37;HASH_ADD_STR(i->sub, name, s);/* iterate over hash elements */HASH_ITER(hh, items, item1, tmp1) {HASH_ITER(hh, item1->sub, item2, tmp2) {printf("$items{%s}{%s} = %d\n", item1->name, item2->name, item2->val);}}/* clean up both hash tables */HASH_ITER(hh, items, item1, tmp1) {HASH_ITER(hh, item1->sub, item2, tmp2) {HASH_DEL(item1->sub, item2);free(item2);}HASH_DEL(items, item1);free(item1);}return 0;

3.3.3 多個hash表包含相同的item

一個結構體item對象，可以被添加到多個hash表中。比如下面的情況：

每個hash表使用不同的key；
每個hash表使用自己的排序算法；
也可以通過多個hash表來對所有item進行分組。

這種情況下，你只需要在你的結構體里面，為每個hash表定義UT_hash_handle字段即可：

UT_hash_handle hh1, hh2;

3.3.4 每個item有多個key

你可能需要用到這樣的組合hash表：每個item都有多個key，每個key對應到不同的hash表。實現方法就是為每個不同的key添加對應的UT_hash_handle域，每個UT_hash_handle對應不同的hash表：

struct my_struct {int id; /* first key */char username[10]; /* second key */UT_hash_handle hh1; /* handle for first hash table */UT_hash_handle hh2; /* handle for second hash table */ };struct my_struct *users_by_id = NULL, *users_by_name = NULL, *s;int i;char *name;s = malloc(sizeof(struct my_struct));s->id = 1;strcpy(s->username, "thanson");/* add the structure to both hash tables */HASH_ADD(hh1, users_by_id, id, sizeof(int), s);HASH_ADD(hh2, users_by_name, username, strlen(s->username), s);/* find user by ID in the "users_by_id" hash table */i=1;HASH_FIND(hh1, users_by_id, &i, sizeof(int), s);if (s) printf("found id %d: %s\n", i, s->username);/* find user by username in the "users_by_name" hash table */name = "thanson";HASH_FIND(hh2, users_by_name, name, strlen(name), s);if (s) printf("found user %s: %d\n", name, s->id);

當然，也可以是兩個hash表使用相同的key，比如上面的hh1和hh2都使用id作為key。

3.3.5 插入有序的hash表

如果你想維護一個有序的hash表，你有兩個選擇：

可以使用HASH_SRT()宏，它將對未排序的元素進行排序，其復雜度是O（n log(n)）。如果你是用HASH_SRT()操作隨機順序hash表，這是最好的策略；但如果需要在插入項之間使列表處于有序狀態，則需要在每次插入操作之后使用HASH_SRT()，其復雜度是O(n^2 log(n))。
使用按順序添加和替換宏HASH_ADD_INORDER*宏，它們的工作原理與HASH_ADD*類似，只是多了一個額外的比較函數，其復雜度為O(n)。

int name_sort(struct my_struct *a, struct my_struct *b) {return strcmp(a->name,b->name); } HASH_ADD_KEYPTR_INORDER(hh, items, &item->name, strlen(item->name), item, name_sort);

3.3.6 多個排序需求

基于一個struct結構可以保存在多個hash表（3.3.4），那么針對相同的struct結構對象，可以擁有完全不同的排序方法。比如3.3.4節的例子，可以分別按照id或name進行排序：

int sort_by_id(struct my_struct *a, struct my_struct *b) {if (a->id == b->id) return 0;return (a->id < b->id) ? -1 : 1; } int sort_by_name(struct my_struct *a, struct my_struct *b) {return strcmp(a->username,b->username); } HASH_SRT(hh1, users_by_id, sort_by_id); HASH_SRT(hh2, users_by_name, sort_by_name);

3.3.7 Bloom過濾器

默認情況下，Bloom過濾器是關閉的，可以通過在編譯的時候指定-DHASH_BLOOM=n即可打開Bloom過濾器：

-DHASH_BLOOM=27

其取值范圍為0~32，它決定了過濾器使用的內存大小。內存使用的越多，過濾器計算將會更加準確，效率也會更高，不過也需要根據你自身系統資源來確定。

nBloom filter size(per hash table)

16	8K bytes
20	128K bytes
24	2M bytes
28	32M bytes
32	512M bytes

Bloom過濾器只是一個性能特性，它不會影像任何hash表操作方式的結果。你可以在你的系統中，通過設置不同的值，進行測試對比性能提升的效率。

3.3.8 篩選SELECT

本操作將篩選滿足條件的源hash表元素插入到目標hash表中，這不會從源hash表中刪除任何元素，而是兩個 hash表中有相同的結構體對象。因此，要滿足此操作，struct結構體中至少應該有兩個或多個hash句柄UT_hash_handle：

user_t *users=NULL, *admins=NULL; /* two hash tables */ typedef struct {int id;UT_hash_handle hh; /* handle for users hash */UT_hash_handle ah; /* handle for admins hash */ } user_t;

那么我們想篩選id小于1024的用戶到admins鏈表：

#define is_admin(x) (((user_t*)x)->id < 1024) HASH_SELECT(ah,admins,hh,users,is_admin);

當我們提供的篩選條件永遠為true，則HASH_SELECT本質上就是將兩個hash表進行合并。有關HASH_SELECT實例詳見tests/test36.c

3.3.9 指定備用key比較函數

當你調用HASH_FIND(hh, head, intfiled, sizeof(int), out)時，uthash將首先調用HASH_FUNCTION(intfiled, sizeof(int), hashvalue)來確定搜索的bucket b；然后，對于bucket b的每個元素elt，uthash將計算：

elt->hh.hashv == hashvalue && elt.hh.keylen == sizeof(int) && HASH_KEYCMP(intfield, elt->hh.key, sizeof(int)) == 0

在找到匹配的elt時，HASH_KEYCMP應該返回0，否則就表示要繼續進行搜索。

默認情況下，uthash定義memcmp為HASH_KEYCMP宏。針對不同的平臺，你可以提供你自己的memcmp方法實現：

#undef HASH_KEYCMP #define HASH_KEYCMP(a,b,len) bcmp(a,b,len)

需要自己提供key比較方法的另外一種情況是：你所定義的key無法通過通用的比較方法實現，這種情況下，你還需要提供你自己的HASH_FUNCTION：

struct Key {short s;/* 2 bytes of padding */float f; }; /* do not compare the padding bytes; do not use memcmp on floats */ unsigned key_hash(struct Key *s) { return s + (unsigned)f; } bool key_equal(struct Key *a, struct Key *b) { return a.s == b.s && a.f == b.f; }#define HASH_FUNCTION(s,len,hashv) (hashv) = key_hash((struct Key *)s) #define HASH_KEYCMP(a,b,len) (!key_equal((struct Key *)a, (struct Key *)b))

需要自己提供key比較函數的另一種情況是：有更高的性能要求或者更高的正確性要求！在對bucket線性搜索過程中，uthash總是比較32位的hashv，并且只在hashv相等時才調用HASH_KEYCMP。也就是說每次成功的查詢至少有一次調用HASH_KEYCMP。在一個好的hash函數中，我們希望hasv比較僅在40億次中產生一次“false positive”等式，因此，我們希望HASH_KEYCMP在大多數情況下生成0。如果我們期望許多成功的發現，并且我們的應用不關心偶然出現“false positive”，我們可以替換一個no-op比較函數：

#undef HASH_KEYCMP #define HASH_KEYCMP(a,b,len) 0 /* occasionally wrong, but very fast */

注意：全局均衡比較函數HASH_KEYCMP與作為參數傳遞給HASH_ADD_INORDER的小于比較函數沒有任何關系。

3.3.10 內置hash函數

在uthash內部，hash函數會自動將key轉換為bucket號以便于Jenkins使用，使用者可以完全不用關心。

你可以通過在編譯時指定-DHASH_FUNCTION=HASH_xyz來使用另外的hash函數。xyz是下面表中的一種：

cc -DHASH_FUNCTION=HASH_BER -o program program.c SymbolName

JEN	Jenkins(default)
BER	Bernstein
SAX	Shift-Add-Xor
OAT	One-at-a-time
FNV	Fowler/Noll/Vo
SFH	Paul Hsieh
MUR	MurmurHash V3

四、附錄宏定義快速查詢表

Convenience macros

為了您能正常的使用Convenience macros，必須保證如下兩點：

您結構體的UT_hash_handle成員名必須是hh；
您結構體的key字段類型必須是int、char []或pointer類型。

macroarguments

HASH_ADD_INT	(head, keyfield_name, item_ptr)
HASH_REPLACE_INT	(head, keyfiled_name, item_ptr,replaced_item_ptr)
HASH_FIND_INT	(head, key_ptr, item_ptr)
HASH_ADD_STR	(head, keyfield_name, item_ptr)
HASH_REPLACE_STR	(head,keyfield_name, item_ptr, replaced_item_ptr)
HASH_FIND_STR	(head, key_ptr, item_ptr)
HASH_ADD_PTR	(head, keyfield_name, item_ptr)
HASH_REPLACE_PTR	(head, keyfield_name, item_ptr, replaced_item_ptr)
HASH_FIND_PTR	(head, key_ptr, item_ptr)
HASH_DEL	(head, item_ptr)
HASH_SORT	(head, cmp)
HASH_COUNT	(head)

General macros

當您結構的UT_hash_handle成員名字不是hh，或者結構的key類型不是int、char []或者pointer類型時，可以使用下面通用的宏：