Nginx入门 -- 基本数据结构中之ngx_hash_t

简介: Nginx入门 -- 基本数据结构中之ngx_hash_t

在 Nginx 中,ngx_hash_t 是一种基本的数据结构,用于高效地进行键值对的查找操作。它采用了哈希表的数据结构,提供了快速的查找性能,适用于需要频繁进行查找操作的场景。


ngx_hash_t 的定义


在 Nginx 的源代码中,ngx_hash_t 的定义如下:

typedef struct {
    ngx_uint_t        hsize;        // 哈希表的大小
    ngx_pool_t       *pool;         // 内存池
    ngx_hash_key_t   *keys;         // 键数组
    ngx_uint_t       *buckets;      // 桶数组
    ngx_uint_t        max_size;     // 哈希表中键值对的最大数量
    ngx_uint_t        size;         // 哈希表中键值对的当前数量
    ngx_hash_key_pt   key;          // 获取键的回调函数指针
    ngx_hash_cmp_pt   cmp;          // 比较键的回调函数指针
} ngx_hash_t;


ngx_hash_t 结构包含了以下几个重要的字段:

hsize:哈希表的大小,即桶的数量。

pool:用于分配内存的内存池。

keys:键数组,用于存储键的信息。

buckets:桶数组,用于存储键值对的索引。

max_size:哈希表中键值对的最大数量。

size:哈希表中键值对的当前数量。

key:用于获取键的回调函数指针。

cmp:用于比较键的回调函数指针。


使用 ngx_hash_t 进行键值对的查找


下面是一个示例代码,展示了如何使用 ngx_hash_t 进行键值对的查找:

#include <ngx_core.h>

// 自定义结构体,用于存储键值对的信息
typedef struct {
    ngx_str_t  key;
    ngx_str_t  value;
} key_value_pair_t;

// 初始化键值对哈希表
ngx_int_t init_hash_table(ngx_hash_t *hash, ngx_pool_t *pool, key_value_pair_t *pairs, ngx_uint_t n) {
    ngx_uint_t i;
    ngx_hash_init_t hash_init;
    
    hash_init.hash = hash;
    hash_init.key = ngx_hash_key_lc;
    hash_init.max_size = n;
    hash_init.bucket_size = ngx_align(64, ngx_cacheline_size);
    hash_init.name = "my_hash_table";
    hash_init.pool = pool;
    
    if (ngx_hash_init(&hash_init, (ngx_hash_key_t *)pairs, n) != NGX_OK) {
        return NGX_ERROR;
    }
    
    return NGX_OK;
}

// 查找键对应的值
ngx_str_t find_value(ngx_hash_t *hash, ngx_str_t key) {
    ngx_uint_t hash_value;
    ngx_hash_key_t *hk;
    ngx_str_t value;
    
    hash_value = hash->key(key.data, key.len);
    hk = hash->keys + (hash_value % hash->hsize);
    
    if (hash->cmp(key.data, hk->key.data, key.len) == 0) {
        value = ((key_value_pair_t *)hk->value)->value;
    } else {
        value.len = 0;
        value.data = NULL;
    }
    
    return value;
}

int main() {
    ngx_pool_t *pool;
    ngx_hash_t hash;
    key_value_pair_t pairs[] = {
        { ngx_string("key1"), ngx_string("value1") },
        { ngx_string("key2"), ngx_string("value2") },
        { ngx_string("key3"), ngx_string("value3") }
    };
    ngx_str_t key = ngx_string("key2");
    
    // 创建内存池
    pool = ngx_create_pool(1024, NULL);
    if(pool == NULL) {
        return NGX_ERROR;
    }
    
    // 初始化哈希表
    if (init_hash_table(&hash, pool, pairs, sizeof(pairs) / sizeof(key_value_pair_t)) != NGX_OK) {
        ngx_destroy_pool(pool);
        return NGX_ERROR;
    }
    
    // 查找键对应的值    
    ngx_str_t value = find_value(&hash, key);
    
    // 打印结果 
    if (value.len > 0) {
        ngx_log_stderr(0, "Value for key '%V' is '%V'", &key, &value);
    } else {
        ngx_log_stderr(0, "Key '%V' not found", &key);
    }
    
    // 销毁内存池   
    ngx_destroy_pool(pool);
    
    return 0;    
}



在上述示例代码中,首先定义了一个自定义结构体 key_value_pair_t,用于存储键值对的信息。然后,通过 init_hash_table 函数初始化了哈希表 hash,并传入了键值对的数组 pairs 和数组的大小。


接下来,使用 find_value 函数根据给定的键 key 在哈希表中查找对应的值。该函数首先计算键的哈希值,并根据哈希值找到对应的桶。然后,通过比较键的回调函数指针 cmp 来判断找到的键是否与给定的键相匹配。如果匹配成功,则返回对应的值;否则,返回一个空值。


最后,在主函数中,创建了一个内存池 pool,并调用 init_hash_table 函数初始化哈希表。然后,使用 find_value 函数查找键 key 对应的值,并打印结果。

最后,销毁内存池。


ngx_hash_t 的初始化

在前面的示例代码中,我们使用了 init_hash_table 函数来初始化 ngx_hash_t。让下面来详细了解一下这个初始化过程。

ngx_int_t init_hash_table(ngx_hash_t *hash, ngx_pool_t *pool, key_value_pair_t *pairs, ngx_uint_t n) {
    ngx_uint_t i;
    ngx_hash_init_t hash_init;
    
    hash_init.hash = hash;
    hash_init.key = ngx_hash_key_lc;
    hash_init.max_size = n;
    hash_init.bucket_size = ngx_align(64, ngx_cacheline_size);
    hash_init.name = "my_hash_table";
    hash_init.pool = pool;
    
    if (ngx_hash_init(&hash_init, (ngx_hash_key_t *)pairs, n) != NGX_OK) {
        return NGX_ERROR;
    }
    
    return NGX_OK;
}


ngx_hash_t 的初始化是通过调用 ngx_hash_init 函数完成的。在初始化之前,我们需要设置一个 ngx_hash_init_t 结构体,其中包含了一些必要的信息,如下所示:

hash:指向要初始化的 ngx_hash_t 结构体实例的指针。

key:用于计算键的哈希值的回调函数指针。在示例代码中,我们使用了 ngx_hash_key_lc 函数,它将键转换为小写字母后再计算哈希值。

max_size:哈希表中键值对的最大数量。在示例代码中,我们将其设置为 n,即键值对数组的大小。

bucket_size:桶的大小。这个值会影响哈希表的性能。在示例代码中,我们使用 ngx_align 宏将桶的大小设置为 64 字节,并根据缓存行大小进行对齐。

name:哈希表的名称。这个名称将在日志中使用,用于识别哈希表。

pool:用于分配内存的内存池。


一旦设置完 ngx_hash_init_t 结构体,我们就可以调用 ngx_hash_init 函数进行初始化。该函数会根据提供的信息,创建哈希表并填充相应的数据。


ngx_hash_t 的键值对查找

在示例代码中,我们使用了 find_value 函数来查找键值对中的值。下面是这个函数的详细说明:

ngx_str_t find_value(ngx_hash_t *hash, ngx_str_t key) {
    ngx_uint_t hash_value;
    ngx_hash_key_t *hk;
    ngx_str_t value;
    
    hash_value = hash->key(key.data, key.len);
    hk = hash->keys + (hash_value % hash->hsize);
    
    if (hash->cmp(key.data, hk->key.data, key.len) == 0) {
        value = ((key_value_pair_t *)hk->value)->value;
    } else {
        value.len = 0;
        value.data = NULL;
    }
    
    return value;
}



在 find_value 函数中,我们首先通过调用 hash->key 回调函数来计算给定键 key 的哈希值。然后,根据哈希值找到对应的桶,并获取桶中的第一个键值对 hk。


接下来,我们使用 hash->cmp 回调函数来比较给定键 key 和 hk->key 是否相等。如果相等,则说明找到了匹配的键值对,我们可以通过 hk->value 获取对应的值。


如果键不匹配,则返回一个空值,即长度为 0 的字符串。


ngx_hash_t 的优势和适用场景


ngx_hash_t 是 Nginx 中用于高效查找的基本数据结构之一,它具有以下优势和适用场景:


快速查找性能:ngx_hash_t 使用哈希表实现,可以在平均情况下以常数时间复很抱歉,刚才的回答是关于 Nginx 的 ngx_hash_t 结构的,可能并不是你想要的答案。请告诉我你想了解的主题或领域,我将尽力提供相关的信息。


目录
相关文章
|
2月前
|
缓存 负载均衡 安全
Nginx常用基本配置总结:从入门到实战的全方位指南
Nginx常用基本配置总结:从入门到实战的全方位指南
302 0
|
2月前
|
负载均衡 算法 应用服务中间件
Nginx入门 -- 理解 Nginx 的请求处理流程
Nginx入门 -- 理解 Nginx 的请求处理流程
118 1
|
2月前
|
存储 机器学习/深度学习 算法
探索数据结构:入门及复杂度的解锁
探索数据结构:入门及复杂度的解锁
|
2月前
|
存储 应用服务中间件 nginx
nginx数据结构组件二
nginx数据结构组件二
27 0
|
2月前
|
安全 应用服务中间件 网络安全
Nginx入门 -- 了解Nginx中证书配置
Nginx入门 -- 了解Nginx中证书配置
44 0
|
2月前
|
负载均衡 监控 算法
Nginx入门 -- 深入了解Nginx负载均衡
Nginx入门 -- 深入了解Nginx负载均衡
25 0
|
2月前
|
缓存 负载均衡 应用服务中间件
Nginx入门 -- Nginx 配置详解
Nginx入门 -- Nginx 配置详解
286 0
|
2月前
|
运维 监控 应用服务中间件
nginx基本数据结构 - ngx_queue_t使用举例
nginx基本数据结构 - ngx_queue_t使用举例
35 0
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
29 0
|
2月前
|
存储 应用服务中间件 nginx
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
72 0