知识卡片

普通读书笔记卡 · 3566.i

红黑树同键须有次序

理解等级:高级

ngx_rbtree_node_t.key 是整数,可能有不同对象共用同一个 key。把节点内嵌到业务结构体后,应按完整身份选择 ngx_rbtree_insert_pt 插入函数;本书的字符串节点先按 key、再按长度与字节内容确定方向,并用对应的 ngx_str_rbtree_lookup 检索。发散:哈希值可以缩小查找范围,不能独自充当唯一身份。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章7.5.3、7.5.5(源文件:`_epub-src/EPUB/text00057.html`)。 - 结论依据:`ngx_rbtree_t.insert` 保存插入回调;书中字符串节点示例在 key 相等时继续比较字符串长度与内容,检索同时传入 hash 与 name。 - 原始内容:树节点的关键字)。例如,不同的字符串可能会散列出相同的关键字,这时它们在红黑树中的关键字是相同的,然而它们又是不同的节点,这样在添加时就不可以覆盖原有同名关键字节点,而是作为新插入的节点存在。因此,在添加元素时,需要考虑到这种情况。