在Java中比较两个相似地图的高效方法

Question

在Java中比较两个相似地图的高效方法

3

想象一下我有两张地图：

HashMap<TestClass, Integer> map1, map2;

假设TestClass已经定义为:

class TestClass {
    int i;

    public TestClass(int i){
        this.i = i;
    }
}

以下代码用于填充地图：

map1.put(new TestClass(1), 1);
map1.put(new TestClass(2), 2);

map2.put(new TestClass(1), 1);
map2.put(new TestClass(2), 2);

我希望编写一个方法，如果两个映射包含“相同”的键和值，则返回true。在上面的示例中，我可以创建一个本地变量来存储第一个构造函数调用的结果并将其传递给第二个映射，但在我的实际应用程序中我不能这样做，因为我想比较不相等的相似对象，至少就Java的equals方法实现而言。

我之前的实现（简化）：

if(map1.size() == map2.size()){
    for(String key1 : map1.keySet()){
        if(!map1.get(key1).equals(map2.get(key1))
            return false;
    }
    return true;
} else
    return false;

对于String来说，这很好用，因为即使在不同的位置实例化两次，它们也是相等的。

但是，执行TestClass的构造函数两次会返回两个不同的对象，因此map2.get(key1)将返回null（或抛出异常，我不是完全确定），因为key1不在map2中。

为了比较两个映射，我编写了以下代码（简化）：

if(map1.size() == map2.size()){
    for(TestClass key1 : map1.keySet()){
        boolean foundEqualing = false;
        for (TestClass key2 : map2.keySet()) {
            // Search equaling 
            if (key1.i == key2.i) {
                // Check if corresponding values equal as well
                if (map1.get(key1).equals(map2.get(key2))
                    // Store that a equaling key value pair was found
                    foundEqualing = true;
                // Break if keys equaled each other
                break;
            }
        }
        // Return false if no equaling key was found or if keys equal each other but the corresponding values don't
        if (!foundEqualing)
            return false;
    }
    return true;
} else
    return false;

我对这段代码的问题在于它循环遍历了两个映射表，这对效率来说似乎非常低下。我不熟悉正确的标记符号，但是如果我没有弄错的话，操作所需时间会随着地图大小的加倍而增加四倍。

除了编写for循环之外，是否有更有效的方式来循环或过滤这些映射表呢？

我的真实代码使用反射，因此不要过分关注提供的示例。映射表的类型可能来自任何类型（唯一我知道的是它们必须实现某个接口，否则它们将被忽略）。

编辑：

我目前正在考虑使用流筛选收集语法，但我从未使用过。它是否更有效，还是内部也只是循环遍历映射表？

- Jojomatik

@Abra containsKey在这种情况下无法工作，因为两个映射中的键不相同（至少对于Java而言）。 - Jojomatik

@Abra 我只使用 equals 方法来比较值，而不是键。 - Jojomatik

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jalaj Varshney · Answer 1

如果您能在您的TestClass中实现equals方法，那么这个过程可以更加简单。您将不需要使用循环。您也可以使用Map.equals()方法。

Map.equals()方法的工作原理是使用Object.equals()方法比较键和值。这意味着只有当键和值对象都正确实现了equals()方法时，它才能正常工作。

import java.util.HashMap;
import java.util.Objects;

class Main {

    public static void main(String[] args) {
        HashMap<TestClass, Integer> map1, map2;
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        map1.put(new TestClass(1), 1);
        map1.put(new TestClass(2), 2);

        map2.put(new TestClass(1), 1);
        map2.put(new TestClass(2), 2);

        System.out.println(map1.equals(map2));
    }

}

class TestClass {
    int i;

    public TestClass(int i){
        this.i = i;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TestClass testClass = (TestClass) o;
        return i == testClass.i;
    }

    @Override
    public int hashCode() {
        return Objects.hash(i);
    }
}

编辑：如评论中所述，上述实现由于使用了反射而无法使用。可以通过通常的空间和时间交换来改善时间复杂度。

既然您必须编写比较两个对象相等的逻辑，我创建了一个带有附加值字段并在其中实现了equals逻辑的类。我正在使用HashSet来处理这个类，从而将时间复杂度从O(m*n)降低到O(max(m,n))。（假设大小为m和n）。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;

class Main {

    public static void main(String[] args) {
        HashMap<TestClass, Integer> map1, map2;
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        map1.put(new TestClass(1), 1);
        map1.put(new TestClass(2), 2);

        map2.put(new TestClass(1), 1);
        map2.put(new TestClass(2), 2);
        boolean check = checkEqual(map1, map2);
        System.out.println(check);

        //---------------------------------------

        map1 = new HashMap<>();
        map2 = new HashMap<>();
        map1.put(new TestClass(1), 1);
        map1.put(new TestClass(2), 2);

        map2.put(new TestClass(1), 1);
        map2.put(new TestClass(2), 3);
        check = checkEqual(map1, map2);
        System.out.println(check);

    }

    private static boolean checkEqual(HashMap<TestClass, Integer> map1, HashMap<TestClass, Integer> map2) {
        HashSet<TestAndValue> set = new HashSet<>();
        map1.forEach((k,v) -> set.add(new TestAndValue(k,v)));
        for(TestClass t: map2.keySet()) {
            if(!set.contains(new TestAndValue(t, map2.get(t))))
                return false;
        }
        return true;
    }


}
class TestAndValue {
    TestClass t;
    int val;

    public TestAndValue(TestClass t, int val) {
        this.t = t;
        this.val = val;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TestAndValue that = (TestAndValue) o;
        return val == that.val && t.i == that.t.i;
    }

    @Override
    public int hashCode() {
        return Objects.hash(t.i, val);
    }
}

class TestClass {
    int i;

    public TestClass(int i){
        this.i = i;
    }
}

输出结果为：

true
false

尽管实现有些混乱，但我希望它能够给你足够的想法来在线性时间内实现。