一、简介

[外链图片转存失败(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的使用，大部分都是来自于如上链接的翻译，部分加入了自己使用过程中的总结。

英语能力有限，翻译不对的地方多多谅解，也可通过[email protected]联系我。

二、简单使用

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 1

typedef 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，它决定了过滤器使用的内存大小。内存使用的越多，过滤器计算将会更加准确，效率也会更高，不过也需要根据你自身系统资源来确定。

n	Bloom 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

Symbol	Name
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类型。

macro	arguments
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类型时，可以使用下面通用的宏：

macro	arguments
HASH_ADD	(hh_name, head, keyfield_name, key_len, item_ptr)
HASH_ADD_BYHASHVALUE	(hh_name, head, keyfield_name, key_len, hashv, item_ptr)
HASH_ADD_KEYPTR	(hh_name, head, key_ptr, key_len, item_ptr)
HASH_ADD_KEYPTR_BYHASHVALUE	(hh_name, head, key_ptr, key_len, hashv, item_ptr)
HASH_ADD_INORDER	(hh_name, head, keyfield_name, key_len, item_ptr, cmp)
HASH_ADD_BYHASHVALUE_INORDER	(hh_name, head, keyfield_name, key_len, hashv, item_ptr, cmp)
HASH_ADD_KEYPTR_INORDER	(hh_name, head, key_ptr, key_len, item_ptr, cmp)
HASH_ADD_KEYPTR_BYHASHVALUE_INORDER	(hh_name, head, key_ptr, key_len, hashv, item_ptr, cmp)
HASH_REPLACE	(hh_name, head, keyfield_name, key_len, item_ptr, replaced_item_ptr)
HASH_REPLACE_BYHASHVALUE	(hh_name, head, keyfield_name, key_len, hashv, item_ptr, replaced_item_ptr)
HASH_REPLACE_INORDER	(hh_name, head, keyfield_name, key_len, item_ptr, replaced_item_ptr, cmp)
HASH_REPLACE_BYHASHVALUE_INORDER	(hh_name, head, keyfield_name, key_len, hashv, item_ptr, replaced_item_ptr, cmp)
HASH_FIND	(hh_name, head, key_ptr, key_len, item_ptr)
HASH_FIND_BYHASHVALUE	(hh_name, head, key_ptr, key_len, hashv, item_ptr)
HASH_DELETE	(hh_name, head, item_ptr)
HASH_VALUE	(key_ptr, key_len, hashv)
HASH_SRT	(hh_name, head, cmp)
HASH_CNT	(hh_name, head)
HASH_CLEAR	(hh_name, head)
HASH_SELECT	(dst_hh_name, dst_head, src_hh_name, src_head, condition)
HASH_ITER	(hh_name, head, item_ptr, tmp_item_ptr)
HASH_OVERHEAD	(hh_name, head)

【参数说明】：

• hh_name：name of the UT_hash_handle field in the structure. Conventionally called hh.
• head：the structure pointer variable which acts as the “head” of the hash. So named because it initially points to the first item that is added to the hash.
• keyfield_name：the name of the key field in the structure. (In the case of a multi-field key, this is the first field of the key). If you’re new to macros, it might seem strange to pass the name of a field as a parameter. See note.
• key_len：the length of the key field in bytes. E.g. for an integer key, this is sizeof(int), while for a string key it’s strlen(key). (For a multi-field key, see this note.)
• key_ptr：for HASH_FIND, this is a pointer to the key to look up in the hash (since it’s a pointer, you can’t directly pass a literal value here). For HASH_ADD_KEYPTR, this is the address of the key of the item being added.
• hashv：the hash value of the provided key. This is an input parameter for the …_BYHASHVALUE macros, and an output parameter for HASH_VALUE. Reusing a cached hash value can be a performance optimization if you’re going to do repeated lookups for the same key.
• item_ptr：pointer to the structure being added, deleted, replaced, or looked up, or the current pointer during iteration. This is an input parameter for the HASH_ADD, HASH_DELETE, and HASH_REPLACE macros, and an output parameter for HASH_FIND and HASH_ITER. (When using HASH_ITER to iterate, tmp_item_ptr is another variable of the same type as item_ptr, used internally).
• replaced_item_ptr：used in HASH_REPLACE macros. This is an output parameter that is set to point to the replaced item (if no item is replaced it is set to NULL).
• cmp：pointer to comparison function which accepts two arguments (pointers to items to compare) and returns an int specifying whether the first item should sort before, equal to, or after the second item (like strcmp).
• condition：a function or macro which accepts a single argument (a void pointer to a structure, which needs to be cast to the appropriate structure type). The function or macro should evaluate to a non-zero value if the structure should be “selected” for addition to the destination hash.

想了解更多有关嵌入式Linux驱动、应用、常用开源库、框架、模式、重构等相关相关的主题内容，请长安下面图片，关注我的公众号（只有技术干货分享，不拉稀摆带！）。
[外链图片转存失败(img-RW5uaGUD-1565700105638)(https://note.youdao.com/yws/api/personal/file/C896F98003CB4B89BC0D38CF42CED1D3?method=download&shareKey=f9732570d98f6d2e5a417c9941e35533)]