Java中：遍历Y列表匹配X，还是匹配后移除Y元素更高效？

先明确前提：X和Y是一对一无重复关联，每个Y的xId对应唯一X的id，匹配后Y无需保留在列表中。

两种方式的效率分析 #

方式一：全遍历匹配

for(X x: xList) {
    for(Y y: yList) {
        if(y.getXId() == x.getId()) {
            x.setY(y);
            break;
        }
    }
}

这种实现很直观，但本质是双重循环暴力匹配，时间复杂度是O(n*m)（n是X数量，m是Y数量）。哪怕某个Y已经被匹配过，后续的X还是会遍历到它——虽然不会命中，但遍历的开销依然存在。数据量越大，重复遍历的浪费越明显。

方式二：匹配后移除Y

for(X x: xList) {
    for(int i = 0; i < yList.size(); i++) {
        Y y = yList.get(i);
        if(y.getXId() == x.getId()) {
            x.setY(y);
            yList.remove(i);
            i--;
            break;
        }
    }
}

这种方式看似能减少后续遍历的Y数量，但隐藏了很大的性能坑：

• 如果用的是ArrayList，remove(int)操作需要把删除位置后的所有元素往前移动一位，时间复杂度是O(m)。如果前面的X频繁匹配到列表前面的Y，每次删除都要移动大量元素，这个开销会远大于“少遍历几个Y”的收益，整体效率可能比方式一还低。
• 如果用LinkedList，remove操作本身是O(1)，但get(int)需要从头遍历到指定索引，又是O(m)的开销，遍历成本反而更高。

最优解决方案：用HashMap预映射 #

处理这类“通过唯一键关联对象”的问题，标准高效做法是先把Y列表转成以xId为key的HashMap，再直接通过X的id查找：

// 先构建Y的映射表
Map<Long, Y> yIdToYMap = new HashMap<>();
for (Y y : yList) {
    yIdToYMap.put(y.getXId(), y);
}

// 遍历X直接匹配
for (X x : xList) {
    Y matchedY = yIdToYMap.get(x.getId());
    if (matchedY != null) {
        x.setY(matchedY);
    }
}

这个方案的时间复杂度是O(n + m)：构建映射表需要遍历一次Y列表（O(m)），遍历X列表时每个查找都是O(1)的哈希查找（总O(n)），不管数据量多大，效率都远高于前两种方式。

总结 #

• 数据量极小的时候，两种方式差异可以忽略，方式一实现更简单。
• 数据量较大时，方式二的移除操作带来的额外开销会让它得不偿失。
• 优先选择HashMap预映射的方案，这是最合理的高效实现。

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