第1章 通知队列核心数据结构

通知队列是 SystemUI 中处理通知事件流转的中枢，高效的数据结构直接决定了入队、出队、延迟、去重和状态查询的性能。本章围绕四种核心数据结构展开：PriorityQueue（优先级队列）、延迟队列、有序集合与键值映射，分析它们各自在通知处理管道中的角色、实现原理及工程化落地方案。

1.1 数据结构对比与选型

1.2 原理与职责分工

PriorityQueue 是通知管道的入口缓冲。系统产生的每条通知都携带一个整数优先级（Notification.PRIORITY_MAX 到 PRIORITY_MIN），PriorityQueue 通过小顶堆保证最高优先级的通知优先被处理线程消费。

延迟队列 解决通知的“定时触发”问题。例如锁屏通知需要在指定延迟后自动折叠，或者静默通知等待用户空闲时段才展示。延迟队列内部的堆结构按到期时间排序，只有到期元素才能从队列中取出。

有序集合 负责通知展示列表的全局排序。即使多个通知优先级相同，也需要按时间戳或自定义顺序呈现。TreeSet 保证元素唯一且有序，用于去重以及维持 List 的条目顺序。

键值映射 提供 O(1) 的随机访问能力。当接收到更新通知或取消通知时，系统需要根据 NotificationKey 快速找到目标条目进行替换或移除。ConcurrentHashMap 是首选实现，兼顾并发与性能。

1.3 组合架构流程图

下图展示了四种数据结构在 SystemUI 通知队列中的协作关系：上游产生通知后依次经过优先级排序、延迟控制、去重与顺序维护，最终通过键值映射进行高效更新。

1.4 核心实现流程

以下伪代码片段展示了如何在 SystemUI 通知处理线程中整合这四个数据结构。注意使用 PriorityBlockingQueue 保证线程安全，DelayQueue 配合 Delayed 接口实现超时控制。

// 通知队列管理器核心类片段
public class NotificationQueueManager {
    // 优先级队列（消费线程按优先级取出）
    private final PriorityBlockingQueue<NotificationEntry> priorityQueue =
            new PriorityBlockingQueue<>(11, Comparator.comparingInt(NotificationEntry::getPriority));

    // 延迟队列（仅到期元素可见）
    private final DelayQueue<DelayedNotification> delayedQueue = new DelayQueue<>();

    // 有序集合（维护展示顺序 + 去重）
    private final ConcurrentSkipListSet<NotificationEntry> orderedSet =
            new ConcurrentSkipListSet<>(Comparator.comparingLong(NotificationEntry::getPostTime));

    // 键值映射（快速定位）
    private final ConcurrentHashMap<String, NotificationEntry> keyIndex = new ConcurrentHashMap<>();

    // 入队方法
    public void enqueue(NotificationEntry entry) {
        // 1. 写入键值映射
        keyIndex.put(entry.getKey(), entry);
        // 2. 加入有序集合
        orderedSet.add(entry);
        // 3. 根据延迟属性选择队列
        if (entry.getDelayMillis() > 0) {
            delayedQueue.put(new DelayedNotification(entry, entry.getDelayMillis()));
        } else {
            priorityQueue.put(entry);
        }
    }

    // 消费线程主循环
    public void processLoop() {
        while (!Thread.currentThread().isInterrupted()) {
            // 优先处理延迟到期的通知
            DelayedNotification delayed = delayedQueue.poll();
            if (delayed != null) {
                process(delayed.getEntry());
                continue;
            }
            // 再取优先级队列
            NotificationEntry entry = priorityQueue.poll(100, TimeUnit.MILLISECONDS);
            if (entry != null) {
                process(entry);
            }
        }
    }
}

1.5 调试与日志观察

在 SystemUI 环境（/data/system/notification_queue.txt）下，可以通过以下命令实时观察队列状态：

# 打印优先级队列当前大小
adb shell dumpsys notification | grep "PriorityQueue size"

# 查看延迟队列中所有待消费元素及其到期时间
adb shell dumpsys notification --delay-queue

# 转储键值映射，检查是否存在残留通知
adb shell dumpsys notification --key-index

常见日志标记（logcat 过滤）：

adb logcat -s NotificationQueueManager:D

1.6 常见错误与规避

• Comparable 实现不一致： 若同一通知同时出现在 PriorityQueue 和 TreeSet 中，两个排序器的比较器必须逻辑一致，否则会导致数据不一致。
• 延迟队列空指针： DelayQueue.take() 在空队列时会阻塞，务必配合超时轮询（poll(time, unit)）避免永久挂起。
• 键值映射内存泄漏： 通知取消时未从 keyIndex 移除，导致陈旧通知堆积。需在 remove() 时联动清理。
• 线程安全： PriorityQueue 非线程安全，必须使用 PriorityBlockingQueue；有序集合使用 ConcurrentSkipListSet 而非 TreeSet。

1.7 性能与稳定性优化建议

在 SystemUI 启动阶段，可预先设置合理初始容量以规避扩容开销：

// 典型配置：预期同时存在 100 条通知
PriorityBlockingQueue<NotificationEntry> queue =
        new PriorityBlockingQueue<>(100, comparator);
ConcurrentHashMap<String, NotificationEntry> map =
        new ConcurrentHashMap<>(128, 0.75f, 4); // 4个并发段