Kotlin优化两个自定义列表匹配更新的时间效率方案

你当前的写法本质是双层嵌套循环：遍历listB的每个id时，都要全量扫描listA找匹配项，时间复杂度为O(NM)*。当两个列表都达到50万条规模时，总计算量会到2500亿次，耗时必然过长。

核心优化思路是把id匹配的查询复杂度从O(M)降到O(1)，把整体时间复杂度压缩到O(N+M)，50万条数据处理可以稳定在毫秒级。

通用场景实现（适配所有id分布，代码最简单） #

第一步先把listB的所有id存入HashSet，哈希结构的单值查询是O(1)复杂度，之后仅需遍历一次listA就能完成所有字段更新，不需要嵌套循环：

// 转换待匹配id为哈希集，自动去重，查询复杂度O(1)
val matchIds = listB.toHashSet()
// 单次遍历listA完成更新，无嵌套循环
listA.forEach { item ->
    if (item.id in matchIds) {
        item.isUsed = true
    }
}

优化点说明 #

• 避免嵌套循环：总遍历次数从N*M降到N+M，计算量下降几个数量级
• 自动去重：HashSet会自动过滤listB中的重复id，减少无效判断
• 低内存开销：直接修改listA中元素的可变字段，不需要额外创建新的列表或模型实例，GC压力极小

极端性能场景优化（id取值范围集中时使用） #

如果业务中id的取值范围是连续、且最大值不超过200万，可以用BitSet代替HashSet，内存占用降低90%以上，查询速度更快：

// 先确定id的最大值，初始化位图
val maxId = listA.maxOf { it.id }
val idMarks = BitSet(maxId + 1).apply {
    listB.forEach { set(it) }
}
// 遍历更新
listA.forEach { item ->
    if (idMarks.get(item.id)) {
        item.isUsed = true
    }
}

注意：如果id分布非常分散（比如id是随机生成的十几位长整型），不适合用BitSet，会造成极大的内存浪费，直接用HashSet即可。

内容的提问来源于stack exchange，提问作者Muhammad Ammar