哈希表结构 -- ngx_hash_t

2015-09-17 23:21:03   最后更新: 2015-09-20 23:41:26   访问数量:1095




哈希表又称散列表,在一些合理假设下,对任意元素的检索、插入时间复杂度的期望时间都是 O(1),因此他非常适合频繁读取、插入、删除元素的应用场景

而 nginx 作为一个高性能的 web 服务器,对数据的频繁读取、删除、插入的需求是很大的,而为了增加效率与灵活性,nginx 提供了基于通配符的哈希表

 

哈希表是一个基础的数据结构,众所周知,数组的随机访问效率是最高的,原因是数组的随机访问可以通过索引直接定位到数据的实际地址,而无需遍历数组实现,这正是哈希表的思想,而数组也可以看成是索引为数字的特殊哈希表

哈希表实现了给定索引,直接计算出被索引数据存储地址的功能,这个过程是通过两次映射实现的:

  1. 给定索引数据 k,通过一个映射函数 f(k) 计算出实际的 key 值
  2. 通过计算出的 key 值在 info 数组中直接得到偏移

 

即:

k ----> f(k) ----> info[f(k)]

 

上述过程中,f(k) 就是哈希函数,info 数组就是哈希表

 

在理想状态下,k 与 key 是一一对应的,且 info 数组中不存在空元素,而实际情况往往是无法做到的

两个不同的 k 经过 f(k) 得到了相同的 key 的情况就称为哈希碰撞,解决碰撞有三种思路:

  1. 开放地址法
  2. 再哈希法
  3. 链地址法

 

nginx 采用的是链地址法,通过分桶的方式解决冲突的情况

在逻辑上,nginx 的哈希表是一个二维数组,这个数组的大小受两个因素影响:桶的大小和桶的个数

 

需要注意的是 nginx 的哈希表一经初始化就不可更改,既不能增加元素,也不能删除元素

正是因为这个特性,所以可以预先知道所有元素的偏移,因此采用链地址法可以有效解决冲突问题,同时使用数组来代替链表解决冲突则是更优的选择

 

nginx 使用的是 BKDR 哈希算法:

#define ngx_hash(key, c) ((ngx_uint_t) key * 31 + c) // ngx_uint_t ngx_hash_key(u_char *data, size_t len) // 哈希函数,获取 key 对应的哈希 key 值 {{{ ngx_uint_t ngx_hash_key(u_char *data, size_t len) { ngx_uint_t i, key; key = 0; // 计算hash_key for (i = 0; i < len; i++) { key = ngx_hash(key, data[i]); } return key; } // }}} // ngx_uint_t ngx_hash_key_lc(u_char *data, size_t len) // 哈希函数,获取 key 对应的哈希 key 值(不区分大小写) {{{ ngx_uint_t ngx_hash_key_lc(u_char *data, size_t len) { ngx_uint_t i, key; key = 0; // 计算hash_key for (i = 0; i < len; i++) { key = ngx_hash(key, ngx_tolower(data[i])); } return key; } // }}} // ngx_uint_t ngx_hash_strlow(u_char *dst, u_char *src, size_t n) // 哈希函数,将 src 转换为小写存入 dst 指向的地址内 // 返回 dst 对应的哈希 key 值 {{{ // 实现了不区分大小写的哈希函数,同时计算 data 对应的全小写版本 ngx_uint_t ngx_hash_strlow(u_char *dst, u_char *src, size_t n) { ngx_uint_t key; key = 0; while (n--) { *dst = ngx_tolower(*src); key = ngx_hash(key, *dst); dst++; src++; } return key; } // }}}

 

 

nginx 实现了上述三个哈希函数,分别用来计算区分/不区分大小写的 hash key 值,同时,在 ngx_hash_strlow 中,全小写的 data 值使用值-结果参数 dst 返回

key 则放在 names[n].key_hash % size 的桶中,name 就是下面即将要介绍的 ngx_hash_key_t 类型数组,也就是哈希函数计算结果对 size 取余

 

上面提到了,nginx 的哈希表实际上是一个二维数组,他采用开放地址法通过分桶解决冲突问题,因此,nginx 采用了两层结构实现哈希表:

// struct ngx_hash_t // 哈希表结构 {{{ typedef struct { ngx_hash_elt_t **buckets; // 哈希桶数组 ngx_uint_t size; // buckets 数组长度 } ngx_hash_t; // }}}

 

 

buckets 是一个指向 ngx_hash_elt_t 数组的指针,由他构成了一个 ngx_hash_elt_t 为元素的二维数组,每一维的长度则由它指向的 ngx_hash_elt_t 数组来决定

// struct ngx_hash_elt_t // 哈希桶结构 {{{ typedef struct { void *value; // 为 null 代表该元素为当前bucket最尾元素 u_short len; // key 长度 u_char name[1]; // key 的值 } ngx_hash_elt_t; // }}}

 

 

哈希表所有的 key、value 则存储在哈希表索引结构 ngx_hash_key_t 中,用于在哈希表创建时提供数据

// struct ngx_hash_key_t // 哈希表索引结构 {{{ typedef struct { ngx_str_t key; // 索引 ngx_uint_t key_hash; // 索引指向的哈希值 void *value; // 内容 } ngx_hash_key_t; // }}}

 

 

// 哈希表创建时指定的哈希函数 typedef ngx_uint_t (*ngx_hash_key_pt) (u_char *data, size_t len); // struct ngx_hash_init_t // 哈希表创建限制结构 {{{ typedef struct { ngx_hash_t *hash; // 用于管理哈希表的结构体 ngx_hash_key_pt key; // 哈希函数 ngx_uint_t max_size; // 哈希桶个数最大值 ngx_uint_t bucket_size; // 哈希桶大小 char *name; // 哈希表名字 ngx_pool_t *pool; // 哈希表所使用的内存池 ngx_pool_t *temp_pool; // 估算时临时使用的内存池 } ngx_hash_init_t; // }}}

 

 

这个结构中不仅定义了即将要创建的哈希表桶的最大个数和桶大小的限制,还有指定的哈希函数、用于分配哈希表的内存池等创建哈希表所必需的属性资源

哈希表的创建工作正是围绕这个结构体展开的

 

// ngx_int_t // ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) // 创建哈希表 {{{ ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) { u_char *elts; size_t len; u_short *test; ngx_uint_t i, n, key, size, start, bucket_size; ngx_hash_elt_t *elt, **buckets; // 检查names数组的每一个元素,判断桶的大小是否足够分配 for (n = 0; n < nelts; n++) { // 哈希桶大小不足 if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) { ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, "could not build the %s, you should " "increase %s_bucket_size: %i", hinit->name, hinit->name, hinit->bucket_size); return NGX_ERROR; } } // 临时用于保存 hash 数据的空间 test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log); if (test == NULL) { return NGX_ERROR; } bucket_size = hinit->bucket_size - sizeof(void *); start = nelts / (bucket_size / (2 * sizeof(void *))); start = start ? start : 1; if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) { start = hinit->max_size - 1000; } for (size = start; size <= hinit->max_size; size++) { ngx_memzero(test, size * sizeof(u_short)); for (n = 0; n < nelts; n++) { if (names[n].key.data == NULL) { continue; } // 计算 key 哈希函数计算结果对 size 取余,得到桶编号 key = names[n].key_hash % size; // 计算每个 name 的长度并保存在 test[key] 中 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); #if 0 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "%ui: %ui %ui \"%V\"", size, key, test[key], &names[n].key); #endif // 若超出桶大小则到下一桶重新计算 if (test[key] > (u_short) bucket_size) { goto next; } } goto found; next: continue; } size--; // 说明任何桶都不够容纳下某个 name ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0, "could not build optimal %s, you should increase " "either %s_max_size: %i or %s_bucket_size: %i; " "ignoring %s_bucket_size", hinit->name, hinit->name, hinit->max_size, hinit->name, hinit->bucket_size, hinit->name); found: for (i = 0; i < size; i++) { test[i] = sizeof(void *); } for (n = 0; n < nelts; n++) { if (names[n].key.data == NULL) { continue; } key = names[n].key_hash % size; test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); } len = 0; // 让 test[i] 存储对应数据的大小 + sizeof(void *) for (i = 0; i < size; i++) { if (test[i] == sizeof(void *)) { continue; } test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size)); len += test[i]; } if (hinit->hash == NULL) { // 为哈希结构在内存池中分配空间 hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t) + size * sizeof(ngx_hash_elt_t *)); if (hinit->hash == NULL) { ngx_free(test); return NGX_ERROR; } buckets = (ngx_hash_elt_t **) ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t)); } else { buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *)); if (buckets == NULL) { ngx_free(test); return NGX_ERROR; } } // 分配整块内存用于存储完整的哈希表结构并对齐 elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size); if (elts == NULL) { ngx_free(test); return NGX_ERROR; } elts = ngx_align_ptr(elts, ngx_cacheline_size); // 将整块连续内存打散成每个桶 for (i = 0; i < size; i++) { if (test[i] == sizeof(void *)) { continue; } buckets[i] = (ngx_hash_elt_t *) elts; elts += test[i]; } for (i = 0; i < size; i++) { test[i] = 0; } // 将传进来的每一个hash数据存入hash表 for (n = 0; n < nelts; n++) { if (names[n].key.data == NULL) { continue; } // 为即将存入的数据分配空间 key = names[n].key_hash % size; elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]); // 存入数据 elt->value = names[n].value; elt->len = (u_short) names[n].key.len; ngx_strlow(elt->name, names[n].key.data, names[n].key.len); // 存储下一个要被存入的长度偏移 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); } for (i = 0; i < size; i++) { if (buckets[i] == NULL) { continue; } elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]); elt->value = NULL; } ngx_free(test); hinit->hash->buckets = buckets; hinit->hash->size = size; #if 0 for (i = 0; i < size; i++) { ngx_str_t val; ngx_uint_t key; elt = buckets[i]; if (elt == NULL) { ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "%ui: NULL", i); continue; } while (elt->value) { val.len = elt->len; val.data = &elt->name[0]; key = hinit->key(val.data, val.len); ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "%ui: %p \"%V\" %ui", i, elt, &val, key); elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, sizeof(void *)); } } #endif return NGX_OK; } // }}}

 

 

这个函数通过预先已经存储了所有数据的 ngx_hash_key_t 结构和存储限制条件的 ngx_hash_init_t 结构创建了 hinit->hash 的 ngx_hash_t 结构

在这个函数中首先进行了限制条件的校验,保证空间足够,然后他通过循环,计算了每个数据的大小和偏移,最终将哈希表创建在内存池中一块连续的内存中

 

初始化完成后整个结构如下图所示

 

 

// void * // ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len) // 通过 key 查找对应的哈希值 {{{ void * ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len) { ngx_uint_t i; ngx_hash_elt_t *elt; #if 0 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name); #endif elt = hash->buckets[key % hash->size]; if (elt == NULL) { return NULL; } while (elt->value) { if (len != (size_t) elt->len) { goto next; } for (i = 0; i < len; i++) { if (name[i] != elt->name[i]) { goto next; } } return elt->value; // 有碰撞则查找相邻的下一元素 next: elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, sizeof(void *)); continue; } return NULL; } // }}}

 

 

这段代码很好理解,首先通过上面说的 key % size 得到桶数组序号,然后通过 buckets 指针获取桶数组首地址,然后遍历对应的桶数组,最终返回查询结果

 






技术帖      linux      web      算法      c语言      数据结构      struct      龙潭书斋      nginx      server      opensource      sourcecode      webserver      hash      source      hashtable      ngx_hash_t     


京ICP备15018585号