java - 如何根据来自不同 Java 类的字段比较 "equivalence"的两个集合？

Question

给定任意两个类，例如ClassA和 ClassB以下:

class ClassA {
    private int intA;
    private String strA;
    private boolean boolA;
    // Constructor
    public ClassA (int intA, String strA, boolean boolA) {
        this.intA = intA; this.strA = strA; this.boolA = boolA;
    } // Getters and setters etc. below...
}

class ClassB {
    private int intB;
    private String strB;
    private boolean boolB;
    // Constructor
    public ClassB (int intB, String strB, boolean boolB) {
        this.intB = intB; this.strB = strB; this.boolB = boolB;
    } // Getters and setters etc. below...
}

和任意两个不同 Collection类型，一种带有 ClassA元素和其他 ClassB元素，例如:

List<Object> myList = Arrays.asList(new ClassA(1, "A", true),
                                    new ClassA(2, "B", true));
Set<Object> mySet = new HashSet<Object>(
                      Arrays.asList(new ClassB(1, "A", false),
                                    new ClassB(2, "B", false)));

判断两者是否一致的最简单方法是什么Collection s 在指定的字段子集方面是“等效的”(*)？

(*) 使用“等效”一词而不是“相等”，因为这是上下文 - 即这种“等效”在另一个上下文中可能有不同的定义。

上面的工作示例:
假设我们指定 intA和 strA应该与 intB 匹配和 strB分别(但可以忽略 boolA/boolB 值)。这将使上面定义的两个集合对象被认为是等效的——但是如果一个元素被添加到其中一个集合中或从其中一个集合中删除，那么它们将不再是。

首选方案:所使用的方法对于任何 Collection 都应该是通用的。类型。理想情况下，Java 7 仅限于使用它(但其他人可能会对 Java 8 感兴趣)。乐于使用 Guava 或 Apache Commons，但不想使用更晦涩的外部库。

Answer 1

这是使用 lambda 和高阶函数的 Java 8 版本。可能可以使用匿名内部类而不是 lambda 将其转换为 Java 7。 (我相信大多数 IDE 都有执行此操作的重构操作。)我将把它留给感兴趣的读者作为练习。

这里实际上有两个不同的问题:

给定两个不同类型的对象，通过检查每个对象的相应字段来评估它们。这与 JDK 库 API 已经定义的“equals”和“compare”操作不同，因此我将使用术语“equivalent”代替。

给定两个包含这些类型元素的集合，确定它们对于该术语的某些定义是否“相等”。这实际上非常微妙；请参阅下面的讨论。

1.等价

给定两个类型的对象 T和 U我们想确定它们是否相等。结果是一个 boolean 值。这可以用类型为 BiPredicate<T,U> 的函数表示。 .但我们不一定能直接检查对象；相反，我们需要从每个对象中提取各自的字段，并相互评估提取结果。如果字段提取自 T类型为 TR以及从 U 中提取的字段类型为 UR ，那么提取器由函数类型表示

Function<T, TR>
Function<U, UR>

现在我们已经提取了 TR 类型的结果和 UR .我们可以拨打 equals()对他们，但这是不必要的限制。相反，我们可以提供另一个等价函数，该函数将被调用以相互评估这两个结果。那是一个 BiPredicate<TR,UR> .

鉴于所有这些，我们可以编写一个高阶函数，它接受所有这些函数并为我们生成和等价函数(包含通配符以确保完整性):

static <T,U,TR,UR> BiPredicate<T,U> equiv(Function<? super T, TR> tf,
                                          Function<? super U, UR> uf,
                                          BiPredicate<? super TR, ? super UR> pred) {
    return (t, u) -> pred.test(tf.apply(t), uf.apply(u));
}

使用 equals() 评估字段提取的结果可能是一种常见情况。 ，所以我们可以为此提供一个重载:

static <T,U> BiPredicate<T,U> equiv(Function<? super T, ?> tf,
                                    Function<? super U, ?> uf) {
    return (t, u) -> equiv(tf, uf, Object::equals).test(t, u);
}

我本可以提供另一个类型变量 R作为两个函数的结果类型，以确保它们是相同的类型，但事实证明这不是必需的。自 equals()在 Object 上定义它需要一个 Object参数，我们实际上并不关心函数返回类型是什么，因此是通配符。

以下是如何使用它仅使用字符串字段来评估 OP 的示例类:

ClassA a = ... ;
ClassB b = ... ;
if (equiv(ClassA::getStrA, ClassB::getStrB).test(a, b)) {
    // they're equivalent
}

作为一种变体，我们可能还需要原始特化以避免不必要的装箱:

static <T,U> BiPredicate<T,U> equivInt(ToIntFunction<? super T> tf,
                                       ToIntFunction<? super U> uf) {
    return (t, u) -> tf.applyAsInt(t) == uf.applyAsInt(u);
}

这让我们可以基于单个字段构建等价函数。如果我们想基于多个字段来评估等价性怎么办？我们可以通过链接 and() 来组合任意数量的 BiPredicates方法。以下是如何创建一个使用 int 来计算等价性的函数。和 String来自 OP 示例的类的字段。为此，最好将函数存储在一个变量中而不是使用它，尽管这可能全部内联(我认为这会使它不可读):

BiPredicate<ClassA, ClassB> abEquiv =
    equivInt(ClassA::getIntA, ClassB::getIntB)
        .and(equiv(ClassA::getStrA, ClassB::getStrB));

if (abEquiv.test(a, b)) {
    // they're equivalent
}

最后一个例子，在为两个类创建等价函数时，能够为字段提取结果提供等价函数是非常强大的。例如，假设我们要提取两个 String 字段，如果提取的字符串是相等的，忽略大小写，则认为它们是等效的。以下代码导致 true :

equiv(ClassA::getStrA, ClassB::getStrB, String::equalsIgnoreCase)
    .test(new ClassA(2, "foo", true),
          new ClassB(3, "FOO", false))

2.“平等”系列

第二部分是评估两个集合在某种意义上是否“相等”。问题是在集合框架中，相等的概念被定义为一个 List 只能等于另一个 List，而一个 Set 只能等于另一个 Set。因此，其他类型的 Collection 永远不能等于 List 或 Set。参见 Collection.equals() 的规范对这一点的一些讨论。

这显然与 OP 想要的不一致。正如 OP 所建议的那样，我们并不真正想要“平等”，但我们想要一些需要为其提供定义的其他属性。基于 OP 的示例，以及 Przemek Gumula 的其他答案中的一些建议和 janos ，似乎我们希望两个集合中的元素以某种方式一一对应。我称之为 bijection这在数学上可能不精确，但似乎足够接近。此外，每对元素之间的对应关系应该是如上定义的等效。

计算这个有点微妙，因为我们有自己的等价关系。我们不能使用许多内置的 Collections 操作，因为它们都使用 equals() .我的第一次尝试是这样的:

// INCORRECT
static <T,U> boolean isBijection(Collection<T> c1,
                                 Collection<U> c2,
                                 BiPredicate<? super T, ? super U> pred) {
    return c1.size() == c2.size() &&
           c1.stream().allMatch(t -> c2.stream()
                                       .anyMatch(u -> pred.test(t, u)));
}

(这与 Przemek Gumula 给出的基本相同。)这有问题，归结为一个集合中的多个元素对应另一个集合中的单个元素的可能性，从而使元素不匹配。如果给定两个多重集，使用相等作为等价函数，这会产生奇怪的结果:

{a x 2, b}    // essentially {a, a, b}
{a, b x 2}    // essentially {a, b, b}

这个函数认为这两个多重集是一个双射，这显然不是这种情况。如果等价函数允许多对一匹配，则会出现另一个问题:

Set<String> set1 = new HashSet<>(Arrays.asList("foo", "FOO", "bar"));
Set<String> set2 = new HashSet<>(Arrays.asList("fOo", "bar", "quux"));

isBijection(set1, set2, equiv(s -> s, s -> s, String::equalsIgnoreCase))

结果是true ，但如果集合以相反的顺序给出，结果是 false .这显然是错误的。

另一种算法是创建一个临时结构并删除匹配的元素。该结构必须考虑重复项，因此我们需要递减计数，并且仅在计数达到零时才删除元素。幸运的是，Java 8 的各种特性使这变得非常简单。这与 janos 的答案中使用的算法非常相似。 ，虽然我已经将等价函数提取到方法参数中。唉，因为我的等价函数可以有嵌套的等价函数，这意味着我不能探测映射(由等式定义)。相反，我必须搜索 map 的键，这意味着算法是 O(N^2)。那好吧。

然而，代码非常简单。首先，使用 groupingBy 从第二个集合生成频率图.然后，迭代第一个集合的元素，并搜索频率图的键以查找等效项。如果找到一个，则减少它的出现次数。注意 null 的返回值来自传递给 Map.compute() 的重映射函数.这具有删除条目的副作用，而不是将映射设置为 null .这有点像 API hack，但它非常有效。

对于第一个集合中的每个元素，必须在第二个集合中找到一个等价的元素，否则就会退出。在处理完第一个集合的所有元素后，频率图中的所有元素也应该已被处理，因此只需测试它是否为空。

这是代码:

static <T,U> boolean isBijection(Collection<T> c1,
                                 Collection<U> c2,
                                 BiPredicate<? super T, ? super U> pred) {
    Map<U, Long> freq = c2.stream()
                          .collect(Collectors.groupingBy(u -> u, Collectors.counting()));
    for (T t : c1) {
        Optional<U> ou = freq.keySet()
                             .stream()
                             .filter(u -> pred.test(t, u))
                             .findAny();
        if (ou.isPresent()) {
            freq.compute(ou.get(), (u, c) -> c == 1L ? null : c - 1L);
        } else {
            return false;
        }
    }

    return freq.isEmpty();
}

这个定义是否正确尚不完全清楚。但直觉上似乎是人们想要的。不过它很脆弱。如果等价函数不对称，isBijection将失败。还有一些自由度没有考虑在内。例如，假设集合是

{a, b}
{x, y}

和 a等同于 x和 y ，但是 b仅相当于 x .如 a匹配到 x , isBijection 的结果是 false .但如果 a匹配到 y ，结果将是 true .

放在一起

这是 OP 的示例，使用 equiv() 编码, equivInt() , 和 isBijection职能:

List<ClassA> myList = Arrays.asList(new ClassA(1, "A", true),
                                    new ClassA(2, "B", true));

Set<ClassB> mySet = new HashSet<>(Arrays.asList(new ClassB(1, "A", false),
                                                new ClassB(2, "B", false)));

BiPredicate<ClassA, ClassB> abEquiv =
    equivInt(ClassA::getIntA, ClassB::getIntB)
        .and(equiv(ClassA::getStrA, ClassB::getStrB));

isBijection(myList, mySet, abEquiv)

这样做的结果是 true .