摘要：本篇的上篇為源碼分析上。主體思路分析中使用的哈希函數(shù)，圍繞初始化時使用的結(jié)構(gòu)體展開。這樣得到一個關(guān)于請求的首部哈希數(shù)組。源碼中大多數(shù)的代碼是跟預(yù)估表大小相關(guān)的。的哈希表的核心是表的管理結(jié)構(gòu)體數(shù)組及表內(nèi)存空間分配。

本篇的上篇為 Nginx 源碼分析：ngx_hash_t（上）。
建議先讀完上篇再來讀下篇。

上篇回顧了hash表的基礎(chǔ)概念，分析了Nginx中hash表的內(nèi)存模型及邏輯模型，從而引出了其核型數(shù)據(jù)結(jié)構(gòu)ngx_hash_elt_t和ngx_hash_t，并從設(shè)計的角度解釋了如何初始化這兩個結(jié)構(gòu)體。

本篇主要分析，在Nginx源碼中是如何初始化這兩個結(jié)構(gòu)體的。

分析Nginx中使用的哈希函數(shù)，圍繞初始化時使用的ngx_hash_key_t結(jié)構(gòu)體展開。

分析Nginx如何估算所需內(nèi)存大小，如何分配內(nèi)存。

相信仔細(xì)看過上篇后，對這兩個問題已經(jīng)心里有底了。

上篇說過，Nginx中hash表是只讀的，因此，可以提前對需要多大的內(nèi)存進(jìn)行預(yù)估。
在Nginx中，提前將索引值、對應(yīng)hash值，及內(nèi)容計算出來，放入一個ngx_hash_key_t結(jié)構(gòu)體中。

typedef struct {
    ngx_str_t         key;        // 索引值
    ngx_uint_t        key_hash;   // 對應(yīng)hash值
    void             *value;      // 內(nèi)容
} ngx_hash_key_t;

那么，如何計算一個字符串key的哈希值呢？答案是哈希函數(shù)。
Nginx提供的哈希函數(shù)有兩個：

#define ngx_hash(key, c)   ((ngx_uint_t) key * 31 + c)

ngx_uint_t
ngx_hash_key(u_char *data, size_t len)
{
    ngx_uint_t  i, key;

    key = 0;

    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)
{
    ngx_uint_t  i, key;

    key = 0;

    for (i = 0; i < len; i++) {
        key = ngx_hash(key, ngx_tolower(data[i]));
    }

    return key;
}

其中ngx_hash_key_lc是大小寫無關(guān)，ngx_hash_key是大小寫相關(guān)的。

一般情況下，我們會得到一個ngx_hash_key_t的數(shù)組。
例如HTTP請求的通用首部：

Host:
Connection:
User-Agent:
...

每一條首部對應(yīng)一個ngx_hash_key_t。這樣得到一個關(guān)于HTTP請求的首部哈希數(shù)組。

有了這些信息，就可以提前預(yù)估根據(jù)這個數(shù)組生成的哈希表究竟需要多大的內(nèi)存。

關(guān)于Nginx的哈希表，上篇提到過兩點(diǎn)：

1）Nginx的哈希表本身是向ngx_pool_t申請的一塊連續(xù)的內(nèi)存，因此初始化哈希表需要知道ngx_pool_t。
2）Nginx的哈希表解決哈希沖突采用了hash桶的辦法，因此，在邏輯上，哈希表是一個二維數(shù)組。這個數(shù)組的大小受兩個因素影響：桶的大小和桶的個數(shù)。

一般來講，桶的個數(shù)越大，所需要桶的大小越小。

因此，這個在初始化時預(yù)先對內(nèi)存進(jìn)行估計的結(jié)構(gòu)體ngx_hash_init_t是長成這個樣子的：

typedef ngx_uint_t (*ngx_hash_key_pt) (u_char *data, size_t len);

typedef struct {
    ngx_hash_t       *hash;            // 用于管理哈希表的結(jié)構(gòu)體
    ngx_hash_key_pt   key;             // 哈希函數(shù)

    ngx_uint_t        max_size;        // 哈希桶個數(shù)的最大值
    ngx_uint_t        bucket_size;     // 哈希桶的大小

    char             *name;            // 哈希表的名字
    ngx_pool_t       *pool;            // 使用的內(nèi)存池
    ngx_pool_t       *temp_pool;       // 估算時臨時使用的內(nèi)存池
} ngx_hash_init_t;

其中*hash用于指向創(chuàng)建的哈希表管理結(jié)構(gòu)體ngx_hash_t，當(dāng)這個值為NULL時，在完成初始化時，回從內(nèi)存池中獲取一塊內(nèi)存。

max_size是限制生成的哈希表中桶的個數(shù)上限制。這個值越大，桶的大小越小，因此沖突項(xiàng)越少，查詢速度更快，但是浪費(fèi)的內(nèi)存會增多。

bucket_size用來限制每個桶的大小上限值。

這兩個參數(shù)是給哈希表生成時提供一個上限參考，并不是哈希表生成的最終大小。

鋪墊了這么久，終于進(jìn)入正題。-_-!!

Nginx的哈希表生成函數(shù)聲明如下：

ngx_int_t 
ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,ngx_uint_t nelts);

其中，*hinit是初始化的限制條件，詳見上一小節(jié)的說明；
*names是Nginx根據(jù)索引值，提前算出來的哈希值數(shù)組，詳見上上一小節(jié)；
nelts是*names數(shù)組的大小。

總體來說：這個函數(shù)做了三件事情：

根據(jù)輸入的ngx_hash_key_t結(jié)構(gòu)體數(shù)組及ngx_hash_init_t結(jié)構(gòu)體，估算出hash表所需的hash桶的個數(shù)及每個hash桶的大?。?/p>

根據(jù)算出的hash桶的個數(shù)及hash桶的大小，向內(nèi)存池中申請空間；

將ngx_hash_key_t數(shù)組的內(nèi)容裝入生成的hash表中。

因?yàn)?b>ngx_hash_init的函數(shù)定義很長，為了更好的說明問題，我按照次序撿取主要內(nèi)容一段一段拆開來分析。感興趣的可以看Ngx_hash.c的源碼完整版

首先，對傳入的hinit及names中的bucket_size大小進(jìn)行校驗(yàn)。
條件是，hinit中的bucket_size >= sizeof(ngx_hash_elt_t)

#define ngx_align(d, a)     (((d) + (a - 1)) & ~(a - 1))

#define NGX_HASH_ELT_SIZE(name)                                               
    (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))

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;
        }
    }

可以看到，NGX_HASH_ELT_SIZE的最小值為 sizeof(void*) + sizeof(void*)，因此bucket_size的最小值是兩個指針的大小。

這里需要解釋一下ngx_align(d,a)這個宏的作用：將d取a的向上整數(shù)倍。例如，b=5，a=4，那么ngx_align(5,4)的結(jié)果就是8。

在實(shí)現(xiàn)原理上，利用了二進(jìn)制計算的技巧。這里稍微講一下（已經(jīng)懂的可以跳過）：

===========我是華麗的分割線===============
當(dāng)a為2的某個冪的值時（例如a=2^2=4，或a=2^3=8），有以下特點(diǎn)：

a = 4:  二進(jìn)制： 0000 0100       從右起，第三位為1，剩下全為0;
a = 8:  二進(jìn)制： 0000 1000       從右起，第四位為1, 剩下全為0；
a = 16: 二進(jìn)制:  0001 0000       從右起，第五位為1，剩下全為0；

a - 1 = 3:  二進(jìn)制： 0000 0011   從右起，第三位之前，全是1；
a - 1 = 7:  二進(jìn)制： 0000 0111   從右起，第四位之前，全是1；
a - 1 = 15: 二進(jìn)制： 0000 1111   從右起，第五位之前，全是1；

~(a - 1) = ~3:  二進(jìn)制： 1111 1100   從右起，第二位之后，全是1；
~(a - 1) = ~7:  二進(jìn)制： 1111 1000   從右起，第三位之后，全是1；
~(a - 1) = ~15: 二進(jìn)制： 1111 0000   從右起，第四位之后，全是1；

(理解的關(guān)鍵點(diǎn))一個數(shù)，一定是這個數(shù)的二進(jìn)制從右起第一個不為零的位所表示的數(shù)的整數(shù)倍
比如：

a = 12:  二進(jìn)制： 0000 1100 
從右起，第一個不為零的位所表示的整數(shù)為 0000 0100 即 4
那么，a = 12 一定是 4 的整數(shù)倍

如果，我們需要任意的一個數(shù)a對4取整怎么辦呢？很簡單，只需要把a從右起的若干位置0就可以了。
比如：

a = 13: 二進(jìn)制：0000 1101
向0000 0100 即 4 取整，只需要將 0000 1101從右起，前兩位置0，即可得到，0000 1100 即12

這個置0的過程可以表達(dá)為0000 1101 &  1111 1100
而 1111 1100 = ~(4 - 1)，因此，13 對 4 取整的二進(jìn)制運(yùn)算即為：13 & ~(4 - 1)

可以看到，這樣的二進(jìn)制運(yùn)算的結(jié)果是向下取整數(shù)倍。
但是，在申請內(nèi)存時，只能比需求的大，而不能比需求的小，因此需要向上取整數(shù)倍：

對于一個任意的數(shù)d和一個2的任意次冪a：
d對a向下取整的二進(jìn)制運(yùn)算為：d & ~(a -1)
d對a向上取整的二進(jìn)制運(yùn)算為：(d + (a - 1)) & ~(a - 1)

相信到這里，已經(jīng)可以很容易理解ngx_align這個宏的含義了

#define ngx_align(d, a)     (((d) + (a - 1)) & ~(a - 1))

===========我是華麗的分割線===============

準(zhǔn)備工作

現(xiàn)在我們手頭上有所有索引值及其對應(yīng)的hash值所組成的ngx_hash_key_t數(shù)組，這個數(shù)組的大小表示將來形成的hash表中有效元素的數(shù)目。

那么，可知，hash桶數(shù)目 * 每個hash桶能放置元素的個數(shù) > ngx_hash_key_t 數(shù)組大小

從上一小節(jié)的分析可知：bucket_size的最小值為2 * sizeof(void*)，那么，預(yù)設(shè)的ngx_hash_init_t中的bucket_size / 2 * sizeof(void*)就能得到每個桶所能放置的沖突項(xiàng)的個數(shù)最大值。

因此，ngx_hash_key_t的數(shù)組的大小值nelts / (bucket_size / 2 * sizeof(void*))就是預(yù)估的hash表所需hash桶數(shù)目的最小值。

因此，接下來Nginx有這么一段：

    bucket_size = hinit->bucket_size - sizeof(void *);
    // start 為預(yù)估hash桶數(shù)目的最小值，因?yàn)闀S著計算不斷向上增加，所以命名為start
    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;
    }

這部分代碼可以看作是在估算hash表中hash桶數(shù)目的最小值的合理值。

開始估算
ngx_hash_key_t數(shù)組中含有所有索引值及其對應(yīng)的哈希值，為了將hash表的hash桶數(shù)目控制在一定數(shù)量內(nèi)，需要對ngx_hash_key_t內(nèi)的哈希值進(jìn)行取模運(yùn)算。

取模運(yùn)算會將結(jié)果控制在一定整數(shù)范圍內(nèi)。
比如：key_hash % size，表示運(yùn)算得到的結(jié)果一定在[0, size)區(qū)間內(nèi)。

這樣，對于上述代碼得到的start，我們就可以從start開始到hinit->max_size結(jié)束，挨個嘗試，看看每個start所算出的bucket_size是否符合要求（<= hinit->bucket_size）

代碼如下：

// 從start 開始，到hints->max_size為止，挨個嘗試
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;
            }
            // 取模運(yùn)算，將hash值控制在當(dāng)前size范圍內(nèi)
            key = names[n].key_hash % size;
            // 累加計算每個hash值對應(yīng)的沖突項(xiàng)占用的hash桶空間
            test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
            // 當(dāng)某個hash值所有沖突項(xiàng)占用的hash桶空間超過上限，
            // 表示當(dāng)前hash桶個數(shù)設(shè)置太小，進(jìn)入下一輪循環(huán)
            if (test[key] > (u_short) bucket_size) {
                goto next;
            }
        }
        // 找到合適的hash桶個數(shù)，接下來進(jìn)入申請空間及初始化結(jié)構(gòu)體階段
        goto found;

    next:

        continue;
    }

當(dāng)代碼運(yùn)行到goto found時，表示找到合適的hash桶數(shù)目，可以進(jìn)入下一階段：申請內(nèi)存空間及初始化結(jié)構(gòu)體了。

根據(jù)上一篇文章對于ngx_hash_t內(nèi)存的描述，可知需要申請的內(nèi)存空間分成兩部分：

1）用于管理hash表的ngx_hash_t結(jié)構(gòu)體，及用于指向內(nèi)存不同分組的ngx_hash_elt_t *數(shù)組。根據(jù)上一小節(jié)的估算，ngx_hash_elt_t *數(shù)組的大小為size。
2）用于存放hash表的連續(xù)內(nèi)存塊，其大小為所有hash桶占用空間的總和。

這部分的源代碼如下：

    // 清空上次為了估算hash桶數(shù)目所存儲在test中的數(shù)據(jù)
    for (i = 0; i < size; i++) {
        test[i] = sizeof(void *);
    }
    // 重新計算各個hash值所占用的內(nèi)存空間
    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;
    // 將所有hash值占用的內(nèi)存空間加和，得到總共需要的內(nèi)存空間len
    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];
    }

對所有的ngx_hash_key_t重新計算了一遍，得到了存放所有數(shù)據(jù)需要的內(nèi)存空間len

然后，就可以向ngx_pool_t內(nèi)存池申請空間了。

if (hinit->hash == NULL) {
        // 在堆上創(chuàng)建hash管理結(jié)構(gòu)體ngx_hash_t，及ngx_hash_elt_t*
        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;
        }
        // 將ngx_hash_t** 指針指向hash桶管理結(jié)構(gòu)體
        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;
        }
    }
    // 向內(nèi)存池申請hash表所使用的內(nèi)存空間
    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);

這段代碼的邏輯分成兩部分：

1）向內(nèi)存池申請管理hash表的結(jié)構(gòu)體所使用的內(nèi)存空間，包括ngx_hash_t結(jié)構(gòu)體及ngx_hash_elt_t*指針數(shù)組。
2）向內(nèi)存池申請hash表所使用的內(nèi)存空間，直接使用之前計算的len申請。當(dāng)然，Nginx的源碼中為了效率，進(jìn)行了對齊操作。

OK， 有了管理結(jié)構(gòu)體，有了hash表，最后的任務(wù)就是將管理結(jié)構(gòu)體的各個指針指向正確的地址，各個變量賦于正確的值即可。

    // 將ngx_hash_key_t* 數(shù)組指向各個內(nèi)存段
    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表中填入正確的內(nèi)容
    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);

    // hash表管理結(jié)構(gòu)體賦于正確的內(nèi)容
    hinit->hash->buckets = buckets;
    hinit->hash->size = size;

這樣，就完成了初始化hash表的整個工作。

個人經(jīng)驗(yàn)：理解ngx_hash_t的關(guān)鍵點(diǎn)如下：

1）Nginx的哈希表是只讀的，所以采用了預(yù)先估算hash表所需占用內(nèi)存的大小的辦法。源碼中大多數(shù)的代碼是跟預(yù)估hash表大小相關(guān)的。
2）Nginx的哈希表的內(nèi)存空間采用內(nèi)存池管理，因此理解其內(nèi)存模型是理解代碼邏輯的關(guān)鍵。內(nèi)存模型請查看上一篇文章。
3）Nginx的哈希表的核心是hash表的管理結(jié)構(gòu)體ngx_hash_t、ngx_hash_elt_t*數(shù)組、及hash表內(nèi)存空間分配。

個人覺得，Nginx的高效并不是來自于Nginx有什么屠龍大法，而是來自于針對性很強(qiáng)的優(yōu)化，ngx_hash_t就是一個很好的例子。
在ngx_hash_t中，隨處可見各種優(yōu)化，不論是這種特殊的hash表結(jié)構(gòu)設(shè)計，還是內(nèi)存分配上的各種對齊，都很值得學(xué)習(xí)。