简单好用的hash表-----uthash

在软件开发中，不可不免的会使用到hash表，hash表的优点这里就不说了，以下介绍一个hash表的C实现，

uthash是用宏实现的，使用的时候非常方便，只用包含uthash.h即可。

Uthash的三个数据结构：

typedef struct UT_hash_bucket {

   struct UT_hash_handle *hh_head;

   unsigned count;

   unsigned expand_mult;

} UT_hash_bucket;

UT_hash_bucket作用提供根据hash进行索引。

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表的表头。

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于用户节点首地址的差。

uthash使用代码例子

#include "uthash.h"

#include <stdlib.h>   /* malloc */

#include <stdio.h>    /* printf */

#include <time.h>  

typedef struct example_user_t {

    int id;

    int cookie;

    UT_hash_handle hh;

} example_user_t;  

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

    int i;

    example_user_t *user, *users=NULL;  

    srand((unsigned int)time(NULL));

    /* create elements */

    for(i=;i<;i++) {

        if ( (user = (example_user_t*)malloc(sizeof(example_user_t))) == NULL) exit(-);

        user->id = rand()%;

        user->cookie = i*i;

        HASH_ADD_INT(users,id,user);

    }  

    for(user=users; user != NULL; user=(example_user_t*)(user->hh.next)) {

        printf("user %d, cookie %d\n", user->id, user->cookie);

    }

   return ;

}

巴特西

简单好用的hash表-----uthash

最新文章

热门文章