序言

众所周知，哈希表是时间复杂度为o(1)的一种查找方式。当要查找的数据比较多，又没有什么规律时，因为哈希表的时间复杂度几乎不随着数据量的增加而增大，于是使用哈希表就是一种不错的数据查找方式。
之后嘛，我在做 leetcode 的一道题的时候，使用的是C语言，但有需要使用到哈希表的数据结构，于是就自己手撸了一个。结果嘛，因为是自己造轮子，所以效果自然不是特别理想。后来才知道 leetcode 里的c语言可以直接使用 UT_Hash 这个库，所以这里也简单记录下用法。

（简介略）

哈希表这种数据结构有什么用呢？这里简单举个我记忆中之前在某本算法书里看到的例子：
比如你有一家水果店，店里就卖两种水果：苹果卖5元，香蕉卖10元。那么各商品的价格可以用下表来表示：

到目前为止，我们还只有两种水果，若是客人拿着水果来向我们询问价格的话，我们可以很轻松地写出一个函数：

# 伪代码
def get_price(fruit):
    if fruit == 'Apple':
        return 5
    else:
        return 10

好，现在我们给获取价格函数还非常简单，但是，若是随着我们水果店之后的发展，水果的数量变多了呢：

水果数量躲起来之后，再一个个if...else...判断就会比较麻烦了。不过我们还可以使用遍历的方法去查询：

# 伪代码
def get_price(fruit):
    for item in fruits:
        if item.name == fruit:
            return item.price

虽然这样的函数的编写还是非常容易的。但是很显然，这样的查询的时间复杂度为 o(n) 。随着水果数量的增加，查询所需的时间也会比较快的增加。有没有办法能降低这一过程的时间复杂度呢？
在储存所有的水果的价格的时候，我们会开辟一段内存用于储存水果的价格。所以，查询的过程就可以看作通过给定输入的水果名称得到储存着水果价格的地址的函数。所以，只要能降低这个函数的时间复杂度，那就好办了。
仔细观察一下上面的水果，我们可以发现他们的首字母都不同，那么，我们可以用这么一个方式去储存水果的价格：先开辟长度为26的一段内存空间，然后再按照26个英文字母的排序将它们放到指定的空间。即：

这样的话，之后查询水果的价格就可以又方便又快捷了：

 # 伪代码
def get_price(fruit):
    return fruits[fruit[0] - 'A'].price

好的！我们成功地把查询水果价格的时间复杂度降到了 o(1) ，来再多的水果也不怕！
当然，你可能会反驳：世界上又不是只有这么点水果，要是遇上首字母相同的水果该怎么办啊！
不要慌\~，这种问题我们还是有很多解决方法的。我这里举两种例子。假如我们又多了个叫做 berry 的水果吧，它和我们的 banana 重复啦：

1. 其一就是：虽然我们遇到了首字母相同的水果，但这毕竟是少数。我们可以先不直接储存水果的价格，而是储存一个包含所有相同首字母的水果的链表的首个元素地址，这样子，我们在查询 B开头的水果的时候，虽不能直接定位到 Berry ，但 B 开头的水果已经比所有的水果少多了，我们再在这些水果中遍历查找指定的水果，速度还是比直接遍历查找快多了。
2. 其二就是：虽然这两个水果的首字母重复了，但它们的第二个字母不同啊，所以我们可以开辟 26*26=676 长度的内存，按照它们的前两个字母插入指定的位置。查找的时候再按照它前两个字母来计算出对应的地址。就算水果前两个字母都相同了，我们也还可以继续扩展到第三位，第四位...总不可能两个水果名字完全相同吧。

以上，我们就可以算是找到了一种可以比较快速定位要查找的目标的算法了。虽然我们可以看到，在这个过程中有不少的内存被浪费掉了，不过确实是降低了查询的时间复杂度，可以看作一种“空间换时间”了。

上面我们讨论的做法其实就和哈希表的思想比较接近了。通过区首字母来获取地址的方式可以看作哈希表的哈希函数，只不过一般的哈希表都不会使用这么简单的哈希函数，而是使用一些碰撞率更低的函数，以让插入哈希表的元素能够更均匀的分布在内存中。而上面遇到的首字母相同的情况就可以看作发生了哈希碰撞了。
下面就介绍一下 uthash 这个比较成熟的哈希表的库的使用。

UT_Hash 在 C 语言中的运用

那么我这里就简单介绍下 uthash 这个库的使用。

首先我们要知道的是，哈希表可以看作从一个“东西”到另一个“东西”的映射。例如在之前的例子中，通过水果的名字“字符串”到它的价格“实数”的映射。在进行操作时，我们输入水果的名字，通过哈希函数从而得到储存着这种水果的价格的地址。

graph LR
A[Fruit] -- "Name: Apple" --> B(Hash Function)
B --"Address: 0x123" --> C[Price]

对于C语言这样的静态类型语言，我们在指定哈希表之前就应该确定好键值和查找对象的类型。
为了简化一些，下面的示例中使用 int 为键值类型，字符串为要找的值的类型。例如现实生活中通过学号去查找这个学号对应的学生的姓名的情况。这种查找若是采用逐一比较的方式的话时间复杂度为 o(n) ，当学生数量很多的时候效率就会非常低。虽然采用例如二分查找的方式能有 o(logn) 的时间复杂度，但很多情况下，学号在最大值和最小值之间并不是均匀分布的，再加上一些其他的原因，二分查找不一定是最优解。所以这里使用哈希表的方式查找。

uthash 的使用需要先包含相应的库并建立对应的结构体：

#include"uthash.h"  
   
struct my_struct {  
    int id;                    /* key */  
    char name[10];  
    UT_hash_handle hh;         /* makes this structure hashable */  
};  

定义好了一个结构体之后用下面的代码实例化一个哈希表：

struct my_struct *g_users = NULL;

有了这些之后就可以对这个哈希表进行增删查改的操作了。

1. 查

下面的代码用来查找指定的哈希表中是否存在着指定键的值。

int ikey = 123; // 指定要查找的键（例如学号）。
struct my_struct *s;  // 查找到的结果将保存在这里（例如姓名）。
HASH_FIND_INT(g_users, &ikey, s );  // uthash 提供的查找函数。
if(s) // exists.

可以看到，其中的 HASH_FIND_INT 就是这段代码的核心。通过示例代码我们不难看出它的结构。它的三个参数分别代表了：在哪个哈希表(g_users)中查找关键字为某个值(&ikey)的数据并保存在这个地址(s)中。

2. 增

接下来介绍下增加元素的部分：

void add_user(int ikey, char *value_buf) {  
    struct my_struct *s;  
    HASH_FIND_INT(g_users, &ikey, s);  // 插入前先查看key值是否已经在hash表g_users里面了  
    if (s==NULL) {  // g_users 内不存在 ikey 时才进行插入操作。
      s = (struct my_struct*)malloc(sizeof(struct my_struct));  // 为插入的元素开辟空间。
      s->ikey = ikey;  
      HASH_ADD_INT(g_users, ikey, s );  // 执行插入操作。
    }  
    strcpy(s-> value, value_buf);  // 别忘了给s赋值。
}  

同样，上面的代码也是比较显然了。需要注意的就是 uthash 要求 key 必须是唯一的，所以这里我们在插入前要先查找是否存在同 key 的元素，不存在再进行插入。

由于uthash要求键（key）必须唯一，而uthash内部未对key值得唯一性进行很好的处理，因此它要求外部在插入操作时要确保其key值不在当前的hash表中，这就需要，在插入操作时，先查找hash表看其值是否已经存在，不存在在时再进行插入操作，在这里需要特别注意以下两点：
插入时，先查找，当键不在当前的hash表中时再进行插入，以确保键的唯一性。
需调用插入接口函数时需要明确告诉接口函数，自己定义的键变量的名字是什么。

之后在 HASH_ADD_INT 内，这个函数也有三个参数。其含义就相当于建立一个在 g_users 内，从 ikey 到 s 的一个映射。有了这个映射，我们之后再 g_users 内查找的时候，输入 ikey 的时候就可以找到 s 了。不过需要注意的是，这个时候我们还是仅建立了从 ikey 到 s 的地址的映射，与 s 内的具体的内容无关。所以，之后我们还要手动给 s 这个结构体内的 name 进行赋值。

3. 删

接下来是删除操作，用于在指定的哈希表中删除一个指定的元素：

void delete_user(int ikey) {  
    struct my_struct *s = NULL;  
    HASH_FIND_INT(g_users, &ikey, s);  
    if (s!=NULL) {  
      HASH_DEL(g_users, s);   
      free(s);              
    }  
}  

同样，这一部分也还是比较容易理解的，先查找到要删除的元素，然后去删除。

删除操作的接口函数为 HASH_DEL ，只需要告诉该接口要释放哪个 hash 表（这里是 g_users ）里的哪个节点（这里是 s ），需要注意：释放申请的hash结构体变量，uthash函数只将结构体从hash表中移除，并未释放该结构体所占据的内存。

以上，就实现了一个哈希表的增删查改操作了。什么，你问改在哪里？前面都那么多示例了，你先查到对应的结构体然后进行修改不久可以了嘛。
除了常见的增删查改操作外，uthash还有一些其他的功能，这里简单摘录下。（下面基本转载于《c开源hash项目 uthash的用法总结》[1]。）

4. 清空 Hash 表

void delete_all() {  
  struct my_struct *current_user, *tmp;  
   
  HASH_ITER(hh, users, current_user, tmp) {  
    HASH_DEL(g_users,current_user);    
free(current_user);              
  }  
}  

5. 统计 Hash 表中已存在的元素数

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

6. 遍历元素

void print_users() {  
    struct my_struct *s;  
   
    for(s=g_users; s != NULL; s=s->hh.next) {  
        printf("user ikey %d: value %s\n", s->ikey, s->value);  
    }  
}  

uthash 的实际使用

在 uthash 的官方github页面下有一篇使用示例[3]，已经写的比较详细，这里不再赘述。
本想在这里放一段自己在leetcode里实际使用到uthash的代码来着，不过因为时间久远已经找不到了，就之后再补吧。。

References

c开源hash项目 uthash的用法总结
C语言中哈希表uthash的使用
uthash/tests/example.c