知识卡片
红黑树同键须有次序
ngx_rbtree_node_t.key 是整数,可能有不同对象共用同一个 key。把节点内嵌到业务结构体后,应按完整身份选择 ngx_rbtree_insert_pt 插入函数;本书的字符串节点先按 key、再按长度与字节内容确定方向,并用对应的 ngx_str_rbtree_lookup 检索。发散:哈希值可以缩小查找范围,不能独自充当唯一身份。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章7.5.3、7.5.5(源文件:`_epub-src/EPUB/text00057.html`)。
- 结论依据:`ngx_rbtree_t.insert` 保存插入回调;书中字符串节点示例在 key 相等时继续比较字符串长度与内容,检索同时传入 hash 与 name。
- 原始内容:树节点的关键字)。例如,不同的字符串可能会散列出相同的关键字,这时它们在红黑树中的关键字是相同的,然而它们又是不同的节点,这样在添加时就不可以覆盖原有同名关键字节点,而是作为新插入的节点存在。因此,在添加元素时,需要考虑到这种情况。