问题描述
在实际的软件开发中，我们经常遇到需要将具有一对多关系的子实体集合关联到其对应的父实体上的场景。例如，一个product（产品）可能包含多个productsub（产品子项）。当我们从不同的服务或数据源获取到独立的product列表和productsub列表时，需要将每个productsub正确地分配给其所属的product。
为了更好地理解，我们定义以下两个实体类：
public class Product {
private long productId;
private String productName;
private BigDecimal costAmount;
private List productSublist; // 用于存储子项
// 构造函数、Getter和Setter方法省略
}
public class ProductSub {
private long productId; // 指向父Product的ID
private long productSubId;
private String lineItemName;
private BigDecimal subCost;
// 构造函数、Getter和Setter方法省略
} 初始实现（低效）
一种直观的实现方式是遍历Product列表，并在每次迭代中，从ProductSub总列表中过滤出与当前Product匹配的子项。
ListproductList = ...; // 从服务获取的产品列表 List productSubList = ...; // 从服务获取的产品子项列表 for (Product productItem : productList) { // 为每个产品过滤并收集其子项 List productSubItems = productSubList.stream() .filter(x -> x.getProductId() == productItem.getProductId()) .collect(Collectors.toList()); productItem.setProductSubList(productSubItems); }
这种方法虽然能够正确实现功能，但其效率较低。对于productList中的每个productItem，我们都需要遍历（或流式处理）整个productSubList来查找匹配项。如果productList有n个元素，productSubList有m个元素，那么这种方法的*时间复杂度为O(n m)**。当n和m都很大时，性能瓶颈会非常明显。
优化策略：使用哈希映射
为了提高效率，我们可以利用哈希映射（HashMap）的快速查找特性。核心思想是：首先对productSubList进行一次预处理，将其中的ProductSub对象按照productId分组，存储在一个Map中。这样，每个productId都对应一个ProductSub列表。之后，当遍历Product列表时，我们可以通过productId直接从Map中以O(1)的平均时间复杂度获取到对应的ProductSub列表，避免了重复的全局遍历。
立即学习“Java免费学习笔记（深入）”；
优化后的实现
以下是使用HashMap进行优化的实现示例：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional; // 用于处理map.get()可能返回null的情况
public class ProductAssociator {
public void associateProductSubs(List productList, List productSubList) {
// 1. 构建ProductId到ProductSub列表的映射
Map> productSubMap = new HashMap<>();
for (ProductSub productSub : productSubList) {
// 使用computeIfAbsent确保如果键不存在，则创建一个新的ArrayList
productSubMap.computeIfAbsent(productSub.getProductId(), k -> new ArrayList<>()).add(productSub);
}
// 2. 遍历Product列表，从映射中获取对应的子项
for (Product product : productList) {
// 获取当前产品的子项列表，如果不存在则设置为空列表
List subs = productSubMap.get(product.getProductId());
product.setProductSubList(Optional.ofNullable(subs).orElse(new ArrayList<>()));
}
}
// 示例用法
public static void main(String[] args) {
// 模拟数据
List products = new ArrayList<>();
products.add(new Product(1L, "Laptop", BigDecimal.valueOf(1200)));
products.add(new Product(2L, "Mouse", BigDecimal.valueOf(25)));
products.add(new Product(3L, "Keyboard", BigDecimal.valueOf(75)));
List productSubs = new ArrayList<>();
productSubs.add(new ProductSub(1L, 101L, "CPU", BigDecimal.valueOf(500)));
productSubs.add(new ProductSub(1L, 102L, "RAM", BigDecimal.valueOf(200)));
productSubs.add(new ProductSub(2L, 201L, "Wireless", BigDecimal.valueOf(15)));
productSubs.add(new ProductSub(1L, 103L, "SSD", BigDecimal.valueOf(150)));
ProductAssociator associator = new ProductAssociator();
associator.associateProductSubs(products, productSubs);
// 打印结果以验证
for (Product p : products) {
System.out.println("Product: " + p.getProductName() + " (ID: " + p.getProductId() + ")");
if (p.getProductSublist() != null && !p.getProductSublist().isEmpty()) {
for (ProductSub ps : p.getProductSublist()) {
System.out.println(" - SubItem: " + ps.getLineItemName() + " (SubID: " + ps.getProductSubId() + ")");
}
} else {
System.out.println(" - No sub-items.");
}
}
}
} 代码解析：
-
构建映射：
- 我们创建了一个HashMap
>，其中键是productId，值是该产品对应的ProductSub列表。 - 遍历productSubList一次。
- map.computeIfAbsent(productSub.getProductId(), k -> new ArrayList())：这是一个非常高效的方法。如果productSub.getProductId()作为键在map中不存在，它会创建一个新的ArrayList并将其与该键关联；如果键已经存在，它会返回与该键关联的现有列表。然后，我们将当前的productSub添加到这个列表中。
- 我们创建了一个HashMap
-
关联子项：
- 遍历productList一次。
- 对于每个Product，使用productSubMap.get(product.getProductId())直接获取其对应的ProductSub列表。
- Optional.ofNullable(subs).orElse(new ArrayList())：这是一个健壮的处理方式，确保即使某个Product没有对应的ProductSub，其productSublist字段也不会被设置为null，而是被设置为一个空的ArrayList，避免潜在的NullPointerException。
性能分析与注意事项
这种优化后的方法的时间复杂度为O(n + m)，其中n是productList的大小，m是productSubList的大小。这是因为我们只遍历了productSubList一次来构建映射，然后遍历了productList一次来关联子项。与O(n * m)相比，当n和m较大时，性能提升是巨大的。
注意事项：
- 内存消耗： 使用HashMap会占用额外的内存来存储映射。对于非常大的productSubList，需要考虑内存限制。然而，通常情况下，这种内存开销是可接受的，并且其带来的性能收益远大于开销。
- 键的唯一性与散列： productId作为HashMap的键，其类型Long已正确实现了hashCode()和equals()方法，保证了哈希映射的正确性。
- 空列表处理： 确保当某个父产品没有子项时，其productSublist被设置为一个空列表而不是null，这有助于避免后续代码中的NullPointerException。Optional.ofNullable().orElse()模式是一个很好的实践。
- 数据源一致性： 这种方法假设productSubList中包含所有可能需要关联的子项。如果数据源是数据库，并且数据量极其庞大，考虑在数据库层面使用JOIN操作来预先关联数据，减少应用层的数据传输和处理负担。
总结
在Java中处理父子列表关联时，采用哈希映射（HashMap）进行预处理是一种高效且推荐的策略。它将时间复杂度从O(n * m)显著优化到O(n + m)，极大地提升了处理大规模数据集时的性能。通过构建一个以父ID为键的子项列表映射，我们可以实现O(1)的平均时间查找，从而避免了重复的全局遍历，使得代码更加高效、专业。
