理解 Nginx 源碼之七 哈希表結構 ngx

概述

關於哈希表的基本知識在前面的文章《數據結構-哈希表》已作介紹。哈希表結合了數組和鏈表的特點，使其尋址、插入以及刪除操作更加方便。哈希表的過程是將關鍵字通過某種哈希函數映射到相應的哈希表位置，即對應的哈希值所在哈希表的位置。但是會出現多個關鍵字映射相同位置的情況導致衝突問題，為了解決這種情況，哈希表使用兩個可選擇的方法：

Nginx 的哈希表中使用開放尋址來解決衝突問題，為了處理字符串，Nginx 還實現了支持通配符操作的相關函數，下面對 Nginx 中哈希表的源碼進行分析。源碼文件：src/core/ngx_hash.h/.c。

哈希表結構

**ngx_hash_elt_t 結構 **

哈希表中關鍵字元素的結構 ngx_hash_elt_t，哈希表元素結構採用 鍵-值 形式，即 。其定義如下：

ngx_hash_t 結構

哈希表基本結構 ngx_hash_t，其結構定義如下

元素結構圖以及基本哈希結構圖如下所示：

**ngx_hash_init_t 初始化結構 **

哈希初始化結構 ngx_hash_init_t，Nginx 的 hash 初始化結構是 ngx_hash_init_t，用來將其相關數據封裝起來作為參數傳遞給ngx_hash_init()，其定義如下：

哈希元素數據 ngx_hash_key_t，該結構也主要用來保存要 hash 的數據，即鍵-值對，在實際使用中，一般將多個鍵-值對保存在 ngx_hash_key_t 結構的數組中，作為參數傳給ngx_hash_init()。其定義如下：

哈希操作

哈希操作包括初始化函數、查找函數；其中初始化函數是 Nginx 中哈希表比較重要的函數，由於 Nginx 的 hash 表是靜態只讀的，即不能在運行時動態添加新元素的，一切的結構和數據都在配置初始化的時候就已經規劃完畢。

哈希函數

哈希表中使用哈希函數把用戶數據映射到哈希表對應的位置中，下面是 Nginx 哈希函數的定義：

哈希初始化函數

hash 初始化由 ngx_hash_init() 函數完成，其 names 參數是 ngx_hash_key_t 結構的數組，即鍵-值對 數組，nelts 表示該數組元素的個數。該函數初始化的結果就是將 names 數組保存的鍵-值對，通過 hash 的方式將其存入相應的一個或多個 hash 桶(即代碼中的 buckets )中。hash 桶裡面存放的是 ngx_hash_elt_t 結構的指針(hash元素指針)，該指針指向一個基本連續的數據區。該數據區中存放的是經 hash 之後的鍵-值對

哈希查找函數

hash 查找操作由 ngx_hash_find() 函數完成，查找時由 key 直接計算所在的 bucket，該 bucket 中保存其所在 ngx_hash_elt_t 數據區的起始地址；然後根據長度判斷並用 name 內容匹配，匹配成功，其 ngx_hash_elt_t 結構的 value 字段即是所求。其定義如下：

測試程序：

main函數

輸出結果：

閱讀更多 七度猿人見聞 的文章

關鍵字: Nginx 數據結構 技術