IoTShare

uthash实现分析

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

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

数据结构

uthash一共有三个数据类型,分别是UT_hash_handleUT_hash_bucketUT_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和元数据到哈希表中时,执行的步骤如下。

  1. 将这个Key通过哈希函数转换为整型数值hashv,常用的哈希函数参见另一篇文章哈希算法
  2. 将得到的hashv进一步映射,映射的范围是bucket的数量范围,因为table中是由数组存放每个bucket的,所以此次映射的目的是决定由哪一个bucket存放数据,即生成数组的索引;
  3. 将这个元数据添加到对应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;

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

总结

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

本原创文章未经允许不得转载 | 当前页面:IoTShare » uthash实现分析

评论