知识卡片

普通读书笔记卡 · 3566.l

散列桶内逐项核键

理解等级:中级

ngx_hash_find 用 key % size 定位桶,在该桶内沿连续排布的变长 ngx_hash_elt_t 逐项检查 len 和 name,命中后返回 value。碰撞处理限于桶内遍历,不是线性探测后续桶;把书中“开放寻址”直接套到这里,会误读查找与内存布局。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章7.7.1(源文件:`_epub-src/EPUB/text00059.html`,图7-10 `Image00078.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_find`需同时核对散列码、名称与长度,但“开放寻址/顺序找后续槽”的表述与对应版本源码不符;源码仅取`buckets[key % size]`,随后在同一桶的变长元素区按对齐步长前进,以空`value`结束。 - 原始内容:ngx_hash_find的执行结果就是返回散列表中关键字与name、len指定关键字完全相同的槽中,ngx_hash_elt_t结构体中value成员所指向的用户数据。