HashMap优化嵌套循环技巧

本篇文章给大家分享《HashMap优化嵌套循环：Java列表转换技巧》，覆盖了文章的常见基础知识，其实一个语言的全部知识点一篇文章是不可能说完的，但希望通过这些问题，让读者对自己的掌握程度有一定的认识(B 数)，从而弥补自己的不足，更好的掌握它。

本文旨在通过使用 HashMap 优化嵌套循环，显著提升 Java 对象列表处理的效率。我们将针对包含嵌套对象列表的场景，演示如何将传统的双重循环结构转换为基于 HashMap 的查找方式，从而降低时间复杂度，提高程序性能。本文将提供详细的代码示例和步骤说明，帮助开发者理解并应用这种优化技巧。

在处理 Java 对象列表时，嵌套循环常常会导致性能瓶颈，尤其是在数据量较大的情况下。传统的双重循环时间复杂度为 O(n*m)，其中 n 和 m 分别是两个列表的长度。通过引入 HashMap，可以将查找的时间复杂度降低到接近 O(1)，从而显著提升整体性能。

以下示例将演示如何将包含嵌套对象列表的双重循环转换为使用 HashMap 的方式。假设我们有两个类 Object1 和 Object2，Object1 包含一个 Object2 的列表。

import java.util.*;
import java.util.stream.Collectors;

public class Object1 {

    private String name;
    private String xyz;
    private List<Object2> listObject2;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getXyz() {
        return xyz;
    }

    public void setXyz(String xyz) {
        this.xyz = xyz;
    }

    public List<Object2> getListObject2() {
        return listObject2;
    }

    public void setListObject2(List<Object2> listObject2) {
        this.listObject2 = listObject2;
    }

    @Override
    public String toString() {
        return "Object1{" +
                "name='" + name + '\'' +
                ", xyz='" + xyz + '\'' +
                ", listObject2=" + listObject2 +
                '}';
    }
}

public class Object2 {

    private String name;
    private String abc;
    private String def;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getAbc() {
        return abc;
    }

    public void setAbc(String abc) {
        this.abc = abc;
    }

    public String getDef() {
        return def;
    }

    public void setDef(String def) {
        this.def = def;
    }

    @Override
    public String toString() {
        return "Object2{" +
                "name='" + name + '\'' +
                ", abc='" + abc + '\'' +
                ", def='" + def + '\'' +
                '}';
    }
}

现在，我们有一个 fillNestedObject 方法，它使用嵌套循环来填充 Object1 中的 listObject2。

public class Main {

    public static void fillNestedObject(List<Object1> listObject1, List<Object2> listObject2) {
        for (Object1 object1 : listObject1) {
            List<Object2> tmpList = new ArrayList<>();
            for (Object2 object2 : listObject2) {
                if (object1.getName().equals(object2.getName())) {
                    tmpList.add(object2);
                }
            }
            object1.setListObject2(tmpList);
        }
    }

    public static void fillNestedObjectWithHashMap(List<Object1> listObject1, List<Object2> listObject2) {
        // Create a map of Object2 lists, keyed by name.
        Map<String, List<Object2>> object2Map = listObject2.stream()
                .collect(Collectors.groupingBy(Object2::getName));

        // Iterate over Object1 list and set the corresponding Object2 list.
        for (Object1 object1 : listObject1) {
            object1.setListObject2(object2Map.getOrDefault(object1.getName(), new ArrayList<>()));
        }
    }

    public static void main(String[] args) {
        // Example usage
        List<Object1> listObject1 = new ArrayList<>();
        List<Object2> listObject2 = new ArrayList<>();

        // Populate the lists with sample data
        Object1 obj1_1 = new Object1();
        obj1_1.setName("A");
        Object1 obj1_2 = new Object1();
        obj1_2.setName("B");
        listObject1.add(obj1_1);
        listObject1.add(obj1_2);

        Object2 obj2_1 = new Object2();
        obj2_1.setName("A");
        Object2 obj2_2 = new Object2();
        obj2_2.setName("A");
        Object2 obj2_3 = new Object2();
        obj2_3.setName("B");
        listObject2.add(obj2_1);
        listObject2.add(obj2_2);
        listObject2.add(obj2_3);

        // Fill using nested loops
        fillNestedObject(listObject1, listObject2);
        System.out.println("Filled using nested loops:");
        System.out.println(listObject1);

        // Reset listObject1
        listObject1.forEach(obj -> obj.setListObject2(null));

        // Fill using HashMap
        fillNestedObjectWithHashMap(listObject1, listObject2);
        System.out.println("Filled using HashMap:");
        System.out.println(listObject1);
    }
}

优化步骤

1. 创建 HashMap： 首先，将 listObject2 转换为一个 HashMap，其中 key 是 Object2 的 name 属性，value 是具有相同 name 属性的 Object2 列表。这可以通过 Java 8 的 Stream API 轻松实现。

   Map<String, List<Object2>> object2Map = listObject2.stream()
           .collect(Collectors.groupingBy(Object2::getName));

2. 使用 HashMap 填充： 然后，遍历 listObject1，并使用 HashMap 查找与 Object1 的 name 属性匹配的 Object2 列表。

   for (Object1 object1 : listObject1) {
       object1.setListObject2(object2Map.getOrDefault(object1.getName(), new ArrayList<>()));
   }

完整优化后的方法

将上述步骤整合到 fillNestedObjectWithHashMap 方法中：

public static void fillNestedObjectWithHashMap(List<Object1> listObject1, List<Object2> listObject2) {
    // Create a map of Object2 lists, keyed by name.
    Map<String, List<Object2>> object2Map = listObject2.stream()
            .collect(Collectors.groupingBy(Object2::getName));

    // Iterate over Object1 list and set the corresponding Object2 list.
    for (Object1 object1 : listObject1) {
        object1.setListObject2(object2Map.getOrDefault(object1.getName(), new ArrayList<>()));
    }
}

性能分析

• 原始方法（嵌套循环）： 时间复杂度为 O(n*m)，其中 n 是 listObject1 的大小，m 是 listObject2 的大小。
• 优化方法（HashMap）： 创建 HashMap 的时间复杂度为 O(m)，遍历 listObject1 的时间复杂度为 O(n)，HashMap 查找的时间复杂度接近 O(1)。因此，总时间复杂度为 O(n + m)，在 n 和 m 都很大时，性能提升非常显著。

注意事项

• 确保 Object2 的 name 属性是唯一标识，如果不是，需要考虑更复杂的 HashMap 结构，例如使用 List 作为 key。
• 如果 listObject2 经常变化，需要考虑 HashMap 的维护成本。
• 在数据量较小的情况下，HashMap 的额外开销可能抵消性能提升，因此需要根据实际情况进行评估。

总结

通过使用 HashMap 优化嵌套循环，可以显著提高 Java 对象列表处理的效率。这种方法尤其适用于需要频繁查找和匹配的场景。在实际开发中，需要根据具体情况选择合适的优化策略，并进行性能测试，以确保达到最佳效果。

以上就是《HashMap优化嵌套循环技巧》的详细内容，更多关于的资料请关注golang学习网公众号！