源码阅读 libevent - 数据结构：哈希表
libevent 源码中除了 queue.h 文件中定义了 5 种数据结构，在 ht-internal.h 文件中定义了另一个重要的数据结构：哈希表。
本系列大部分文章介绍
linux系统下libevent的源码，但libevent在linux环境下并没有用到哈希表结构，但学习libevent中哈希表的实现非常有助于对哈希表结构的理解。
哈希表定义
哈希表定义宏
#define HT_HEAD(name, type) \ struct name { \ struct type **hth_table; /* The hash table itself. */ \ unsigned hth_table_length; /* How long is the hash table? */ \ unsigned hth_n_entries; /* How many elements does the table contain? */ \ unsigned hth_load_limit; /* How many elements will we allow in the table before resizing it? */ \ int hth_prime_idx; /* Position of hth_table_length in the primes table. */ \ } #define HT_ENTRY(type) \ struct { \ struct type *hte_next; \ unsigned hte_hash; /* Hash cache */ \ }
哈希表结构
与双向链表一样，我们通过测试程序来看哈希表在内存中的结构：
#include <stdio.h> #include <stdlib.h> #include <time.h> #include "ht-internal.h" typedef struct Node { int key; int value; HT_ENTRY(Node) map_node; } Node; HT_HEAD(INT_MAP, Node); static inline unsigned hashfn(struct Node *e) { unsigned h = (unsigned) e->key; h += (h>> 2) | (h << 30); return h; } static inline int eqfn(struct Node *e1, struct Node *e2) { return e1->key == e2->key; } HT_PROTOTYPE(INT_MAP, Node, map_node, hashfn, eqfn) HT_GENERATE(INT_MAP, Node, map_node, hashfn, eqfn, 0.5, malloc, realloc, free) int main(void) { struct INT_MAP table; HT_INIT(INT_MAP, &table); int a = 0; for (int i = 0; i < 20; i++) { srand(time(NULL) + a % 1000003); a = rand() % 1000003; Node* new_item = malloc(sizeof(Node)); new_item->key = a; new_item->value = i; HT_INSERT(INT_MAP, &table, new_item); } printf("\n[HEAD]: **hth_table = %p\n" "hth_table_length = %d\n" "hth_n_entries = %d\n" "hth_load_limit = %d\n" "hth_prime_idx = %d\n\n", table.hth_table, table.hth_table_length, table.hth_n_entries, table.hth_load_limit, table.hth_prime_idx); for (int i = 0; i < table.hth_table_length; i++) { if (table.hth_table[i]) { printf("[TABLE]: [%03d] - [%p]", i, table.hth_table[i]); Node* item = table.hth_table[i]->map_node.hte_next; while (item) { printf("--> [%p]", item); item = item->map_node.hte_next; } printf("\n"); } } Node** item; HT_FOREACH(item, INT_MAP, &table) { printf("[NODE]: Key = %-8d Value = %-5d Next = %-10p Addr = %-10p\n", (*item)->key, (*item)->value, (*item)->map_node.hte_next, *item); } return 0; }
程序执行结果如下：
哈希表头
可以看出，libevent 中定义的哈希表头结构体意义如下：
hth_table：哈希表的存储位置hth_table_length：哈希表的长度hth_n_entries：哈希表的元素个数hth_load_limit：哈希表元素限制，超过限制后需要进行哈希表扩容hth_prime_idx：哈希表容量等级，libevent 的哈希表存在 26 个容量等级
哈希冲突的解决
libevent 的哈希表是使用链地址法解决冲突问题的，这一点可以从 hth_talbe 成员变量看到。它是一个二级指针，其指向了哈希表的元素所在的地址。
哈希函数
libevent 中的哈希函数由使用者定义，上述测试代码中使用了和 libevent 中一样的哈希函数：模 (%)。
libevent中哈希表的代码存在大量的宏定义，可读性低，本文通过gcc的-E选项结合AStyle将上文中的测试程序转化为了可读性较好的代码，以下分析均采用转化后的代码片段。
哈希表的访问
查找
static inline struct Node ** INT_MAP_HT_FIND_P_(struct INT_MAP *head, struct Node *elm) { struct Node **p; if (!head->hth_table) return NULL; p = &((head)->hth_table[((elm)->map_node.hte_hash) % head->hth_table_length]); while (*p) { if (eqfn(*p, elm)) return p; p = &(*p)->map_node.hte_next; } return p; } static inline struct Node * INT_MAP_HT_FIND(const struct INT_MAP *head, struct Node *elm) { struct Node **p; struct INT_MAP *h = (struct INT_MAP *) head; do { (elm)->map_node.hte_hash = hashfn(elm); } while (0); p = INT_MAP_HT_FIND_P_(h, elm); return p ? *p : NULL; }
INT_MAP_HT_FIND_P_ 和 INT_MAP_HT_FIND 均为哈希表的查找函数，两者的区别是：
- 返回数据类型不同：
INT_MAP_HT_FIND_P_返回值是 Node**，是一个二级指针，指向的是保存被查找哈希元素的地址的指针变量 > 比如：hth_table[1]中保存着带查找元素的地址，该函数则返回的是hth_table[1]的地址信息。INT_MAP_HT_FIND返回值是 Node*，指向查找到的哈希元素
- 查找步骤差别：
INT_MAP_HT_FIND_P_直接使用计算过的哈希值进行查找INT_MAP_HT_FIND重新使用哈希函数计算哈希值后进行查找
- 判断查找成功与否方式不同：
INT_MAP_HT_FIND_P_返回值始终非空，需要判断其返回值指向的数据是否为NULL来确认查找结果INT_MAP_HT_FIND_P_查找失败时，返回的地址可以作为该元素插入的地址进行插入操作INT_MAP_HT_FIND未查找到对应元素时返回值为NULL
遍历
static inline struct Node ** INT_MAP_HT_START(struct INT_MAP *head) { unsigned b = 0; while (b < head->hth_table_length) { if (head->hth_table[b]) return &head->hth_table[b]; ++b; } return NULL; } static inline struct Node ** INT_MAP_HT_NEXT(struct INT_MAP *head, struct Node **elm) { if ((*elm)->map_node.hte_next) return &(*elm)->map_node.hte_next; else { unsigned b = (((*elm)->map_node.hte_hash) % head->hth_table_length)+1; while (b < head->hth_table_length) { if (head->hth_table[b]) return &head->hth_table[b]; ++b; } return NULL; } }
遍历的三要素：
- 遍历的起始节点
- 依次查找哈希表数组中的每一个元素，首个非空的元素即为起始节点
- 下一个节点的获取
- 如果当前节点的
next指针非空，则next指针指向的位置为下一个节点 - 如果当前节点的
next指针为空，则继续遍历哈希表数组中的元素
- 如果当前节点的
- 遍历的结束条件
- 如果遍历完哈希表数组遍历完成（根据哈希表长度值
hth_table_length判断），则遍历结束
- 如果遍历完哈希表数组遍历完成（根据哈希表长度值
哈希表的操作
哈希表的基础操作
/* 哈希表的判空 */ #define HT_EMPTY(head) ((head)->hth_n_entries == 0) /* 哈希表的表数组大小 */ #define HT_SIZE(head) ((head)->hth_n_entries) /* 哈希表的表占用的内存大小 */ #define HT_MEM_USAGE(head) (sizeof(*head) + (head)->hth_table_length * sizeof(void*))
以上接口较为简单，不进行过多说明。
初始化
static inline void INT_MAP_HT_INIT(struct INT_MAP *head) { head->hth_table_length = 0; head->hth_table = NULL; head->hth_n_entries = 0; head->hth_load_limit = 0; head->hth_prime_idx = -1; }
哈希表的初始化其实就是对表头数据进行初始化。
插入
static inline void INT_MAP_HT_INSERT(struct INT_MAP *head, struct Node *elm) { struct Node **p; if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) INT_MAP_HT_GROW(head, head->hth_n_entries + 1); ++head->hth_n_entries; do { (elm)->map_node.hte_hash = hashfn(elm); } while (0); p = &((head)->hth_table[((elm)->map_node.hte_hash) % head->hth_table_length]); elm->map_node.hte_next = *p; *p = elm; }
插入操作可分为 3 ~ 4 个步骤：
- 判断当前哈希表是否需要扩容
- 调用哈希函数计算新插入数据的哈希值
- *(需要时) 解决哈希冲突
- 头插法插入新数据（后插入的数据在链表头）
需要注意的是：
libevent的插入函数INT_MAP_HT_INSERT并没有对重复的哈希key进行判断，所以根据不同的应用场景，可能会有不同的应用方式。
修改 & 插入
static inline struct Node * INT_MAP_HT_REPLACE(struct INT_MAP *head, struct Node *elm) { struct Node **p, *r; if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) INT_MAP_HT_GROW(head, head->hth_n_entries + 1); do { (elm)->map_node.hte_hash = hashfn(elm); } while (0); p = INT_MAP_HT_FIND_P_(head, elm); r = *p; *p = elm; if (r && (r!=elm)) { elm->map_node.hte_next = r->map_node.hte_next; r->map_node.hte_next = NULL; return r; } else { ++head->hth_n_entries; return NULL; } }
INT_MAP_HT_REPLACE 函数相比 INT_MAP_HT_INSERT，多了对于重复数据的查找和替换。
需要注意的是：
INT_MAP_HT_REPLACE在插入时返回值为NULL，而在替换时返回值为被替换元素的地址，如果被替换元素空间是通过malloc等内存申请函数申请得到的，需要调用free等函数对空间进行释放。
删除
static inline struct Node * INT_MAP_HT_REMOVE(struct INT_MAP *head, struct Node *elm) { struct Node **p, *r; do { (elm)->map_node.hte_hash = hashfn(elm); } while (0); p = INT_MAP_HT_FIND_P_(head,elm); if (!p || !*p) return NULL; r = *p; *p = r->map_node.hte_next; r->map_node.hte_next = NULL; --head->hth_n_entries; return r; } static inline struct Node ** INT_MAP_HT_NEXT_RMV(struct INT_MAP *head, struct Node **elm) { unsigned h = ((*elm)->map_node.hte_hash); *elm = (*elm)->map_node.hte_next; --head->hth_n_entries; if (*elm) return elm; else { unsigned b = (h % head->hth_table_length)+1; while (b < head->hth_table_length) { if (head->hth_table[b]) return &head->hth_table[b]; ++b; } return NULL; } }
删除操作本质就是一次查找与一次数组或链表操作，两个删除函数作用类似，但返回值存在区别：
INT_MAP_HT_REMOVE和INT_MAP_HT_REPLACE类似，返回值是被删除元素的地址。INT_MAP_HT_NEXT_RMV和INT_MAP_HT_FIND_P_类似，返回的是一个二级指针，指向的是保存被删除哈希元素的下一个元素地址的指针变量。 > 比如：hth_table[0]中保存着被删除元素的地址，hth_table[3]中保存着被删除元素的下一个元素地址，则该函数会删除hth_table[0]所指向元素的地址，并返回的hth_table[3]的地址信息。
两个删除操作均不会进行被删除元素的内存释放操作：
INT_MAP_HT_REMOVE返回被删除元素的地址，可通过返回值释放内存。INT_MAP_HT_NEXT_RMV需要在删除前保存被删除元素的地址信息，然后在删除操作之后释放内存。
参数检查
static inline void INT_MAP_HT_FOREACH_FN(struct INT_MAP *head, int (*fn)(struct Node *, void *), void *data) { unsigned idx; struct Node **p, **nextp, *next; if (!head->hth_table) return; for (idx=0; idx < head->hth_table_length; ++idx) { p = &head->hth_table[idx]; while (*p) { nextp = &(*p)->map_node.hte_next; next = *nextp; if (fn(*p, data)) { --head->hth_n_entries; *p = next; } else p = nextp; } } }
调用 fn 函数检查每个哈希表中的元素，如果 fn 函数返回值非 0，则删除对应的元素。
注：如有需要，
fn函数中应对被删除元素进行内存释放
销毁
void INT_MAP_HT_CLEAR(struct INT_MAP *head) { if (head->hth_table) free(head->hth_table); INT_MAP_HT_INIT(head); }
该函数需要在哈希表清空后使用，否则会丢失哈希表中元素信息，导致一些 malloc 的空间无法释放，例如：
/* 自定义函数，非 libenent 宏定义生成函数 */ void INT_MAP_HT_CLEAR_ALL(struct INT_MAP * head) { struct Node **ent, **next, *this; for (ent = HT_START(INT_MAP, head); ent; ent = next) { this = *ent; next = HT_NEXT_RMV(INT_MAP, head, ent); mm_free(this); } HT_CLEAR(INT_MAP, head); }
扩容
static unsigned INT_MAP_PRIMES[] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741 }; static unsigned INT_MAP_N_PRIMES = (unsigned)(sizeof(INT_MAP_PRIMES)/sizeof(INT_MAP_PRIMES[0])); int INT_MAP_HT_GROW(struct INT_MAP *head, unsigned size) { unsigned new_len, new_load_limit; int prime_idx; struct Node **new_table; if (head->hth_prime_idx == (int)INT_MAP_N_PRIMES - 1) return 0; if (head->hth_load_limit > size) return 0; prime_idx = head->hth_prime_idx; do { new_len = INT_MAP_PRIMES[++prime_idx]; new_load_limit = (unsigned)(0.5*new_len); /* 0.5 为装载因子 */ } while (new_load_limit <= size && prime_idx < (int)INT_MAP_N_PRIMES); if ((new_table = malloc(new_len*sizeof(struct Node*)))) { unsigned b; memset(new_table, 0, new_len*sizeof(struct Node*)); for (b = 0; b < head->hth_table_length; ++b) { struct Node *elm, *next; unsigned b2; elm = head->hth_table[b]; while (elm) { next = elm->map_node.hte_next; b2 = ((elm)->map_node.hte_hash) % new_len; elm->map_node.hte_next = new_table[b2]; new_table[b2] = elm; elm = next; } } if (head->hth_table) free(head->hth_table); head->hth_table = new_table; } else { unsigned b, b2; new_table = realloc(head->hth_table, new_len*sizeof(struct Node*)); if (!new_table) return -1; memset(new_table + head->hth_table_length, 0, (new_len - head->hth_table_length)*sizeof(struct Node*)); for (b = 0; b < head->hth_table_length; ++b) { struct Node *e, **pE; for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { b2 = ((e)->map_node.hte_hash) % new_len; if (b2 == b) pE = &e->map_node.hte_next; else { *pE = e->map_node.hte_next; e->map_node.hte_next = new_table[b2]; new_table[b2] = e; } } } head->hth_table = new_table; } head->hth_table_length = new_len; head->hth_prime_idx = prime_idx; head->hth_load_limit = new_load_limit; return 0; }
哈希表的扩容分为以下几个步骤：
- 根据装载因子、当前容量、当前数据量判断是否需要扩容
- 获取当前容量等级并计算需要扩容的等级
- 申请新的哈希表空间
- 重建哈希表，并释放旧空间
- 更新哈希表头信息
libevent采用的扩容方法方法的缺点是，容量扩张是一次完成的，期间要花很长时间一次转移hash表中的所有元素。这样在 hash 表每次扩容时，往里边插入一个元素将会等候很长的时间。