场景描述与初始实现
在业务开发中，我们经常会遇到需要将关联的子项数据集合添加到主对象列表中的场景。例如，我们有一个产品（product）列表，以及一个产品子项（productsub）列表。每个产品子项都通过 productid 关联到特定的产品。我们的目标是将所有属于某个产品的子项收集起来，并设置到该产品的 productsublist 属性中。
以下是相关的类定义：
public class Product {
private long productId;
private String productName;
private BigDecimal costAmount;
private List productSublist;
// 构造函数、Getter和Setter（为简洁省略）
public Product(long productId, String productName, BigDecimal costAmount) {
this.productId = productId;
this.productName = productName;
this.costAmount = costAmount;
this.productSublist = new ArrayList<>(); // 初始化为空列表
}
public long getProductId() { return productId; }
public void setProductId(long productId) { this.productId = productId; }
public List getProductSublist() { return productSublist; }
public void setProductSublist(List productSublist) { this.productSublist = productSublist; }
// ... 其他getter/setter
}
public class ProductSub {
private long productId;
private long productSubId;
private String lineItemName;
private BigDecimal subCost;
// 构造函数、Getter和Setter（为简洁省略）
public ProductSub(long productId, long productSubId, String lineItemName, BigDecimal subCost) {
this.productId = productId;
this.productSubId = productSubId;
this.lineItemName = lineItemName;
this.subCost = subCost;
}
public long getProductId() { return productId; }
public void setProductId(long productId) { this.productId = productId; }
// ... 其他getter/setter
} 一个常见的、直观的实现方式是遍历 Product 列表，对于每一个 Product 对象，再遍历或过滤 ProductSub 列表，找出所有匹配的子项，然后将其设置到 Product 对象中。
ListproductList = /* 从服务获取 Product 列表 */; List productSubList = /* 从服务获取 ProductSub 列表 */; // 初始实现方式 for (Product productItem : productList){ List productSubItems = productSubList.stream() .filter(x -> x.getProductId() == productItem.getProductId()) .collect(Collectors.toList()); productItem.setProductSubList(productSubItems); }
初始实现的问题分析
上述初始实现虽然逻辑清晰，但在性能上存在明显的瓶颈。假设 productList 的大小为 n，productSubList 的大小为 m。在每次外层循环中，我们都会对 productSubList 进行一次完整的流式过滤和收集操作。这意味着，对于每一个 Product，我们都需要遍历（或部分遍历，取决于过滤器的实现）m 个 ProductSub 对象。
因此，这种方法的整体时间复杂度为 *O(n m)**。当 n 和 m 都较大时，例如各有数千甚至数万条记录，这种平方级别的复杂度会导致非常显著的性能下降，甚至可能造成应用程序响应缓慢或内存溢出。
立即学习“Java免费学习笔记（深入）”；
优化的解决方案：使用哈希映射
为了提高效率，我们可以利用哈希映射（HashMap）的O(1)平均时间复杂度查找特性。核心思想是：首先对 productSubList 进行一次预处理，将其中的 ProductSub 对象按照 productId 分组存储到一个 Map 中。这样，每个 productId 都会对应一个 ProductSub 列表。之后，我们只需遍历 productList 一次，通过 productId 从 Map 中直接获取对应的 ProductSub 列表即可。
这种方法的步骤如下：
- 创建一个 Map
>，其中键是 productId，值是该 productId 下所有 ProductSub 对象的列表。 - 遍历 productSubList，将每个 ProductSub 对象添加到其对应 productId 的列表中，并存储在 Map 中。
- 遍历 productList，对于每个 Product 对象，使用其 productId 从 Map 中查找对应的 ProductSub 列表，并将其设置到 Product 对象的 productSublist 属性中。
以下是优化后的代码示例：
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class ProductListAssociator {
public static void associateProductSublists(List productList, List productSubList) {
// 步骤1 & 2: 预处理 ProductSub 列表，将其按 productId 分组到 Map 中
Map> productSubMap = new HashMap<>();
for (ProductSub productSub : productSubList) {
// 使用 computeIfAbsent 确保如果键不存在，则创建一个新的 ArrayList
productSubMap.computeIfAbsent(productSub.getProductId(), k -> new ArrayList<>()).add(productSub);
}
// 步骤3: 遍历 Product 列表，从 Map 中获取对应的子列表并设置
for (Product product : productList) {
// 从 Map 中获取子列表，如果不存在则返回空列表，避免 NPE
List associatedSubList = productSubMap.getOrDefault(product.getProductId(), new ArrayList<>());
product.setProductSubList(associatedSubList);
}
}
// 示例用法
public static void main(String[] args) {
// 模拟数据
List products = new ArrayList<>();
products.add(new Product(1L, "Laptop", new BigDecimal("1200.00")));
products.add(new Product(2L, "Mouse", new BigDecimal("25.00")));
products.add(new Product(3L, "Keyboard", new BigDecimal("75.00")));
List productSubs = new ArrayList<>();
productSubs.add(new ProductSub(1L, 101L, "CPU i7", new BigDecimal("400.00")));
productSubs.add(new ProductSub(1L, 102L, "RAM 16GB", new BigDecimal("100.00")));
productSubs.add(new ProductSub(2L, 201L, "Wireless Mouse", new BigDecimal("20.00")));
productSubs.add(new ProductSub(1L, 103L, "SSD 512GB", new BigDecimal("80.00")));
productSubs.add(new ProductSub(3L, 301L, "Mechanical Keyboard", new BigDecimal("70.00")));
System.out.println("--- 关联前 ---");
products.forEach(p -> System.out.println("Product ID: " + p.getProductId() + ", Sublist Size: " + p.getProductSublist().size()));
associateProductSublists(products, productSubs);
System.out.println("\n--- 关联后 ---");
products.forEach(p -> {
System.out.println("Product ID: " + p.getProductId() + ", Sublist Size: " + p.getProductSublist().size());
p.getProductSublist().forEach(sub -> System.out.println(" - Sub ID: " + sub.getProductSubId() + ", Name: " + sub.getLineItemName()));
});
}
} 性能效益分析
优化后的方法，其时间复杂度显著降低。
- 构建 productSubMap 的过程需要遍历 productSubList 一次，时间复杂度为 O(m)。
- 遍历 productList 并从 Map 中获取子列表的过程需要遍历 productList 一次，每次 Map 查找的平均时间复杂度为 O(1)，所以这部分的时间复杂度为 O(n)。
因此，整体的时间复杂度为 O(n + m)。与初始的 O(n * m) 相比，这是一个巨大的改进，尤其是在 n 和 m 值较大的情况下。例如，如果 n=1000, m=1000，初始方法需要大约 1,000,000 次操作，而优化方法只需要大约 2,000 次操作。
注意事项与最佳实践
- 空子列表处理：在从 Map 中获取子列表时，如果某个 productId 在 productSubMap 中不存在（即该产品没有任何子项），map.get(productId) 将返回 null。为了避免 NullPointerException，可以使用 map.getOrDefault(product.getProductId(), new ArrayList()) 来确保总是返回一个非空的 List，即使是空列表。
- 内存消耗：虽然哈希映射方案在时间复杂度上更优，但它需要额外的内存来存储 productSubMap。对于极大规模的 productSubList，这可能会是一个考虑因素。然而，在大多数实际应用中，这种内存开销通常是可接受的，并且其带来的性能提升远超内存成本。
-
Java 8 Stream API 的 Collectors.groupingBy：对于构建 productSubMap，Java 8 提供了更简洁的 Stream API 方式：
Map
这种方式同样能达到 O(m) 的时间复杂度，并且代码更具声明性。
- 线程安全：如果 productList 和 productSubList 是在多线程环境下共享并修改的，需要考虑线程安全问题，例如使用并发集合或适当的同步机制。但在上述单次关联操作中，如果源列表是不可变的或仅在当前方法作用域内使用，则无需额外处理。
总结
在Java中处理父子列表关联的场景时，选择合适的算法和数据结构至关重要。直接的嵌套循环或在循环内部进行过滤操作，虽然直观，但其 O(n * m) 的时间复杂度在数据量较大时会成为性能瓶颈。通过引入哈希映射进行预处理，将子列表按关联ID分组，我们可以将时间复杂度优化到 O(n + m)，从而实现更高效、更具扩展性的数据关联操作。这种模式不仅适用于产品与子项的场景，也广泛适用于其他一对多关系的数据集合关联。
