【C语言】算法学习·哈希算法全解

#include "uthash.h"

要运行测试套件，请输入tests目录。然后，

• 在 Unix 平台上，运行make

• 在 Windows 上，运行“do_tests_win32.cmd”批处理文件。（如果您的 Visual Studio 安装在非标准位置，您可以编辑批处理文件）。

与任何散列一样，每个项目都必须有一个唯一的键。您的应用程序必须强制执行密钥唯一性。在将项目添加到哈希表之前，您必须首先知道（如果有疑问，请检查！）该密钥尚未使用。您可以使用 . 检查哈希表中是否已存在键HASH_FIND。

散列句柄在 32 位系统上每个项目消耗大约 32 个字节，或在 64 位系统上每个项目消耗 56 个字节。相比之下，其他间接成本——存储桶和桌子——可以忽略不计。您可以使用HASH_OVERHEAD来获取哈希表的开销大小（以字节为单位）。请参阅宏参考。

有人问 uthash 如何清理其内部存储器。答案很简单： 当您从哈希表中删除最后一项时，uthash 会释放与该哈希表关联的所有内部内存，并将其指针设置为 NULL。

uthash 宏分为两类。便利宏可以与整数、指针或字符串键一起使用（并要求您为字段选择常规名称hh）UT_hash_handle。与通用宏相比，便利宏使用的参数更少，这使得它们对这些常见类型的键的使用更加简单。

通用宏可用于任何类型的键，或用于多字段键，或者当.UT_hash_handle被命名为hh. 这些宏接受更多参数并提供更大的灵活性作为回报。但是，如果便利宏满足您的需要，请使用它们——您的代码将更具可读性。

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

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 */
}

将结构添加到散列后，不要更改其键的值。相反，从哈希中删除该项目，更改密钥，然后重新添加它。

在上面的示例中，我们没有检查是否user_id已经是哈希中某个现有项的键。如果您的程序有可能生成重复键，则必须 在将键添加到散列之前明确检查唯一性。如果键已经在散列中，您可以简单地修改散列中的现有结构，而不是添加项。 将具有相同键的两个项目添加到哈希表是错误的。

让我们重写add_user函数来检查 id 是否在哈希中。只有当 id 不存在于散列中时，我们才创建项目并添加它。否则我们只是修改已经存在的结构。

为什么 uthash 不为您检查密钥的唯一性？它为那些不需要它的程序节省了哈希查找的成本 - 例如，其密钥由递增的非重复计数器生成的程序。

但是，如果替换是常见操作，则可以使用 HASH_REPLACE宏。这个宏，在添加item之前，会先尝试找到一个key相同的item，然后先删除。它还返回一个指向被替换项的指针，因此用户有机会释放其内存。

在上面的例子users中是一个全局变量，但是如果调用者想要将哈希指针传递给函数呢add_user？乍一看，您似乎可以简单地将users其作为参数传递，但这是行不通的。

您确实需要将指针传递给哈希指针：

请注意，我们在HASH_ADD也取消引用了指针。

必须处理指向散列指针的指针的原因很简单：散列宏修改它（换句话说，它们修改指针本身而不仅仅是它指向的内容）。

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);             /* optional; it's up to you! */
}

删除一个结构只是将它从哈希表中删除——它不是free 。何时释放结构完全取决于您的选择；uthash 永远不会释放你的结构。例如，当使用HASH_REPLACE宏时，会返回一个替换的输出参数，以便用户可以取消分配它。

哈希表指针（最初指向添加到哈希中的第一项）可以响应更改HASH_DEL（即，如果您删除哈希表中的第一项）。

该HASH_ITER宏是一个删除安全的迭代构造，它扩展为一个简单的 for循环。

如果您只想删除所有项目，而不是释放它们或对每个元素进行任何清理，您可以在单个操作中更有效地执行此操作：

之后，列表头（此处为users）将设置为NULL。

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

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

在上面的示例中，在fors循环的主体中删除和释放是不安全的（因为每次循环迭代时都会取消引用）。这很容易正确重写（通过在释放之前将指针复制到临时变量），但它经常出现，包括删除安全迭代宏 , 。它扩展为 -loop 标头。以下是如何使用它来重写最后一个示例：ss->hh.nextsHASH_ITERfor

如果您在 C++ 程序中使用 uthash，则需要对for 迭代器进行额外转换，例如s = static_cast<my_struct*>(s->hh.next).

当您跟随 hh.next指针时，以“插入顺序”访问散列中的项目。您可以使用 将项目排序为新顺序HASH_SORT。

第二个参数是一个指向比较函数的指针。它必须接受两个指针参数（要比较的项目），并且int如果第一项分别排在第二项之前、等于或之后，则必须返回一个小于零、零或大于零的值。strcmp（这与qsort标准 C 库中使用的约定相同）。

下面是排序函数name_sort的id_sort两个示例。

当哈希中的项目被排序时，第一个项目可能会改变位置。在上面的例子中，users调用后可能会指向不同的结构HASH_SORT。

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/test15.c. 它打印：

现在，这是相同的示例，但使用的是char *键而不是char [ ]：

此示例包含在tests/test40.c.

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

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

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

$items{bob}{age}=37

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

UT_hash_handle hh1, hh2;

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 *s);
    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);

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

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

-DHASH_BLOOM=27

user_t *users = NULL;   /* hash table of users */
user_t *admins = NULL;  /* hash table of admins */

typedef struct {
    int id;
    UT_hash_handle hh;  /* handle for users hash */
    UT_hash_handle ah;  /* handle for admins hash */
} user_t;

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

int is_admin(const void *userv) {
  user_t *user = (const user_t*)userv;
  return (user->id < 1024) ? 1 : 0;
}

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

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

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

cc -DHASH_FUNCTION=HASH_BER -o program program.c

您可以轻松确定关键域的最佳哈希函数。为此，您需要在数据收集过程中运行一次程序，然后通过包含的分析实用程序运行收集的数据。

首先，您必须构建分析实用程序。从顶级目录，

我们将用于test14.c演示数据收集和分析步骤（这里使用sh语法将文件描述符 3 重定向到文件）：

通常，您应该只选择列出的第一个哈希函数。在这里，这是SFH。这是为您的密钥提供最均匀分布的功能。如果有几个相同ideal%，则根据find_usec列选择最快的一个。

fcn

哈希函数的符号名

理想的％

哈希表中可以在理想步数内查找的项目的百分比。（下面进一步解释）。

＃项目

从发出的密钥文件中读取的密钥数

#buckets

添加所有键后哈希中的桶数

重复%

在发出的密钥文件中遇到的重复密钥的百分比。过滤掉重复的键以保持键的唯一性。（重复是正常的。例如，如果应用程序将一个项目添加到哈希中，将其删除，然后重新添加，则密钥将两次写入发出的文件。）

旗帜

如果设置了扩展禁止标志，则为ok或nx(noexpand)，如扩展内部中所述。不建议使用noexpand设置了标志的散列函数。

add_usec

将所有键添加到哈希所需的时钟时间（以微秒为单位）

find_usec

查找哈希中的每个键所需的时钟时间（以微秒为单位）

删除所有 usec

删除哈希中的每个项目所需的时钟时间（以微秒为单位）

cd tests/
make

./test_sleep &
pid: 9711

./hashscan 9711
Address            ideal    items  buckets mc fl bloom/sat fcn keys saved to
------------------ ----- -------- -------- -- -- --------- --- -------------
0x862e038            81%    10000     4096 11 ok 16    14% JEN

./hashscan -k 9711
Address            ideal    items  buckets mc fl bloom/sat fcn keys saved to
------------------ ----- -------- -------- -- -- --------- --- -------------
0x862e038            81%    10000     4096 11 ok 16    14% JEN /tmp/9711-0.key

地址

哈希表的虚拟地址

理想的

可以在理想步数内查找的表中项目的百分比。请参阅本节中的[理想]keystats。

项目

哈希表中的项目数

水桶

哈希表中的桶数

麦克

在哈希表中找到的最大链长度（uthash 通常会尝试在每个存储桶中保留少于 10 个项目，或者在某些情况下是 10 的倍数）

佛罗里达州

标志（或者ok，或者NX如果设置了扩展禁止标志）

绽放/星期六

如果哈希表使用布隆过滤器，这是过滤器的大小（作为 2 的幂）（例如，16 表示过滤器的大小为 2^16 位）。第二个数字是以百分比表示的位的“饱和度”。百分比越低，快速识别缓存未命中的潜在好处就越大。

fcn

哈希函数的符号名

键保存到

保存密钥的文件（如果有）

此哈希尝试在每个存储桶中保留少于 10 个项目。当添加一个会导致存储桶超过此数量的项目时，哈希中的存储桶数量会加倍，并且项目会重新分配到新存储桶中。在理想的世界中，每个桶将包含以前一半的项目。

存储桶扩展会根据需要自动且不可见地发生。应用程序无需知道它何时发生。

每桶扩展阈值

您通常不需要知道或担心这一点，特别是如果您keystats在开发期间使用该实用程序为您的密钥选择一个好的散列。

散列函数可能会在桶中产生不均匀的项目分布。适度这不是问题。随着链条长度的增长，正常的铲斗膨胀发生。但是当出现严重的不平衡时（因为散列函数不太适合关键域），桶扩展可能无法有效减少链长度。

想象一个非常糟糕的哈希函数，它总是将每个项目放在桶 0 中。无论桶的数量翻倍多少倍，桶 0 的链长度保持不变。在这种情况下，最好的行为是停止扩展，并接受O(n)的查找性能。这就是 uthash 所做的。如果散列函数不适合键，它会优雅地降级。

如果两个连续的桶扩展产生ideal%的值低于 50%，则 uthash 禁止该哈希表的扩展。一旦设置，桶扩展禁止标志保持有效，只要散列中有项目。抑制膨胀可能会导致HASH_FIND表现出比恒定时间性能更差的情况。

如果 uthash 正在扩展存储桶或设置存储桶扩展禁止标志，则会执行两个“通知”挂钩。应用程序无需设置这些挂钩或采取行动来响应这些事件。它们主要用于诊断目的。通常这两个钩子都是未定义的，因此编译为空。

uthash_expand_fyi挂钩可以定义为在 utash 执行存储桶扩展时执行代码。

每当 uthash 设置存储桶扩展禁止标志时，uthash_noexpand_fyi可以定义挂钩以执行代码。

默认情况下，uthash 使用mallocandfree来管理内存。如果您的应用程序使用自己的自定义分配器，uthash 也可以使用它们。

注意uthash_free接收两个参数。该sz参数是为了方便管理自己的内存的嵌入式平台。

Uthash 还使用strlen（例如在HASH_FIND_STR便利宏中）和memset（仅用于归零内存）。在不提供这些功能的平台上，您可以替换自己的实现。

如果内存分配失败（即uthash_malloc函数返回NULL），默认行为是通过调用来终止进程exit(-1)。这可以通过重新定义uthash_fatal宏来修改。

致命功能应终止进程或longjmp返回安全位置。请注意，分配失败可能会导致分配的内存无法恢复。之后uthash_fatal，哈希表对象应该被认为是不可用的；HASH_CLEAR当哈希表处于这种状态时，即使在哈希表上运行也可能不安全。

要在无法分配内存时启用“返回失败”，请HASH_NONFATAL_OOM在包含uthash.h头文件之前定义宏。在这种情况下，uthash_fatal不使用；相反，每次分配失败都会导致一次调用uthash_nonfatal_oom(elt)whereelt是其插入触发失败的元素的地址。的默认行为 uthash_nonfatal_oom是无操作。

在调用 之前uthash_nonfatal_oom，哈希表回滚到有问题的插入之前的状态；没有内存泄漏。throw进出处理程序是安全longjmp的uthash_nonfatal_oom 。

参数将elt是正确的指向元素的类型，除非 uthash_nonfatal_oom从 调用HASH_SELECT，在这种情况下，它将是void*类型并且必须在使用之前进行强制转换。无论如何，elt->hh.tbl 都会NULL。

ADD只有在向哈希表添加元素时（包括、REPLACE和SELECT操作） ，分配失败才可能发生。uthash_free不允许失败。

pthread_rwlock_t lock;
if (pthread_rwlock_init(&lock, NULL) != 0) fatal("can't create rwlock");

if (pthread_rwlock_rdlock(&lock) != 0) fatal("can't get rdlock");
HASH_FIND_INT(elts, &i, e);
pthread_rwlock_unlock(&lock);

if (pthread_rwlock_wrlock(&lock) != 0) fatal("can't get wrlock");
HASH_DEL(elts, e);
pthread_rwlock_unlock(&lock);