uthash簡介

??由于C語言本身不存在哈希，但是當需要使用哈希表的時候自己構建哈希會例外復雜，因此，我們可以呼叫開源的第三方頭檔案，這只是一個頭檔案：uthash.h，我們需要做的就是將頭檔案復制到您的專案中，然后：#include "uthash.h"，由于uthash僅是頭檔案，因此沒有可鏈接的庫代碼，

??使用uthash添加，查找和洗掉通常是常數時間的操作，此哈希的目標是簡約高效，它大約有1000行C，它會自動行內，因為它是作為宏實作的，
??uthash還包括三個額外的頭檔案，主要提供鏈表，動態陣列和字串，utlist.h為C結構提供了鏈接串列宏，utarray.h使用宏實作動態陣列，utstring.h實作基本的動態字串，
??github下載鏈接：https://github.com/troydhanson/uthash

uthash的使用

定義結構體

??這里我們將id作為一個索引值，也就是鍵值，將name作為value，

#include "uthash.h"
struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};
/*宣告哈希為NULL指標*/
struct my_struct *users = NULL;    /* important! initialize to NULL */

??注意：一定要包含UT_hash_handle hh;hh不需要初始化，它可以命名為任何名稱，但是我們一般都命名為hh，

添加

??HASH_ADD_INT表示添加的鍵值為int型別
??HASH_ADD_STR表示添加的鍵值為字串型別
??HASH_ADD_PTR表示添加的鍵值為指標型別
??HASH_ADD表示添加的鍵值可以是任意型別

void add_user(int user_id, char *name) {
    struct my_struct *s;
    /*重復性檢查，當把兩個相同key值的結構體添加到哈希表中時會報錯*/
    HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */
    /*只有在哈希中不存在ID的情況下，我們才創建該專案并將其添加，否則，我們只修改已經存在的結構，*/
    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);
}

??HASH_ADD_INT函式中，第一個引數users是哈希表，第二個引數id是鍵欄位的名稱，最后一個引數s是指向要添加的結構的指標，

查找

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是輸出變數，當可以在哈希表中找到相應鍵值時，s回傳給定鍵的結構，當找不到時s回傳NULL，

替換

??HASH_REPLACE宏等效于HASH_ADD宏，HASH_REPLACE會嘗試查找和洗掉專案外，如果找到并洗掉了一個專案，它還將回傳該專案的指標作為輸出引數，

void replace_user(HashHead *head, HashNode *newNode) {
    HashNode *oldNode = find_user(*head, newNode->id);
    if (oldNode)
        HASH_REPLACE_INT(*head, id, newNode, oldNode);
}

洗掉

??要從哈希表中洗掉結構，必須具有指向它的指標，（如果只有鍵，請先執行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是指向我們要從哈希中洗掉的結構的指標，

??洗掉結構只是將其從哈希表中洗掉，并非free ，何時釋放結構的選擇完全取決于自己；uthash永遠不會釋放您的結構

回圈洗掉

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

洗掉哈希表所有元素

??如果您只想洗掉所有專案，但不釋放它們或進行每個元素的清理，則可以通過一次操作更有效地做到這一點：

HASH_CLEAR(hh,users);

??之后，串列頭（此處為users）將設定為NULL，

計算哈希表元素個數

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

??當users為NULL時，HASH_COUNT會回傳0.

遍歷哈希表中的所有專案

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指標，可用于從任何已知項開始向后迭代哈希，
??由于hh.prev和hh.next欄位的緣故，可以在哈希中向前和向后迭代，可以通過重復跟隨這些指標來訪問哈希中的所有專案，因此哈希也是雙鏈表，

排序哈希表

HASH_SORT( users, name_sort );

??第二個引數是指向比較函式的指標，它必須接受兩個指標引數（要比較的專案），并且如果第一個專案分別在第二個專案之前，等于或之后排序，則必須回傳小于零，零或大于零的int，（這與標準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 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);
}

完整代碼

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

鍵值的各種型別舉例

整型鍵值

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

字串鍵值

??當鍵值為字串時，具體要使用那個函式取決于結構體中的鍵值為字串陣列還是字串指標， 這一點很重要，當結構體中的鍵值為字串陣列時，使用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;
}

指標鍵值

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

常用宏參考

型別宏

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)

通用宏

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
??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
??接受單個引數的函式或宏（指向結構的空指標，需要將其強制轉換為適當的結構型別），如果應“選擇”結構以將其添加到目標哈希中，則函式或宏的值應為非零值，

有任何問題，均可通過公告中的二維碼聯系我

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/247018.html

標籤：嵌入式

上一篇：qsort函式使用方法總結（詳細全面+代碼）

下一篇：面試官不講武德，居然讓我講講蠕蟲和金絲雀！

C語言哈希表uthash的使用方法詳解（附下載鏈接）