1. 思想

ngx的hash更确切的描述是使用散列实现的表，在构建表时将数据按照 key,value 的方式录入表，查表时按照key返回value.

ngx的hash用表项在运行前已经确定，所以可以确定整个表占用的最小空间。

对于表项动态变化，ngx使用 树作为容器

ngx的散列支持通配符，不过这里不考虑

2. 实现

// 桶中元素
// 分为两类：普通元素和哨兵
// 普通元素 value, len ,name 皆有用
// 哨兵：只是用value, value= NULL
typedef struct {
    void             *value;    // value同时做哨兵，所以放在首个
    u_short           len;
    u_char            name[1];
} ngx_hash_elt_t;
// 所有桶
// size : 桶的数量
typedef struct {
    ngx_hash_elt_t  **buckets;
    ngx_uint_t        size;
} ngx_hash_t;

// 辅助结构体，不会保存在 ngx_hash_t中
// key  ，元素的 key
// key_hash,  使用 key 计算出的 key_hash 码
// value 元素的 value
typedef struct {
    ngx_str_t         key;
    ngx_uint_t        key_hash;
    void             *value;
} ngx_hash_key_t;

// 计算key_hash的方法
typedef ngx_uint_t (*ngx_hash_key_pt) (u_char *data, size_t len);
typedef struct {
    ngx_hash_t       *hash;
    ngx_hash_key_pt   key;

    ngx_uint_t        max_size; //最多支持的桶的数量
    ngx_uint_t        bucket_size; // 最多支持的桶的大小 

    char             *name;     // hash名称，本身不会保存到hash桶中，作为调试信息使用
    ngx_pool_t       *pool; 
    ngx_pool_t       *temp_pool;
} ngx_hash_init_t;

void *ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len);
ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
    ngx_uint_t nelts);

typedef struct {
    ...
    ngx_hash_t                 headers_in_hash; 
    ...
} ngx_http_core_main_conf_t;

ngx_http_header_t  ngx_http_headers_in[] = {
    { ngx_string("Host"), offsetof(ngx_http_headers_in_t, host),
                 ngx_http_process_host },

    { ngx_string("Connection"), offsetof(ngx_http_headers_in_t, connection),
                 ngx_http_process_connection },
    ...
};

static ngx_int_t
ngx_http_init_headers_in_hash(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf)
{
    ngx_array_t         headers_in;
    ngx_hash_key_t     *hk;
    ngx_hash_init_t     hash;
    ngx_http_header_t  *header;

    if (ngx_array_init(&headers_in, cf->temp_pool, 32, sizeof(ngx_hash_key_t))
        != NGX_OK)
    {
        return NGX_ERROR;
    }

    for (header = ngx_http_headers_in; header->name.len; header++) {
        hk = ngx_array_push(&headers_in);
        if (hk == NULL) {
            return NGX_ERROR;
        }

        hk->key = header->name;
        hk->key_hash = ngx_hash_key_lc(header->name.data, header->name.len);
        hk->value = header;
    }

    hash.hash = &cmcf->headers_in_hash; // 哈希句柄， 说明hash.hash是输出参数
    hash.key = ngx_hash_key_lc;         // 求key的方法
    hash.max_size = 512;                // 最大能接受的桶的数量
    hash.bucket_size = ngx_align(64, ngx_cacheline_size);   // 每个桶最多能接受的字节数
    hash.name = "headers_in_hash";
    hash.pool = cf->pool;
    hash.temp_pool = NULL;

    if (ngx_hash_init(&hash, headers_in.elts, headers_in.nelts) != NGX_OK) {
        return NGX_ERROR;
    }

    return NGX_OK;
}

关键的是 数组元素类型必须是 ngx_hash_key_t

typedef struct {
    ngx_str_t         key;
    ngx_uint_t        key_hash;
    void             *value;
} ngx_hash_key_t;    

因为 这里的 表项是一旦建立就不会有增删，而ngx为了追求极致的内存使用，会预先计算需要的最小空间

// sizeof(void *) 是 value 成员的空间
// （name)->key.len 是 name的空间
// 2 是 len的空间， u_short
#define NGX_HASH_ELT_SIZE(name)                                               \
    (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))

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;

    // 一个桶至少需要容纳一个元素，所以桶的容量至少 大于 下面的值
    // 还可以看出一个桶 需容纳 n个元素 和 一个void *指针， void *指针做次桶的哨兵
    // 元素空间又 一个 void * 成员 和 一定长度的 char * 组成
    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是测量桶的表, max_size 说明 test 能表示最多使用 max_size个桶
    test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
    if (test == NULL) {
        return NGX_ERROR;
    }
    // 所有桶的大小 减少 sizeof(void *), 对应 下面求桶数量处， 少加一个 sizeof(void *)
    bucket_size = hinit->bucket_size - sizeof(void *);
    
    // nelts * (2*sizeof(void *)) : 所有元素最少使用空间（假设都没有key)）
    // start * bucket_size : start为桶的数量，bucket_size 为单个桶的 容积，所以这个表示所有桶的容积
    // start *bucket_size == nelts * (2*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 = names[n].key_hash % size;
            test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));

            if (test[key] > (u_short) bucket_size) {
                goto next;
            }
        }

        goto found;

    next:

        continue;
    }

    ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
                  "could not build the %s, you should increase "
                  "either %s_max_size: %i or %s_bucket_size: %i",
                  hinit->name, hinit->name, hinit->max_size,
                  hinit->name, hinit->bucket_size);

    ngx_free(test);

    return NGX_ERROR;

found:
    // 找到合适 桶的数量 ： size
    // 重新计算每个桶需要的空间, 因为实际分配空间要考虑对齐
    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];
    }

    // 分配句柄空间
    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;
    }

    // 将所有元素录入桶空间
    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]); // test[key]为该桶已经使用的空间大小，buckets[key]为该桶的起始地址,所以得到桶的下一可用空间的地址，紧密排布

        elt->value = names[n].value;
        elt->len = (u_short) names[n].key.len;              // elt->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;

    return NGX_OK;
}

构建完表后，之后查表方法

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;
        }
        // 没有用 strcmp ，可见ngx在细节的优化
        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;
}