鸿蒙OSSortedMap是什么？原理、用法与常见问题一文详解

OSSortedMap是OpenHarmony内核源码里一个基于红黑树实现的有序映射容器，最早出现在LiteOS内核与部分系统服务的代码中。它的核心价值在于把红黑树的复杂旋转逻辑封装起来，对外暴露一套简洁的接口，让开发者能够以键值对的形式管理有序数据。很多初次阅读鸿蒙内核源码的同学会对它的结构设计感到困惑，这篇文章就把它的原理、用法和常见问题一次讲透。

一、OSSortedMap的设计原理与核心结构

要理解OSSortedMap，得先从它底层的红黑树说起。红黑树是一种自平衡二叉搜索树，插入、删除、查找的时间复杂度稳定在O(log n)，最坏情况下也不会退化成链表。OpenHarmony内核对红黑树的实现位于kernel\extended\include\los_rbtree.h相关文件中，核心节点结构是LOS_RBTREENODE，其中包含了左孩子、右孩子、父节点指针以及颜色标记字段。

OSSortedMap本质上是对这棵红黑树的二次封装。它内部持有一个LOS_RBTREE实例，同时定义了一套比较回调函数，用于在插入节点时确定元素的排序位置。典型的结构定义如下：

typedef struct TagSortedMap {
    LOS_RBTREE stRbTree;              // 底层红黑树实例
    SortCompareFunc fnCompare;        // 键比较回调函数
    SortKeyDestroyFunc fnKeyDestroy;  // 键析构回调（可选）
    SortValueDestroyFunc fnValueDestroy; // 值析构回调（可选）
    UINT32 uwNodeCount;               // 当前节点数量
} OSSortedMap;

这种设计有几个值得注意的点。第一，比较函数由使用者在初始化时注入，这意味着OSSortedMap本身不限定键的类型，既可以放整数键，也可以放字符串键甚至复合结构体键，灵活性很高。第二，析构回调的存在让它具备了基本的资源管理能力，销毁整棵树时可以自动释放节点占用的内存，减少手动释放遗漏的风险。第三，节点计数字段让获取元素总数变成O(1)操作，不用每次遍历统计。

二、关键接口的用法与代码示例

OSSortedMap对外提供的接口遵循鸿蒙内核一贯的命名风格，常用的有创建、插入、查找、删除、遍历、销毁这几类。下面通过一段完整代码演示典型用法，以超时时间为键来管理一组定时任务，这也是内核定时器模块的真实使用场景。

#include "los_sortedmap.h"

// 自定义值结构
typedef struct {
    UINT32 uwTaskId;
    CHAR_T szName[16];
} TimerTaskInfo;

// 键比较函数：按UINT32大小排序
STATIC INT32 TimerKeyCompare(const VOID *pKey1, const VOID *pKey2)
{
    UINT32 uwKey1 = *(UINT32 *)pKey1;
    UINT32 uwKey2 = *(UINT32 *)pKey2;
    if (uwKey1 < uwKey2) {
        return -1;
    }
    return (uwKey1 == uwKey2) ? 0 : 1;
}

VOID TimerMapDemo(VOID)
{
    OSSortedMap *pstMap = LOS_SortedMapCreate(TimerKeyCompare, NULL, NULL);
    if (pstMap == NULL) {
        return;
    }

    TimerTaskInfo stTask = { .uwTaskId = 100, .szName = "taskA" };
    UINT32 uwTimeout = 500; // 500个tick后到期

    // 插入节点
    (VOID)LOS_SortedMapAddNode(pstMap, &uwTimeout, &stTask);

    // 查找最早到期的任务（最左节点）
    LOS_SORTMAP_NODE *pstFirst = LOS_SortedMapGetFirst(pstMap);
    if (pstFirst != NULL) {
        TimerTaskInfo *pstInfo = LOS_SortedMapGet(pstMap, pstFirst);
        // 处理最早到期的任务...
    }

    // 删除节点并销毁
    (VOID)LOS_SortedMapDeleteNode(pstMap, pstFirst);
    LOS_SortedMapDestroy(pstMap);
}

这段代码体现了三个关键细节。其一，比较函数的返回值约定是负数、零、正数三态，务必保证比较逻辑在全序关系上成立，否则红黑树的平衡会被破坏。其二，LOS_SortedMapGetFirst返回的是树上最左侧的节点，即键最小的元素，这正是定时器模块快速取最近到期任务的入口。其三，插入的键和值只是指针，OSSortedMap不会帮你复制内容，所以传入的内存生命周期必须覆盖节点的存活周期。

三、常见问题与排查思路

问题一：插入重复键后行为异常。红黑树本身允许写入相等键，但OSSortedMap在比较函数返回0时的处理取决于具体实现。如果你依赖键的唯一性，要么在比较函数中把相等视为一种可区分的情况，要么插入前先调用查找接口判断是否已存在。定时器场景中常见的做法是在键中拼接任务序号，保证任意两个节点的键严格不同。

问题二：删除节点后出现野指针。这是被问到最多的问题。当你通过LOS_SortedMapDeleteNode删除某个节点后，之前拿到的其他节点指针并不失效，但被删节点本身的内存是否释放取决于创建时的析构配置。如果析构回调传了NULL，释放责任就在调用方。更危险的做法是在遍历过程中边遍历边删除，这会破坏遍历上下文。正确的姿势是先收集待删除的节点指针到临时数组，遍历结束后再统一执行删除。

问题三：与哈希表、链表如何选择。如果你的场景只需要随机的增删查改且不关心顺序，哈希表的平均O(1)性能更合适；如果数据量极小（几十个以内），双向链表加线性扫描的代码更简单可控；而当你需要频繁取最值、按序遍历或者范围查询时，OSSortedMap这类有序结构才是最优解。鸿蒙内核的定时器超时管理、部分内存池的空闲块管理选它，正是因为这些场景对取最值的频率要求极高。

问题四：多任务环境下的并发安全。OSSortedMap本身不加锁。在多任务或中断场景下访问同一个实例，必须由上层用互斥锁或关中断保护。内核代码中凡是跨任务使用有序映射的地方，都会配合LOS_MuxLock或者LOS_SpinLock使用，应用层开发时同样不能省略这一步，否则红黑树结构在高并发下很容易被旋转操作撕裂，造成死循环或内存越界。

总的来说，OSSortedMap是鸿蒙内核里一个职责单一但设计干净的数据结构。理解了它对红黑树的封装思路和回调机制，再去阅读定时器、调度相关的内核源码会顺畅很多。如果你在移植或二次开发中遇到更具体的问题，建议直接对照los_sortedmap.c的实现逐行分析，源码总量不大，通读一遍的成本远低于反复猜测接口行为。

鸿蒙OSSortedMap鸿蒙开发OpenHarmony修改时间：2026-09-07 07:40:37