博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
NGINX(三)HASH表
阅读量:5846 次
发布时间:2019-06-18

本文共 8225 字,大约阅读时间需要 27 分钟。

前言

nginx的hash表有几种不同的种类, 不过都是以ngx_hash_t为基础的, ngx_hash_t是最普通的hash表, 冲突采用的是链地址法, 不过这里冲突的元素不是一个链表, 而是一个数组, 为了加快访存速度,这种hash表只用于存储一些静态的信息, 例如所有头部信息, 配置信息等等.

涉及数据结构

/*hash元素数据结构包含key和value*/typedef struct {    /*hash值*/    void             *value;    /*hash表原始key的长度, 即name长度*/    u_short           len;    /*name即原始的key值*/    u_char            name[1];} ngx_hash_elt_t;/*普通hash表*/typedef struct {    /*hash元素*/    ngx_hash_elt_t  **buckets;    /*hash表中元素数量*/    ngx_uint_t        size;} ngx_hash_t;/*hash表中key数据结构, 主要用于传递一个hash时使用*/typedef struct {    /*原始key值*/    ngx_str_t         key;    /*hash函数计算过key值*/    ngx_uint_t        key_hash;    /*hash表中value值*/    void             *value;} ngx_hash_key_t;typedef ngx_uint_t (*ngx_hash_key_pt) (u_char *data, size_t len);/*普通hash表初始化函数*/typedef struct {    /*hash表指针*/    ngx_hash_t       *hash;    /*未使用*/    ngx_hash_key_pt   key;        /*hash表中容纳最大元素数量*/    ngx_uint_t        max_size;    /*hash表中桶的大小, 即容纳一个元素ngx_hash_elt_t大小*/    ngx_uint_t        bucket_size;        /*hash表名字*/    char             *name;    /*内存池用于固定不变的一些数据结构使用*/    ngx_pool_t       *pool;    /*临时的内存池,由于内存池中内存是在内存池销毁时统一释放,因此这里对于临时变量使用*/    ngx_pool_t       *temp_pool;} ngx_hash_init_t;

hash表初始化

初始化hash结构, nginx的hash将内存分为一系列桶, 每个桶内放置一个元素或者是所有冲突的元素, 下面是hash存储的示意图, hash表初始化时, 首先确定每个桶的大小, 其次确定hash表长度, 最后把传进函数中的数据, 按照规则放入hash表中.

hash表分布示意图|-----一个桶大小bucket_size-----|-----一个桶大小bucket_size-----|-----一个桶大小bucket_size-----|-----一个桶大小bucket_size-----|........|--------key_hash%size=0--------|--------key_hash%size=1--------|---------key_hash%size=2-------|--------key_hash%size=3--------|........|------------------|--------|...|------------------|--------|...|------------------|--------|...|------------------|--------|...|........0  ngx_hash_elt_t     len     | 1  ngx_hash_elt_t      len    | 2  ngx_hash_elt_t      len      3  ngx_hash_elt_t      len      4........                              |                               |                    ........                  |                               |                    ........                  取余为0的冲突元素依次放入桶内        取余为1的冲突元素           ........
/*计算桶中元素ngx_hash_elt_t大小, ngx_hash_elt_t结构体长度是可变的, 最后一个成员name[1], C语言惯用的手法, 可以让结构体本身和保存的数据连接在一起, 只是一个 *占位指针, 有时候我们定义为name[0], 因此长度也就是sizeof(value) + sizeof(u_short) + sizeof(name) + len, 但是我们看到下面并不是像我们计算的这样,  *由于sizeof(u_short) + sizeof(name)值肯定小于sizeof(void*), 结构体进行内存对齐时, 以成员最长长度进行对齐, 因此以sizeof(void*)进行对齐, 2代表的是sizeof(u_short).  */#define NGX_HASH_ELT_SIZE(name)                                               \    (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
ngx_hash_elt_t分布示意图|------------------------------|---------------|----------------------|           sizeof(void*)        sizeof(u_short)     长度为len的name(name只是一个占位指针)
ngx_int_tngx_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;    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;        }    }    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 *);        /*预估hash表大小, 这里以ngx_hash_elt_t为最小8字节进行计算*/    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 = names[n].key_hash % size;            /*累加冲突元素的长度*/            test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));            /*元素大小大于桶大小, 累加size值, 重新进行分配*/            if (test[key] > (u_short) bucket_size) {                goto next;            }        }        goto found;    next:        continue;    }    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;    /*计算所有元素总长度*/    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];    }        /*hash表为size个桶分配内存,保存所有桶的指针*/    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;        }    }        /*整个hash表分配内存*/    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表中*/    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]));    }        /*hash表中空缺的位置置空*/    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;    return NGX_OK;}

hash表查找

了解了hash表存储结构, 从hash表中查找元素变得简单多了, 首先取出元素对应的桶, 然后依次比较name是否相等, 相等则返回对应值value

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;    /*取出元素对应的桶位置*/    elt = hash->buckets[key % hash->size];    if (elt == NULL) {        return NULL;    }    while (elt->value) {        if (len != (size_t) elt->len) {            goto next;        }                /*比较对应的name值*/        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;}

转载于:https://www.cnblogs.com/ourroad/p/4844860.html

你可能感兴趣的文章
介绍2个免费生成手机端软件的网站
查看>>
Objective-C的算术表达式 .
查看>>
RPC failed; result=28, HTTP code = 0
查看>>
gcc编译C++程序
查看>>
linux中nfs的自动挂载
查看>>
统一关闭域客户端防火墙服务/功能
查看>>
expandablelistview open group scroll to top
查看>>
Android通过Aidl调用Service实例
查看>>
找回使用Eclipse删除的文件
查看>>
rabbitmq 消息系统 消息队列
查看>>
Intellij IDEA神器居然还有这些小技巧
查看>>
HBase基本原理
查看>>
php使用qr生成二维码
查看>>
集成spring3、hibernate4、junit
查看>>
eclipse常用快捷键
查看>>
URL与ASCII
查看>>
Jetty9安装部署
查看>>
OpenGL的视图变换
查看>>
Redis.conf 说明
查看>>
shell-用grep查看输入的参数是否在/etc/passwd中
查看>>