Kotlin 协程上下文与 CombinedContext 源码解析

在 Kotlin 协程中，CoroutineContext 是一组元素的集合，如 Job、Dispatcher、CoroutineName 等。虽然从逻辑上看它像是一个 Map，但为了性能和协程的特殊需求，它的底层并没有使用 java.util.HashMap，而是使用了一种特殊的递归链表结构：**CombinedContext**。

1. 逻辑上的 Map，物理上的链表

CoroutineContext 定义了类似 Map 的 API：

• get(key)：获取元素。
• plus(context)：合并上下文（使用 + 运算符）。
• minusKey(key)：移除元素。

然而，它的实现类只有三种：

1. **EmptyCoroutineContext**：空集合。
2. **CoroutineContext.Element**：单个元素（如 Dispatchers.Main 本身就是一个 Element）。
3. **CombinedContext**：将两个上下文连接在一起的容器。

2. CombinedContext 的结构

CombinedContext 定义在 Kotlin 标准库中。它通过 left 和 element 两个字段构成一个二叉树状的链表（通常向左倾斜）。

1
2
3
4
5
6
7

// 逻辑示意（标准库实现）
internal class CombinedContext(
    private val left: CoroutineContext,
    private val element: Element
) : CoroutineContext {
    // ...
}

• **左侧 (left)**：可以是另一个 CombinedContext 或一个 Element。
• **右侧 (element)**：始终是一个单体 Element。

这种设计使得上下文的合并（+ 运算）非常轻量，不需要像 HashMap 那样计算哈希值或调整数组大小，只需创建一个新的 CombinedContext 节点即可。

3. 为什么不使用 HashMap？

1. 元素数量极少

大多数协程上下文只包含 2-4 个元素（例如：Job + Dispatcher + Name）。在元素数量如此之少的情况下，遍历微型链表的开销远小于 HashMap 的维护开销。

2. 不可变性与持久化

CoroutineContext 是不可变的。每次 + 运算都会产生新的上下文，而旧的上下文保持不变。CombinedContext 的设计天然支持这种持久化数据结构（Persistent Data Structure），允许新旧上下文共享节点。

详细示例：节点共享机制

假设我们有以下代码：

1
2

val contextA = Job() + Dispatchers.IO
val contextB = contextA + CoroutineName("MyCoroutine")

在底层的物理存储中，它们的关系如下：

1. contextA 的结构：

   • CombinedContext(left = Job, element = Dispatchers.IO)

2. contextB 的结构：

   • CombinedContext(left = contextA, element = CoroutineName("MyCoroutine"))

关键点在于：

• contextB 并没有拷贝 Job 和 Dispatchers.IO。
• 它的 left 指针直接指向了现有的 contextA 实例。
• 如果你启动了 1000 个协程，它们都基于同一个 ParentContext 增加自己的 CoroutineId，那么这 1000 个子上下文的 left 字段都指向内存中同一个 ParentContext 对象。

对比 HashMap：
如果使用 HashMap，每次添加元素（由于不可变性）都需要创建一个新的 Map 实例，并把旧 Map 中的所有 Entry 重新 Put 进去（或者进行复杂的写时复制）。对于频繁创建协程的场景，这会产生大量的垃圾回收压力。而 CombinedContext 只需要创建一个包含两个引用的新对象。

3. 内存效率

对于只有 1-2 个元素的上下文，使用 HashMap 会产生显著的内存浪费（Entry 对象、内部数组等），而 CombinedContext 仅需一个包含两个引用的对象。

4. 特殊优化：ThreadState 与数组缓存

虽然上下文本身是链表结构，但在某些性能敏感的场景下，协程库会将其转换为临时数组以加速访问。

例如在 ThreadContext.kt 中，当需要跨线程恢复多个 ThreadContextElement 时，系统会使用 ThreadState：

1
2
3
4
5

private class ThreadState(val context: CoroutineContext, n: Int) {
    private val values = arrayOfNulls<Any>(n) // 快速索引数组
    private val elements = arrayOfNulls<ThreadContextElement<Any?>>(n)
    // ...
}

这是一种典型的“空间换时间”策略：在执行频率极高的切换逻辑中，通过一次性 fold 遍历将链表转为数组缓存，从而避免后续多次递归查找。

5. 总结

Kotlin 协程上下文巧妙地避开了通用的 HashMap：

1. 基础存储：使用递归链表 CombinedContext，通过“引用共享”实现高效的持久化操作。
2. 查找逻辑：由于元素极少，线性遍历优于哈希查找。
3. 极端优化：在线程切换等关键路径，通过临时数组（ThreadState）进行加速。

这种“因地制宜”的设计是协程能够胜任数百万级并发的重要基石。

正文

双指针（Two Pointers）是一种常用于数组或字符串问题的技巧。当我们需要在有序序列中查找符合特定条件的元素对，或者判断序列是否具有某种属性（如回文）时，从两端向中间遍历是非常高效的。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

fun doublePointer(arr: IntArray): Int {
    var left = 0
    var right = arr.size - 1

    while (left < right) {
        // 根据 left 和 right 相关的条件进行操作
        // 例如：if (arr[left] + arr[right] == target) return ...
        
        if (CONDITION) {
            left++
        } else {
            right--
        }
    }

    return 0 // 返回需要的结果
}

使用说明

1. 适用场景：

   • 有序数组：如两数之和（有序版）、三数之和。
   • 字符串处理：如判断回文字符串、反转数组/字符串。
   • 容器盛水问题：如“盛最多水的容器”。

2. 核心优势：

   • 能够将 $O(N^2)$ 的暴力枚举优化到 $O(N)$。
   • 利用了序列的有序性或特定单调性。

3. 注意点：

   • 循环条件通常是 left < right（找对子）或 left <= right（处理中间元素）。
   • 更新指针时要确保逻辑能够覆盖所有情况，避免死循环。

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

fun twoPointers(nums1: IntArray, nums2: IntArray) {
    var pointer1 = 0
    var pointer2 = 0

    while (pointer1 < nums1.size && pointer2 < nums2.size) {
        // 处理指针1和指针2对应位置的元素
        // ...

        // 移动指针
        pointer1++
        pointer2++
    }

    // 处理剩余未遍历完的元素
    while (pointer1 < nums1.size) {
        // 处理指针1对应位置的元素
        // ...
        pointer1++
    }

    while (pointer2 < nums2.size) {
        // 处理指针2对应位置的元素
        // ...
        pointer2++
    }
}

正文

滑动窗口（Sliding Window）是一种在数组或字符串上执行操作的优化技术。它将嵌套循环的问题转化为单个循环，从而显著降低时间复杂度。

算法模板（固定窗口大小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

fun slidingWindow(nums: IntArray, k: Int): Int {
    val n = nums.size
    if (n < k) return 0
    
    var sum = 0
    var maxSum = 0

    // 1. 初始化：计算第一个窗口的和
    for (i in 0 until k) {
        sum += nums[i]
    }

    maxSum = sum

    // 2. 滑动：从第 k 个元素开始遍历
    for (i in k until n) {
        // 新窗口的和 = 前一个窗口的和 + 新进入的元素 - 离开窗口的元素
        sum += nums[i] - nums[i - k]
        // 更新结果
        maxSum = maxOf(maxSum, sum)
    }

    return maxSum
}

使用说明

1. 适用场景：

   • 固定窗口：给定窗口大小 $k$，求最大/最小和、平均值等。
   • 可变窗口：寻找满足特定条件的最长/最短子数组（通常配合双指针 left, right 使用）。

2. 核心优势：

   • 避免了重复计算窗口重叠部分的值。
   • 时间复杂度通常为 $O(N)$。

3. 注意点：

   • 注意边界条件，如数组长度小于 $k$ 的情况。
   • 如果是求平均值，注意浮点数转换。
   • 对于可变窗口，通常逻辑是：右边界右移增加元素 -> 窗口不满足条件时左边界右移移除元素。

正文

前缀和（Prefix Sum）是一种非常重要的预处理技巧，主要用于高效计算数组中任意区间的元素之和。

算法模板

1
2
3
4
5
6
7
8
9
10
11

fun prefixSum(nums: IntArray): IntArray {
    // 前缀和数组长度为 n + 1，prefixSum[i] 表示 nums 中前 i 个元素的和
    val prefixSum = IntArray(nums.size + 1)

    // 计算前缀和数组
    for (i in 1..nums.size) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
    }
    
    return prefixSum
}

使用说明

1. 区间求和：
   使用前缀和数组 prefixSum，我们可以以 $O(1)$ 的时间复杂度回答多个区间和查询。计算区间 [left, right]（包含两端）的元素之和：

   1	val sum = prefixSum[right + 1] - prefixSum[left]

2. 核心优势：
   将多次区间查询的时间复杂度从 $O(N)$ 降低到 $O(1)$。

3. 注意点：

   • 前缀和数组长度通常设为 n + 1，其中 prefixSum[0] = 0。这样可以统一处理 left = 0 的边界情况，无需额外的 if 判断。
   • 如果数组元素较大，注意前缀和数组可能发生整型溢出，必要时使用 LongArray。

正文

以下是一个高效的字符串构建算法模板：

1
2
3
4
5
6
7
8
9

fun buildString(chars: List<Char>): String {
    val sb = StringBuilder()

    for (ch in chars) {
        sb.append(ch)
    }
    
    return sb.toString()
}

在这个模板中，我们使用 StringBuilder 来构建字符串。StringBuilder 是可变的字符串类，可以高效地进行字符串的拼接操作。

我们通过遍历字符列表 chars，逐个将字符添加到 StringBuilder 中。最后，通过调用 toString() 方法，将 StringBuilder 转换为最终的字符串结果并返回。

使用 StringBuilder 的好处是它避免了在每次拼接字符串时创建新的字符串对象，从而提高了性能和效率。特别是在需要频繁拼接大量字符串的情况下，使用 StringBuilder 可以避免不必要的性能损耗。

使用这个模板，你可以根据具体需求构建字符串。可以根据问题的要求在遍历过程中进行一些字符处理、条件判断等操作。

正文

在模板中，我们使用两个指针，一个指针每次向后移动一个节点，另一个指针每次向后移动两个节点。如果链表中存在循环，快指针最终会追上慢指针，这样我们就可以判断出链表有循环。如果链表没有循环，快指针会先到达链表的末尾，此时我们就可以判断链表没有循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

fun hasCycle(head: ListNode?): Boolean {
    var slow = head
    var fast = head

    while (fast?.next != null && fast.next?.next != null) {
        slow = slow?.next
        fast = fast.next?.next

        if (slow == fast) {
            return true
        }
    }

    return false
}

正文

反转链表（Reverse Linked List）是链表操作中最基础且最高频的考点。它通过改变节点间的指针指向，将原本 A -> B -> C 的结构变为 C -> B -> A。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class ListNode(var value: Int) {
    var next: ListNode? = null
}

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var current = head
    
    while (current != null) {
        val nextNode = current.next // 1. 暂存下一个节点
        current.next = prev         // 2. 反转当前节点的指向
        prev = current              // 3. prev 向前移动
        current = nextNode          // 4. current 向前移动
    }

    return prev // 新的头节点
}

使用说明

1. 核心逻辑：
   在遍历过程中，我们需要维持三个变量：prev（已反转部分的头）、current（当前处理的节点）和 nextNode（待处理部分的头）。

2. 关键步骤：
   反转指针前，**必须先暂存 current.next**，否则一旦修改了 current.next，就无法找到链表的后续部分。

3. 时间与空间复杂度：

   • 时间复杂度：$O(N)$，只需遍历一次链表。
   • 空间复杂度：$O(1)$，仅需常数级别的额外空间。

4. 注意点：

   • 空链表或只有一个节点的链表应能正常工作。
   • 在 Kotlin 中，注意处理可空性（ListNode?）。

正文

在算法面试中，“找到符合确切条件的子数组数”通常有两种核心解法：前缀和 + 哈希表（通用性最强）或 双指针/滑动窗口（适用于非负数序列）。

方案一：前缀和 + 哈希表 (通用模板)

这是解决该类问题的“银弹”，适用于数组中包含负数的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
    var count = 0
    var prefixSum = 0
    // key: 前缀和的值, value: 该前缀和出现的次数
    val map = mutableMapOf<Int, Int>()
    // 初始化：前缀和为 0 已经出现过 1 次
    map[0] = 1

    for (num in nums) {
        prefixSum += num
        // 如果 prefixSum - goal 存在于 map 中，说明存在子数组和为 goal
        count += map.getOrDefault(prefixSum - goal, 0)
        // 更新当前前缀和的出现次数
        map[prefixSum] = map.getOrDefault(prefixSum, 0) + 1
    }

    return count
}

方案二：双指针 / 滑动窗口 (针对非负数优化)

如果数组中元素全部非负，使用滑动窗口可以将空间复杂度降低到 $O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 统计和正好为 goal 的子数组数量
fun numSubarraysWithSumSlidingWindow(nums: IntArray, goal: Int): Int {
    // 技巧：正好为 K = 最多为 K - 最多为 K-1
    return atMost(nums, goal) - atMost(nums, goal - 1)
}

private fun atMost(nums: IntArray, goal: Int): Int {
    if (goal < 0) return 0
    var left = 0
    var sum = 0
    var count = 0
    for (right in nums.indices) {
        sum += nums[right]
        while (sum > goal) {
            sum -= nums[left]
            left++
        }
        // [left...right] 之间所有以 right 结尾的子数组都符合“和 <= goal”
        count += right - left + 1
    }
    return count
}

使用说明

1. 为什么原模板中“统计连续的0”比较复杂？
   在滑动窗口中，如果存在 0，窗口的和不会改变，这会导致统计“确切”数量时变得棘手。“恰好为 K = 最多为 K - 最多为 K-1” 是处理此类滑动窗口问题最优雅的数学技巧。

2. 核心优势：

   • 哈希表法：时间 $O(N)$，空间 $O(N)$。适用于任何数组。
   • 双指针法：时间 $O(N)$，空间 $O(1)$。仅适用于非负数组。

3. 常见变形：

   • 求和为 K 的子数组。
   • 求奇数个数为 K 的子数组（将奇数看作 1，偶数看作 0）。

正文

单调栈（Monotonic Stack）是一种极其重要的数据结构，专门用于解决“下一个更大元素（Next Greater Element）”或“上一个更小元素”这类问题。

算法模板 (寻找下一个更大元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

fun nextGreaterElement(nums: IntArray): IntArray {
    val n = nums.size
    val result = IntArray(n) { -1 }
    // 栈中存储元素的索引（以便更新 result 数组）
    val stack = mutableListOf<Int>()

    for (i in nums.indices) {
        // 当栈不为空，且当前元素大于栈顶元素时
        while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
            // 此时 nums[i] 就是栈顶元素的“下一个更大元素”
            val index = stack.removeAt(stack.size - 1)
            result[index] = nums[i]
        }
        
        // 当前元素入栈（等待属于它的更大元素出现）
        stack.add(i)
    }

    return result
}

使用说明

1. 核心特性：

   • 单调递增栈：栈内元素从底到顶单调递增。用于寻找右侧第一个比自己小的元素（或者左侧第一个比自己小的）。
   • 单调递减栈：栈内元素从底到顶单调递减。用于寻找右侧第一个比自己大的元素（即模板写法）。

2. 核心优势：

   • 将 $O(N^2)$ 的暴力查找优化到 $O(N)$。每个元素最多进栈一次、出栈一次。

3. 常见变形：

   • 循环数组：通过遍历两次（i % n）来模拟循环。
   • 接雨水：利用单调栈计算低洼处的面积。
   • 最大矩形面积：利用单调栈寻找左右两侧的边界。

4. 注意点：

   • 明确题目要求的是“右侧第一个更大”还是“左侧第一个更小”。
   • 明确栈里存的是“元素值”还是“元素的下标”（下标通常更通用）。