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

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

上篇回顧了hash表的基礎概念，分析了Nginx中hash表的內存模型及邏輯模型，從而引出了其核型數據結構ngx_hash_elt_t和ngx_hash_t，并從設計的角度解釋了如何初始化這兩個結構體。

本篇主要分析，在Nginx源碼中是如何初始化這兩個結構體的。

分析Nginx中使用的哈希函數，圍繞初始化時使用的ngx_hash_key_t結構體展開。

分析Nginx如何估算所需內存大小，如何分配內存。

相信仔細看過上篇后，對這兩個問題已經心里有底了。

上篇說過，Nginx中hash表是只讀的，因此，可以提前對需要多大的內存進行預估。
在Nginx中，提前將索引值、對應hash值，及內容計算出來，放入一個ngx_hash_key_t結構體中。

typedef struct {
    ngx_str_t         key;        // 索引值
    ngx_uint_t        key_hash;   // 對應hash值
    void             *value;      // 內容
} ngx_hash_key_t;

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

#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是大小寫無關，ngx_hash_key是大小寫相關的。

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

Host:
Connection:
User-Agent:
...

每一條首部對應一個ngx_hash_key_t。這樣得到一個關于HTTP請求的首部哈希數組。

有了這些信息，就可以提前預估根據這個數組生成的哈希表究竟需要多大的內存。

關于Nginx的哈希表，上篇提到過兩點：

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

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

因此，這個在初始化時預先對內存進行估計的結構體ngx_hash_init_t是長成這個樣子的：

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;            // 哈希表的名字
    ngx_pool_t       *pool;            // 使用的內存池
    ngx_pool_t       *temp_pool;       // 估算時臨時使用的內存池
} ngx_hash_init_t;

其中*hash用于指向創建的哈希表管理結構體ngx_hash_t，當這個值為NULL時，在完成初始化時，回從內存池中獲取一塊內存。

max_size是限制生成的哈希表中桶的個數上限制。這個值越大，桶的大小越小，因此沖突項越少，查詢速度更快，但是浪費的內存會增多。

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

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

鋪墊了這么久，終于進入正題。-_-!!

Nginx的哈希表生成函數聲明如下：

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

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

總體來說：這個函數做了三件事情：

根據輸入的ngx_hash_key_t結構體數組及ngx_hash_init_t結構體，估算出hash表所需的hash桶的個數及每個hash桶的大小；

根據算出的hash桶的個數及hash桶的大小，向內存池中申請空間；

將ngx_hash_key_t數組的內容裝入生成的hash表中。

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

首先，對傳入的hinit及names中的bucket_size大小進行校驗。
條件是，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的向上整數倍。例如，b=5，a=4，那么ngx_align(5,4)的結果就是8。

在實現原理上，利用了二進制計算的技巧。這里稍微講一下（已經懂的可以跳過）：

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

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

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

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

(理解的關鍵點)一個數，一定是這個數的二進制從右起第一個不為零的位所表示的數的整數倍
比如：

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

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

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

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

可以看到，這樣的二進制運算的結果是向下取整數倍。
但是，在申請內存時，只能比需求的大，而不能比需求的小，因此需要向上取整數倍：

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

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

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

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

準備工作

現在我們手頭上有所有索引值及其對應的hash值所組成的ngx_hash_key_t數組，這個數組的大小表示將來形成的hash表中有效元素的數目。

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

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

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

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

    bucket_size = hinit->bucket_size - sizeof(void *);
    // start 為預估hash桶數目的最小值，因為會隨著計算不斷向上增加，所以命名為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桶數目的最小值的合理值。

開始估算
ngx_hash_key_t數組中含有所有索引值及其對應的哈希值，為了將hash表的hash桶數目控制在一定數量內，需要對ngx_hash_key_t內的哈希值進行取模運算。

取模運算會將結果控制在一定整數范圍內。
比如：key_hash % size，表示運算得到的結果一定在[0, size)區間內。

這樣，對于上述代碼得到的start，我們就可以從start開始到hinit->max_size結束，挨個嘗試，看看每個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;
            }
            // 取模運算，將hash值控制在當前size范圍內
            key = names[n].key_hash % size;
            // 累加計算每個hash值對應的沖突項占用的hash桶空間
            test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
            // 當某個hash值所有沖突項占用的hash桶空間超過上限，
            // 表示當前hash桶個數設置太小，進入下一輪循環
            if (test[key] > (u_short) bucket_size) {
                goto next;
            }
        }
        // 找到合適的hash桶個數，接下來進入申請空間及初始化結構體階段
        goto found;

    next:

        continue;
    }

當代碼運行到goto found時，表示找到合適的hash桶數目，可以進入下一階段：申請內存空間及初始化結構體了。

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

1）用于管理hash表的ngx_hash_t結構體，及用于指向內存不同分組的ngx_hash_elt_t *數組。根據上一小節的估算，ngx_hash_elt_t *數組的大小為size。
2）用于存放hash表的連續內存塊，其大小為所有hash桶占用空間的總和。

這部分的源代碼如下：

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

然后，就可以向ngx_pool_t內存池申請空間了。

if (hinit->hash == NULL) {
        // 在堆上創建hash管理結構體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桶管理結構體
        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);

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

1）向內存池申請管理hash表的結構體所使用的內存空間，包括ngx_hash_t結構體及ngx_hash_elt_t*指針數組。
2）向內存池申請hash表所使用的內存空間，直接使用之前計算的len申請。當然，Nginx的源碼中為了效率，進行了對齊操作。

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

    // 將ngx_hash_key_t* 數組指向各個內存段
    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]));
    }

    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表管理結構體賦于正確的內容
    hinit->hash->buckets = buckets;
    hinit->hash->size = size;

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

個人經驗：理解ngx_hash_t的關鍵點如下：

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

個人覺得，Nginx的高效并不是來自于Nginx有什么屠龍大法，而是來自于針對性很強的優化，ngx_hash_t就是一個很好的例子。
在ngx_hash_t中，隨處可見各種優化，不論是這種特殊的hash表結構設計，還是內存分配上的各種對齊，都很值得學習。