uthash实现分析

uthash简介详见 http://troydhanson.github.io/uthash/userguide.html，因为毕业论文中对其作了介绍，为避免查重率上升，这里不再作说明。

uthash全部使用了宏对一些函数作了实现。下面对其涉及的数据结构以及增、删、查找与遍历的流程作出介绍。

数据结构

uthash一共有三个数据类型，分别是UT_hash_handle、UT_hash_bucket与UT_hash_table。

UT_hash_handle是数据的基本存储单位，即元数据，每一个使用uthash的数据结构都应该将其作为自己的成员，这样需要使用uthash的数据结构将在uthash中存在挂载点。

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

UT_hash_bucket是用来存储一组元数据的容器，简称bucket。其实UT_hash_bucket只是一个索引，以它为链表头存储着UT_hash_bucket为结点的链表。

UT_hash_table是由多个bucket构成的表（数组）。为了提高查找效率，挂载在bucket链表上的元数据是有个数限制的，当bucket链表长度超过最大长度时，UT_hash_table将会重新申请现在bucket数量的两倍作为新的存储空间，并将原有的数据重新存放到新的bucket中。

哈希的实现采用拉链法，三者的简要的关系图如下。
三者关系.png

增加流程

当增加一个Key和元数据到哈希表中时，执行的步骤如下。

将这个Key通过哈希函数转换为整型数值hashv，常用的哈希函数参见另一篇文章哈希算法；
将得到的hashv进一步映射，映射的范围是bucket的数量范围，因为table中是由数组存放每个bucket的，所以此次映射的目的是决定由哪一个bucket存放数据，即生成数组的索引；
将这个元数据添加到对应bucket的双链表中，如果添加之后这个双链表长度超过了规定的最大长度，此时需要对bucket数量进行扩展，扩展的方法是再申请现在数量的2倍，将现有的数据一个个添加到新的bucket中。

查找与删除流程

查找流程较为简单，执行上面的1、2步骤可以确定存放该元数据的bucket，最后遍历该bucket链表对比Key即可查找到目标数据。将该数据从双链表中摘除即实现了删除流程。

遍历流程

遍历就是把哈希表中所有存放的元数据依次给取出来，顺序应该与添加的顺序相同。这里我们首先看下UT_hash_handle的结构，结构如下。

typedef struct UT_hash_handle {
   struct UT_hash_table *tbl;
   void *prev;                       /* prev element in app order      */
   void *next;                       /* next element in app order      */
   struct UT_hash_handle *hh_prev;   /* previous hh in bucket order    */
   struct UT_hash_handle *hh_next;   /* next hh in bucket order        */
   void *key;                        /* ptr to enclosing struct's key  */
   unsigned keylen;                  /* enclosing struct's key len     */
   unsigned hashv;                   /* result of hash-fcn(key)        */
} UT_hash_handle;

其中prev与next指向存放的上一个与下一个元素。uthash为所有元素建立了一个双链表，其中双链表的末尾指向UT_hash_table中的tail成员。当需要遍历整个哈希表时，只需要遍历该双链表即可。

总结

总而言之，uthash实现还是比较简单的，却很好的实现了哈希表的功能，需要使用哈希表的同学可以试用一下。