簡單好用的hash表-----uthash

轉自：http://blog.csdn.net/devilcash/article/details/7230733

在軟體開發中，不可不免的會使用到hash表，hash表的優點這裡就不說了，以下介紹一個hash表的C實作，

uthash是用宏實作的，使用的時候非常友善，隻用包含uthash.h即可。

Uthash的三個資料結構：

1. typedef struct UT_hash_bucket {

struct UT_hash_handle *hh_head;

unsigned count;

unsigned expand_mult;

} UT_hash_bucket;

UT_hash_bucket作用提供根據hash進行索引。

2.typedef struct UT_hash_table {

UT_hash_bucket *buckets;

unsigned num_buckets, log2_num_buckets;

unsigned num_items;

struct UT_hash_handle *tail; /* tail hh in app order, for fast append */

ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */

unsigned ideal_chain_maxlen;

unsigned nonideal_items;

unsigned ineff_expands, noexpand;

uint32_t signature; /* used only to find hash tables in external analysis */

#ifdef HASH_BLOOM

uint32_t bloom_sig; /* used only to test bloom exists in external analysis */

uint8_t *bloom_bv;

char bloom_nbits;

#endif

} UT_hash_table;

UT_hash_table可以看做hash表的表頭。

3. typedef struct UT_hash_handle {

struct UT_hash_table *tbl;

void *prev; /* prev element in app order */

void *next; /* next element in app order */

struct UT_hash_handle *hh_prev; /* previous hh in bucket order */

struct UT_hash_handle *hh_next; /* next hh in bucket order */

void *key; /* ptr to enclosing struct's key */

unsigned keylen; /* enclosing struct's key len */

unsigned hashv; /* result of hash-fcn(key) */

} UT_hash_handle;

UT_hash_handle，使用者自定義資料必須包含的結構。

三種資料結構的關系如下：

說明：

每一個節點（使用者自定義的）必須包含一個UT_hash_handle hh

key：使用者自定義，可以是int， string和指針。

hh_prev： 指向前一個UT_hash_handle

hh_next： 指向下一個UT_hash_handle

hashv：根據key計算出的hash值

prev： 指向前一個資料節點（Hash沖突時）

next： 指向下一個資料節點（Hash沖突時）

hho： 資料節點中hh于使用者節點首位址的差。

1. #include "uthash.h"
2. #include <stdlib.h> /* malloc */
3. #include <stdio.h> /* printf */
4. #include <time.h>
5. typedef struct example_user_t {
6. int id;
7. int cookie;
8. UT_hash_handle hh;
9. } example_user_t;
10. int main(int argc,char *argv[]) {
11. int i;
12. example_user_t *user, *users=NULL;
13. srand((unsigned int)time(NULL));
14. /* create elements */
15. for(i=0;i<10;i++) {
16. if ( (user = (example_user_t*)malloc(sizeof(example_user_t))) == NULL) exit(-1);
17. user->id = rand()%100;
18. user->cookie = i*i;
19. HASH_ADD_INT(users,id,user);
20. }
21. for(user=users; user != NULL; user=(example_user_t*)(user->hh.next)) {
22. printf("user %d, cookie %d\n", user->id, user->cookie);
24. return 0;