返回主题:内置数据结构的底层实现

知识卡片

普通读书笔记卡 · 3566.n

建表前先整理通配键

理解等级:中级

ngx_hash_keys_arrays_t 先把精确名、前置和后置通配名分流到三组数组,并用对应的简易散列表检查重复或合并。随后初始化最终的三路散列表;暂存结构由 temp_pool 提供内存,可在建表后释放。把“收集去重”与“生成查询结构”分开,避免每加一个键都遍历整组。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章7.7.2(源文件:`_epub-src/EPUB/text00059.html`,图7-15 `Image00087.jpg`);[Nginx 1.8.0 `ngx_hash.c`](https://github.com/nginx/nginx/blob/release-1.8.0/src/core/ngx_hash.c)。 - 结论依据:原书区分三组待建表键数组与三组用于插入时查重的简易散列表,并说明`ngx_hash_keys_array_init`、`ngx_hash_add_key`先于`ngx_hash_init`/`ngx_hash_wildcard_init`;`temp_pool`只用于初始化期间的数据。 - 原始内容:如果没有这3个散列表,在向keys、dns_wc_head、dns_wc_tail动态数组添加元素时,为了避免出现相同关键字的元素,每添加一个关键字元素都需要遍历整个数组。