C語言uthash使用指南

• 1. C語言中的哈希
• 2. 它能做什麼？
• 3. 您的結構
• • 1. The key
  • 2. Unique keys(唯一鍵值)
  • 3. 哈希句柄
• 2. 關于memory
• • 1. 開銷
  • 2. 清理如何進行
• 3. 哈希操作
• • 1.宏引用
  • 2. 聲明哈希
  • 3. 添加項目
  • 檢查唯一性
  • 4. 替換項目
  • 5. 查找項目
  • 6. 删除項目
  • • 1. 單個删除
    • 2. 疊代删除
    • 3. 一次性全部删除
  • 7. 對項目進行計數
  • 8. 疊代和排序
  • • 1. 疊代
    • 2. 排序
• 4. 一個完整的例子
• 5. Standard key 類型
• • 1. 整數鍵值
  • 2. 字元串鍵值
  • 3. 指針鍵值
  • 4. 結構體鍵值
• 6. 參數說明

1. C語言中的哈希

在 C 中，哈希沒有存在于語言本身中。是以使用起來很麻煩，該軟體為C提供了一個哈希表結構。項目開源在github上，uthash下載下傳位址，下載下傳之後是.h頭檔案，功能都是宏實作的，是以可以直接在你的項目中添加#include"uthash.h"之後就能使用，本文章是對于官網的翻譯，友善大家好了解。官方文檔位址

2. 它能做什麼？

此軟體支援對哈希表中的項目進行以下操作：

1.添加/替換

2.找到

3.删除

4.計數

5.疊代

6.排序

3. 您的結構

在 uthash 中，哈希表由結構組成。每個結構代表一個 鍵值關聯。一個或多個結構字段構成鍵。 結構指針本身就是值。

定義可散列的結構

#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};
           

請注意，在 uthash 中，當您将結構添加到哈希表中時，您的結構永遠不會被移動或複制到另一個位置。這意味着您可以保留安全指向您的結構的其他資料結構 - 無論您在程式的生存期内是在哈希表中添加還是删除它。

1. The key

對鍵字段的資料類型或名稱沒有限制。鍵還可以包含多個具有任何名稱和資料類型的連續字段。

任何資料類型…真？

是的，您的鍵和結構可以具有任何資料類型。與具有固定原型的函數調用不同，uthash 由宏組成——其參數是非類型的——是以能夠使用任何類型的結構或鍵。

2. Unique keys(唯一鍵值)

與任何哈希一樣，每個項目都必須有一個唯一的鍵。應用程式必須強制實施密鑰唯一性。在将項目添加到哈希表之前，您必須首先知道（如果有疑問，請檢查！）該密鑰尚未使用。您可以使用 HASH_FIND 檢查哈希表中是否已存在鍵。

3. 哈希句柄

結構中必須存在UT_hash_handle字段。它用于使哈希工作的内部簿記。它不需要初始化。它可以命名為任何東西，但您可以通過命名 hh 來簡化事情。這允許您使用更簡單的“友善”宏來添加、查找和删除項目。

2. 關于memory

1. 開銷

在32位系統中，散列句柄每項消耗大約32個位元組，在64位系統中每項消耗大約56個位元組。其他間接費用 - 存儲桶和 表–相比之下可以忽略不計。

2. 清理如何進行

有人問uthash如何清理其内部存儲器。答案很簡單：當您從哈希表中删除最後一項時，uthash 會釋放所有 與該哈希表關聯的内部存儲器，并将其指針設定為 NULL。

3. 哈希操作

1.宏引用

uthash 宏分為兩類，便利宏與正常宏。

便利宏：

便利宏與正常宏執行相同的操作，但需要較少的參數。為了使用友善的宏，結構的UT_hash_handle字段必須命名為 hh，并且對于“添加”或“查找”，鍵字段的類型必須是 int 或 char[] 或指針。對應HASH_ADD_INT,HASH_ADD_STR,HASH_ADD_PTR。

正常宏：

文章暫時隻介紹便利宏，正常宏暫時不做說明。

2. 聲明哈希

使用前您的哈希必須聲明為指向結構的 -initialized 指針。NULL

3. 添加項目

根據需要配置設定和初始化結構。對 uthash 來說，唯一重要的方面是您的密鑰必須初始化為唯一值。然後調用 .（這裡我們使用便利宏，它為類型的鍵提供了簡化的用法）。HASH_ADDHASH_ADD_INT（增加int類型key值）

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

第一個參數是哈希表，第二個參數是鍵字段的名稱。最後一個參數是指向正在添加的結構的指針。

密鑰在使用過程中不得修改

将結構添加到哈希後，請勿更改其鍵的值。相反，請從哈希中删除該項，更改密鑰，然後重新添加它。

檢查唯一性

在上面的示例中，我們沒有檢查是否已經是哈希中某些現有項目的鍵。如果程式有可能生成重複的密鑰，則必須在将密鑰添加到哈希之前顯式檢查唯一性。如果鍵已在哈希中，則隻需修改哈希中的現有結構，而無需添加項。将具有相同鍵的兩個項目添加到哈希表是錯誤的。

讓我們重寫函數以檢查 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);
}
           

4. 替換項目

HASH_REPLACE_INT宏等效于HASH_ADD_INT宏，隻是它首先嘗試查找和删除項目。如果它找到并删除了某個項目，它還将傳回該項目指針作為輸出參數。

5. 查找項目

要在哈希中查找結構，您需要它的鍵。然後調用 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;
}
           

找到相應鍵值時，s傳回給定鍵的結構，當找不到時s傳回NULL。

中間的參數是一個指向鍵的指針。你不能把一個字面的鍵值傳遞，而是把字面的值配置設定給一個變量，并傳遞一個指向該變量的指針。

6. 删除項目

1. 單個删除

要從哈希中删除一個結構，你必須有一個指向它的指針。(如果你隻有鍵，首先要做的是獲得結構的指針）。

void delete_user(struct my_struct *user) {
    HASH_DEL(users, user);  /* user: pointer to deletee */
    free(user);             /* optional; it's up to you! */
}
           

删除一個結構隻是把它從哈希表中删除–它并沒有删除。何時釋放你的結構，完全由你自己決定；uthash永遠不會釋放你的結構。例如，當使用宏時，被替換的輸出參數會被傳回，以使使用者有可能去配置設定它。

hash表指針（最初指向添加到散列中的第一個項目）可以響應而改變（即如果你删除了散清單中的第一個項目）。

2. 疊代删除

該宏是一個删除安全的疊代結構，可擴充為一個簡單的for循環。 HASH_ITER

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

3. 一次性全部删除

如果你隻想删除所有的項目，但不釋放它們或做任何按元素的清理，你可以在一個操作中更有效地完成。

之後，清單頭将被設定為NULL

7. 對項目進行計數

哈希表中的項目數可以使用以下方法獲得：HASH_COUNT

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

當users為NULL時，HASH_COUNT會傳回0。

8. 疊代和排序

1. 疊代

你可以通過從頭開始并跟随指針hh.next循環浏覽哈希中的項目。

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

由于字段的存在，在哈希中向前和向後疊代項目是可能的。哈希中的所有項目都可以通過反複遵循這些指針來到達，是以哈希也是一個 雙向連結清單。

2. 排序

第二個參數是一個指向比較函數的指針。它必須接受兩個指針參數（要比較的項目），如果第一個項目排序在第二個項目之前、等于或之後。并且必須傳回一個小于零、零或大于零的值。（這與标準C庫中的strcmp或qsort使用的約定相同）。

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

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

4. 一個完整的例子

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

5. Standard key 類型

1. 整數鍵值

當鍵值為整型時，可以使用HASH_ADD_INT和HASH_FIND_INT。（對于所有類型的鍵，其他操作（例如HASH_DELETE和）HASH_SORT都是相同的）。

2. 字元串鍵值

當鍵值為字元串時，具體要使用那個函數取決于結構體中的鍵值為字元數組還是字元指針。 這一點很重要。當結構體中的鍵值為字元數組時，使用HASH_ADD_STR。鍵值為字元指針時使用HASH_ADD_KEYPTR。接下來給出兩個例子參考。

字元數組：

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

字元指針：

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

3. 指針鍵值

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

4. 結構體鍵值

在将項目添加到哈希或查找項目之前，必須将結構體鍵值中的元素清零。（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;
}
           

6. 參數說明

hh_name

  UT_hash_handle結構中字段的 名稱。俗稱 hh。

head

  結構指針變量，用作哈希的“頭”。如此命名是因為它最初指向添加到哈希中的第一項。

keyfield_name

  結構中鍵字段的名稱。（對于多字段鍵，這是鍵的第一個字段）。如果您不熟悉宏，則将字段名稱作為參數傳遞似乎很奇怪。請參閱 注釋。

key_len

  鍵字段的長度（以位元組為機關）。例如，對于整數鍵，它是 sizeof(int)，而對于字元串鍵，它是strlen(key)。（有關多字段鍵，請參閱此注釋。）

key_ptr

  對于HASH_FIND，這是指向要在哈希中查找的鍵的指針（由于它是指針，是以您不能在此處直接傳遞文字值）。對于 HASH_ADD_KEYPTR，這是要添加的項的鍵的位址。

hashv

  提供的鍵的哈希值。這是…_BYHASHVALUE宏的輸入參數，是 的輸出參數HASH_VALUE。如果您要重複查找相同的鍵，則重用緩存的哈希值可以優化性能。

item_ptr

  指向要添加，删除，替換或查找的結構的指針，或疊代期間的目前指針。這是一個輸入參數HASH_ADD， HASH_DELETE和HASH_REPLACE宏，和用于輸出參數HASH_FIND 和HASH_ITER。（當HASH_ITER用于疊代時，tmp_item_ptr 是與item_ptr内部使用的類型相同的另一個變量）。

replace_item_ptr

  用于HASH_REPLACE宏。這是一個輸出參數，設定為指向替換的項目（如果沒有替換的項目，則設定為NULL）。

cmp

  指向比較函數的指針，該函數接受兩個參數（指向要比較的項目的指針），并傳回一個int值，該值指定第一個項目應在第二個項目之前，等于還是之後排序（如strcmp）。

condition

  接受單個參數的函數或宏（指向結構的空指針，需要将其強制轉換為适當的結構類型）。如果應“選擇”結構以将其添加到目标哈希中，則函數或宏的值應為非零值。