提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

uthash用户手册(一)

用户手册
2023-09-27 14:26:51 时间

一种在C中的哈希

本手册位C程序源编写。因为你正在阅读此手册，你可能了解哈希被用于使用键来查找项目。在脚本语言中，哈希或者"字典"被一直使用。哈希在C语言子树中不存在。此软件为C结构体提供一个哈希表。

它能做什么？

此软件在一个哈希表中对项目支持这些操作。

  1. 添加/替换
  2. 查找
  3. 删除
  4. 计数
  5. 迭代
  6. 排序

它快吗？

添加、查找和删除通常是常数时间操作。这受到你的键域和这个哈希函数的影响。这种哈希目标是简约并且高效。它大约1000行C代码。因为以宏实现了它，所以它自动内联。只要这个哈希函数合适你的键，它是快速的。你可以使用默认的哈希函数，或者简单地比较性能并且在某些其它内建哈希函数中选择。

它是一个库吗？

不是地，它仅是单个头文件：uthash.h。所有你需要做地事情是复制这个头文件到你的项目，并且'#include "uthash.h"'。因为uthash只是一个头文件，所以没有要链接的库代码。

C/C++和平台

此软件可以在C和C++平台中被使用。它在以下系统上已经被测试了：

  1. Linux
  2. 使用了Visual Stdio 2008和2010的Windows
  3. Solaris
  4. OpenBSD
  5. FreeBSD
  6. Android 

测试套件

要运行测试套件，进入tests目录。接着：

在Unix平台，运行make

在Windows，运行"do_tests_win32.cmd"批处理文件。(如果你的Visual Stdio不是被安装在一个标准位置，你可能编辑这个批处理文件)。

BSD授权

此软件在修改的BSD证书下可获取。它是免费和开源的。

下载uthash

以下链接GitHub - troydhanson/uthash: C macros for hash tables and more 来复制uthash或者获取一个zip文件。

获取帮助

请使用 uthash Google Group 来请教问题。你可以发送邮件到 uthash@googlegroups.com。

包含的提取文件

uthash带了三个"extras"。这些文件提供了列表、动态数组和字符串：

  1. utlish：为C结构体提供了链表宏。
  2. utarray.h：使用宏实现了动态数组。
  3. utstring.h：实现了一个基本的动态字符串。

你的结构体

在uthash中，一个哈希表是由结构体组成。每个结构体代表一个键-值关联。一个或多个结构体字段组成这个键。结构体指针自身是这个值。

定义一个可以被哈希的结构体

#include "uthash.h"

struct my_struct {
    int id;                    /* 键 */
    char name[10];
    UT_hash_handle hh;         /* 使得这个结构体可哈希 */
};

 注意：在uthash中，当你添加你的结构体到一个哈希表时，它将不被移动或复制到另一个位置。这意味着在你的程序生命期间，无论你添加它到一个哈希表或者从一个哈希表删除它，你可以使得其它数据结构安全地指向你的结构体。

键

对键字段的数据类型或名称没有限制。这个键也可以组合多个连续字段，有任何名称和数据类型。

任何数据类型，真的吗？

真的，你的键和结构体可以有任何数据类型。不同于用固定原型的函数调用，uthash由宏组成--它们的参数是无类型的--并且因而能够对任何结构体或键有效。

唯一键

然而对于任何哈希，每个项必须有一个唯一键。你的程序必须强制键唯一性。在你添加一个项到这个哈希表前，你必须首先知道(如果怀疑，检查!)这个键还未使用。你可以使用HASH_FIND检查一个键是否在哈希表中已经存在。

哈希句柄

UT_hash_handle字段必须在你的结构体中出现。它用于使得哈希工作的内部记录。它不需要初始化。它可以被命名位任何东西，但你可以通过命名它为hh简化这件事情。这使得你可以使用更简单的"快捷"宏来添加，查找和删除项。

有关内存

开销

哈希句柄在32位系统上消耗每项32个字节，或者在64位系统上每项消耗56个字节。其它开销--这个桶和表--相比下是可忽略的。对于一个哈希表，你可以使用HASH_OVERHEAD来获取开销大小(字节为单位)。见宏参考。

如何发生清理

有人问询uthash如何清理它的内部内存。回答简单：当你从一个哈希表删除最后项，uthash释放与那个哈希表相关联的所有内部内存，并且设置其指针为NULL。

哈希操作

这部分通过示例引入哈希宏。需要更简洁的列表，见宏参考。

快捷 VS 一般宏

uthash宏分为两类。快捷宏能够与整数，指针或字符串键(并且需要你需要你为UT_hash_handle字段选择常规名称hh)。快捷宏比一般宏接收更少的参数，使得它们的用法稍微简单于这些一般类型的键。

一般宏可以用于任何类型的键或者用于多字段键，或者在UT_hash_handle已经被命名为除了hh的其它东西。这些宏接收更多参数并且在返回中提供更高的灵活性。但如果这些快捷宏合适你，使用它们--你的代码将更加可读。

1） 声明哈希

你的哈希必须被声明为一个指向你结构体的NULL初始化的指针。

struct my_struct *users = NULL;    /* 重要！初始化为NULL */

2） 添加项

 分配并且初始化你你认为合适的结构体。唯一对哈希重要的方面是你的键必须被初始化为一个唯一值。接着调用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。最后的参数是一个指向被添加结构体的指针。

等一下...这个参数是一个字段名。

如果你发现id奇怪，它是结构体中一个字段的名称，可以作为一个参数被传递，欢饮来自宏的世界。不要担心；C预处理器展开它为有效的C代码。

在使用中键一定不能被修改

一旦一个结构体已经被添加到了哈希，不要更改它键的值。而是，从哈希删除这项，更改这个键，并且接着再次添加它。

检查唯一性

在以上示例中，我们不检查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);
}

uthash为什么不为你检查唯一性？它为那些不需要它检查的程序节省了哈希查找的开销，例如，其键是由增量，非重复计数器产生的程序。

但如果替换是一个常见操作，使用HASH_REPLACE宏是可能的。在添加这个项前，这个宏首先用相同键查找一个项并且删除它。它也返回一个指向被替换项的指针，所以用户有重写分配其内存的机会。

传递这个哈希指针到函数

在以上示例中，users是一个全局变量，但如果调用者想要传递哈希指针到add_user函数会怎么样？起初，你可能只是作为一个参数传递users，但那将工作不正常。

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

你真的需要传递一个指向这个哈希指针的指针：

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

注意：我们在HASH_ADD中也解引用了。

处理一个指向哈希指针的指针是必要的原因简单：哈希宏修改它。(换句话，它们修改这个指针自身，而不仅它所指向的东西)。

替换项

HASH_REPLACE宏除了它们首先尝试查找并且删除这个项前外，等价于HASH_ADD宏。如果它找到并且删除了一个项，它将也以一个输出参数返回项的指针。

查找项

要在一个哈希中查找一个结构体，你需要它的键。接着调用HASH_FIND。(在这里，我们为类型int的键使用快捷宏HASH_FIND_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。而是分配这个字面值到一个变量，并且传递指向这个变量的指针。

删除项

要从一个哈希删除一个结构体，你必须有指向它的指针。(如果你只有这个键，首先进行一次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是一个指向我们想要从哈希移除的结构体的指针。

uthash不会删除你的结构体

删除一个结构体只是从哈希表移除它--它不释放它。何时释放你结构体体的选择完全取决于你；uthash将不会释放你的结构体。例如，当使用HASH_REPLACE宏时，为了使得让用户取消分配它成为可能，返回一个被替换的输出参数。

删除可以更改这个指针

哈希表指针(它初始指向被添加到这个哈希中的第一个项)可以变化来响应HASH_DEL(例如：如果你删除了在这个哈希表中第一项)。

迭代删除

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_CLEAR(hh, users);

从这之后，列表头(在此，users)将被设置成NULL。

对项计数

可以使用HASH_COUNT获取在哈希表中项数：

对哈希表中项数计数

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

即使列表头是NULL，这有效，在这种情况计数为0。

迭代和排序

通过从头开始并且跟着hh.next指针，你能够循环哈希中项。正确地重写是简单的(通过在释放s前复制s->hh.next到一个临时变量)，但它足够经常地出现，使得一个删除安全的宏HASH_ITER

迭代哈希中所有项

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.prev指针，你可以从任何已知项逆向迭代这个哈希。

删除安全的迭代

在以上示例中，在for循环体中删除和释放s是不安全的，(因为每次循环迭代s是被解引用的)。正确地重写它是简单地(通过在释放它前复制s->hh.next指针到一个临时变量)，但它足够经常的出现，使得一个删除安全的宏HASH_ITER被包含。它扩展到了一个for循环头。这是如何使用它重写上个示例：

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

一个哈希也是一个双向链表。

 由于hh.prev和hh.next字段，在哈希中逆向或正向通过项地迭代是可能地。通过重复地跟着这些指针，可以到达哈希中所有项，因而这个哈希也是一个双链表。

如果你在C++程序中使用uthash，你对for迭代器需要一个额外转换，例如：

s = static_cast<my_struct*>(s->hh.next)

排序

当你跟随hh.next指针时，以"插入"顺序访问哈希中这些项。你可以使用HASH_SORT排序这些项为一个新顺序。

HASH_SORT(users, name_sort);

第二个参数是一个指向一个比较函数的指针。它必须接受两个指针参数(要比较的项)，并且必须返回一个int，根据第一项在第二项前，相同或者在其后，其小于0，0或大于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)
   */
}

在下面name_sort和id_sort是sort函数的两个示例。

排序哈希中的项

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

当在哈希中这些项被排序时，第一项可能变化位置。在以上示例中，在调用HASH_SORT后，users可能指向一个不同的结构体。

一个完整示例

我们将重复所有代码并且用一个main()函数修饰它来形成一个可运行的示例。

如果这些代码放置在一个与uthash.h相同目录中名为example.c的文件中，可以像这样编译和运行它：

cc -o example example.c
./example

安装提示，尝试这个程序。

一个完整程序

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

这个程序包含在发行中tests/example.c中。你可以在那个目录中运行make example简单地编译它。

标准键类型

这部分专门挑了如何使用不同类型地键。你可以使用几乎任何类型地键--整数，字符串，指针，结构体等。

注意：

注意浮点数：你可以使用浮点键。对于测试浮点相等的任何程序都出现相同的警告。换句话，两个浮点数值之间即使最微小差别使得它们完全不同。

整数键

接下来的示例演示了整数键的使用。回顾一下，对带有整数键的结构体使用快捷宏HASH_ADD_INT和HASH_FIND_INT。（诸如HASH_DELETE和HASH_SORT的其它操作对于所有键类型相同）。

字符串键

如果你的结构体有一个字符串键，要使用的操作取决于你的结构体是否指向这个键(char *)或者这个字符串是否驻留在这个结构体中(char a[10])。这个区别是重要的。如我们如下所见，当你的结构体指向一个键(即，这个键自身在这个结构体外)，你需要使用HASH_ADD_KEYPTR。相比较，对一个被包含在你结构体中的字符串键使用HASH_ADD_STR。

注意：

char[] vs char*

在以下第一个示例中，字符串是在结构体中--name是一个char[10]字段。在第二个示例中，键是在结构体之外--name是一个char *。因此第一个示例使用HASH_ADD_STR，而第二个示例使用HASH_ADD_KEYPTR。需要这些宏的信息，见Macro reference。

字符串在结构体中

一个字符串做键的哈希(字符串在结构体中)

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

这个示例包含在发行中test/test15.c。它打印：

betty's id is 2

在结构体中字符串指针

现在，这是一个相同示例，但使用了一个char *键替换char []。

一个以字符串为键的哈希(结构体指向字符串)

#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中。

指针键

你的键可以是一个指针。为了非常明确，者表示指针自身可以是这个键(相比较，如果被指向的东西是这个键，这是一个由HASH_ADD_KEYPTR处理的不同使用情况)。

这是一个简单示例，在其中一个结构体有一个称为key的指针成员。

一个指针键

#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中。注意：此程序结尾从哈希删除了这个元素，(并且在哈希中没有更多元素了，uthash)释放其内部内存。

结构体键

你的键字段可以有任何数据类型。对于uthash，它只是一个字节序列。因而，即使一个嵌套结构体也可以被用作一个键。我们将使用一般宏HASH_ADD和HASH_FIND来演示。

注意：结构体包含填充(用于实现结构体成员对齐要求的被浪费的内部空间)。在添加一个项到这个哈希或者查找一个项前，这些填充字节必须被置零。因而，在设置感兴趣成员前，总是置零整个结构体。以下示例做了这件事，键对memset的两次调用。

一个其是结构体体的键

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

这种用法与以下解释的复合键的用法几乎相同。

注意：一般宏需要UT_hash_handle的名称作为第一个参数被传递(在此，这是hh)。一般宏记录在Macro Reference中。

相关文章