uthash.h -- C Style Hashtable

#Usage

uthash.h实现了C语言的哈希表，是一个Header-only Library

Copy the header file into your project, and:

1

#include "uthash.h"

#Structure

uthash允许你将任何C结构体存储在哈希表中，只需要在结构体中加入UT_hash_handle成员，并且选择结构体中的一个变量作为key

1
2
3
4
5


typedef struct {
    int key;                 /* we'll use this field as the key */
    char name[10];
    UT_hash_handle hh;      /* makes this structure hashable */
} HashItem;

#Declaration

你的哈希表必须首先声明初始化为NULL

1

HashItem head = NULL;  /* important! initialize to NULL */

#API

#HASH_ADD_XXX

1

HASH_ADD_INT(head, key, s)

添加元素到哈希表
head: 之前声明的哈希表头
key: 结构体内被选为键的字段名
s: 要放入哈希表的结构体指针

1
2
3
4
5
6


void Hash_Add(int id, char *name) {
    HashItem *item = (HashItem*)malloc(sizeof(HashItem));
    s->key = id;
    strcpy(s->name, name);
    HASH_ADD_INT(head, key, item);  /* key: name of the key field */
}

注意到，第二个参数只需要写结构体中被选为键的那个成员名，在宏展开后它会被处理成有效的C代码。

#检查键的唯一性

在添加一个结构体到哈希表前，用户必须显式检查键的唯一性。如果没有检查唯一性，并且加入了两个相同的键，将会引发错误。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void Hash_Add(int id, char *name) {
    HashItem *item;
    HASH_FIND_INT(head, &id, item);  /* Checking uniqueness */
    if (item == NULL) {
        item = (HashItem*)malloc(sizeof(HashItem));
        s->key = id;
        strcpy(s->name, name);
        HASH_ADD_INT(head, key, item);  /* key: name of the key field */
    }
}

#函数传参

先前使用的head是一个全局变量，如果调用者想把它作为参数传入Hash_Add函数。直觉上只需要传递初始化的头指针head即可，但是这样不会正确工作：

1
2
3
4
5


/* bad */
void Hash_Add(HashItem *head, int id, char *name) {
    ...
    HASH_ADD_INT(head, key, item);
}

你需要传递的是头指针的指针：

1
2
3
4
5


/* good */
void Hash_Add(HashItem **head, int id, char *name) {
    ...
    HASH_ADD_INT(*head, key, item);
}

uthash的哈希表头指针（如head）本质是一个动态变化的哨兵节点。当：

第一次添加元素时，头指针会被赋予第一个元素的地址
删除最后一个元素时，头指针会被重置为 NULL

所以要修改的是指针的指向，即指针的值。

当执行HASH_ADD_INT等操作时，宏内部实际上会修改头指针的值
- 如果头指针原本是NULL，添加一个元素后，头指针必须被更新为新元素的地址
- 传值会创造指针副本，仅修改了副本指针的指向，但不会修改head的指向，是无效的

#HASH_FIND_XXX

1

HASH_FIND_INT(head, &search_key, find_res);

在哈希表中寻找元素
head: 之前声明的哈希表头
search_key: 要查找的键的指针，不可传递字面量
find_res: 出参，结构体指针，用于存放查找结果。为空表示未找到。

1
2
3
4
5


HashItem* Hash_Find(HashItem **head, int id) {
    HashItem *item;
    HASH_FIND_INT(head, &id, item);  /* s: output pointer */
    return item;
}

#HASH_DEL

1

HASH_DEL(head, s);

删除哈希表中的节点
head: 之前声明的哈希表头
s: 要删除的结构体指针

要删除一个节点，必须拥有指向这个节点结构体的指针，若你只有key，那么需要先通过HASH_FIND获取到指向结构体的指针：

1
2
3
4
5
6
7
8


void Hash_Delete(HashItem** head, int id) {
    HashItem *item;
    HASH_FIND_INT(head, &id, item);
    if(s != NULL) {
        HASH_DEL(head, item);
        free(item);
    }
}

#uthash的内存管理

uthash永远不会释放结构体的空间，HASH_DEL仅仅把对应的结构体移除出哈希表，而不会free它。释放空间的时机交由用户进行选择。

#HASH_DEL可能会改变头指针

比如你尝试删除哈希表的第一个节点。

#HASH_ITER

1

HASH_ITER(hh, head, cur, tmp) {...}

用于遍历哈希表节点
hh: 哈希句柄，即UT_hash_handle成员名
head: 哈希表头指针
cur: 遍历过程中指向当前元素的指针
tmp: 临时指针，用于安全删除元素时避免遍历错误

HASH_ITER是一个deletion-safe的宏，展开会是一个for循环。

1
2
3
4
5
6
7
8


/* 删除哈希表中的所有节点 */
void Hash_Destroy(HashItem **head) {
    HashItem *cur, *tmp;
    HASH_ITER(hh, head, cur, tmp) {
        HASH_DEL(head, cur);
        free(cur);
    }
}

#HASH_CLEAR

如果你只想将所有结构体从哈希表中移除，而不释放它们的空间，可以使用以下的简单宏：

1

HASH_CLEAR(hh, head);

调用之后head将会被设为NULL。

#HASH_COUNT

获取哈希表的节点个数：

1
2


unsigned int num = HASH_COUNT(head);
printf("num of hash table: %u \n", num);

#e.g.

380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有相同的概率被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

示例：: 输入; ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]; [[], [1], [2], [2], [], [1], [2], []]; 输出; [null, true, false, true, 2, true, false, 2] ：; 解释; RandomizedSet randomizedSet = new RandomizedSet();; randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。; randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。; randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。; randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。; randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。; randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。; randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

-2³¹ <= val <= 2³¹ - 1
最多调用 insert、remove 和 getRandom 函数 2 * 10⁵ 次
在调用 getRandom 方法时，数据结构中至少存在一个元素。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96


#define MAX_ITEM_NUM 200000

typedef struct {
    int key;
    int value;
    UT_hash_handle hh;
} HashItem;

typedef struct {
    HashItem* hashHead;
    int* vector;
    int vectorSize;
} RandomizedSet;

HashItem* Hash_FindKey(HashItem** head, int key) {
    HashItem* findRet = NULL;
    HASH_FIND_INT(*head, &key, findRet);
    return findRet;
}

void Hash_InsertKey(HashItem** head, int key, int value) {
    HashItem* item = (HashItem*)malloc(sizeof(HashItem));
    item->key = key;
    item->value = value;
    HASH_ADD_INT(*head, key, item);
}

void Hash_DelItem(HashItem** head, HashItem* item) {
    HASH_DEL(*head, item);
    free(item);
}

RandomizedSet* randomizedSetCreate() {
    RandomizedSet* ret = (RandomizedSet*)malloc(sizeof(RandomizedSet));
    ret->hashHead = NULL;
    ret->vector = (int*)malloc(sizeof(int) * MAX_ITEM_NUM);
    ret->vectorSize = 0;
    return ret;
}

bool randomizedSetInsert(RandomizedSet* obj, int val) {
    HashItem* findRet = Hash_FindKey(&obj->hashHead, val);
    if (findRet)
        return false;

    // 1. 插入哈希表
    Hash_InsertKey(&obj->hashHead, val, obj->vectorSize);
    // 2. 插入动态数组
    obj->vector[obj->vectorSize++] = val;
    return true;
}

bool randomizedSetRemove(RandomizedSet* obj, int val) {
    HashItem* findRet = Hash_FindKey(&obj->hashHead, val);
    if (!findRet)
        return false;

    // 1. 删除动态数组
    int toDelIndex = findRet->value;
    obj->vector[toDelIndex] = obj->vector[obj->vectorSize - 1];
    HashItem* lastItem =
        Hash_FindKey(&obj->hashHead, obj->vector[obj->vectorSize - 1]);
    lastItem->value = toDelIndex;
    obj->vectorSize--;
    // 2. 删除哈希表
    Hash_DelItem(&obj->hashHead, findRet);
    return true;
}

int randomizedSetGetRandom(RandomizedSet* obj) {
    if (obj->vectorSize == 0)
        return -1; // 防止除零错误
    int randomIndex = rand() % obj->vectorSize;
    return obj->vector[randomIndex];
}

void randomizedSetFree(RandomizedSet* obj) {
    HashItem *currentItem, *tmp;
    HASH_ITER(hh, obj->hashHead, currentItem, tmp) {
        Hash_DelItem(&obj->hashHead, currentItem);
    }
    free(obj->vector);
    free(obj);
}

/**
 * Your RandomizedSet struct will be instantiated and called as such:
 * RandomizedSet* obj = randomizedSetCreate();
 * bool param_1 = randomizedSetInsert(obj, val);

 * bool param_2 = randomizedSetRemove(obj, val);

 * int param_3 = randomizedSetGetRandom(obj);

 * randomizedSetFree(obj);
*/

uthash.h -- C Style Hashtable

相关文章：