如何根据不同Java类的字段比较两个"等价"集合？

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根据指定的字段子集,判断两者是否"等价"(*)的最简单方法是什么？

(*)使用"等同"一词而不是"相等",因为这是语境 - 即这种"等同"可以在另一个语境中有不同的定义.

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

首选解决方案:使用的方法对于任何Collection类型都应该是通用的.理想情况下Java 7仅限于使用它(但Java 8可能对其他人有额外的兴趣).很高兴使用Guava或Apache Commons,但不想使用更加模糊的外部库.

Answer 1

这是使用lambdas和高阶函数的Java 8版本.可能使用匿名内部类而不是lambdas将其转换为Java 7.(我相信大多数IDE都有重构操作来实现这一点.)我将把它留作感兴趣读者的练习.

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

1. 给定两个不同类型的对象,通过检查每个对象的相应字段来评估它们.这与已经由JDK库API定义的"等于"和"比较"操作不同,因此我将使用术语"等效".

2. 给定两个包含这些类型元素的集合,确定它们对于该术语的某些定义是否"等于".这实际上非常微妙; 见下面的讨论.

1.等价

鉴于类型的两个对象T和U我们想以确定它们是否是等价的.结果是布尔值.这可以用类型的函数表示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 .以下是如何使用OP示例中的类int和String字段来创建一个评估等价的函数.为此,最好将函数存储在一个变量中,而不是使用它,尽管这可能都是内联的(我认为这会让它变得不可读):

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在其他答案中的一些建议,似乎我们希望两个集合中的元素以某种方式一一对应.我会称这是一个可能在数学上不精确的双射,但它似乎足够接近.此外,每对元素之间的对应关系应该是如上定义的等价.

计算这个有点微妙,因为我们有自己的等价关系.我们不能使用许多内置集合操作,因为它们都使用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的答案中使用的算法非常相似,尽管我已经将等价函数提取到方法参数中.唉,因为我的等价函数可以有嵌套的等价函数,这意味着我无法探测地图(由相等定义).相反,我必须搜索地图的键,这意味着算法是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.

Answer 2

另一种可能的解决方案是使用谓词编写一个简单的比较方法(因此您可以明确指定两个类的条件在您的术语上相似).我在Java 8中创建了这个:

<T, U> boolean compareCollections(Collection<T> coll1, Collection<U> coll2, BiPredicate<T, U> predicate) {

    return coll1.size() == coll2.size()
            && coll1.stream().allMatch(
            coll1Item -> coll2.stream().anyMatch(col2Item -> predicate.test(coll1Item, col2Item))
    );
}

如您所见,它比较了大小,然后检查集合中的每个元素是否在第二个集合中都有对应物(虽然它不是比较顺序).它是在Java 8中,但您可以通过实现一个简单的BiPredicate代码将其移植到Java 7,allMatch和anyMatch(每个代码的一个for循环应该足够)

编辑:Java 7代码:

<T, U> boolean compareCollections(Collection<T> coll1, Collection<U> coll2, BiPredicate<T, U> predicate) {

        if (coll1.size() != coll2.size()) {
            return false;
        }

        for (T item1 : coll1) {
            boolean matched = false;
            for (U item2 : coll2) {
                if (predicate.test(item1, item2)) {
                    matched = true;
                }
            }

            if (!matched) {
                return false;
            }
        }
        return true;

    }}
interface BiPredicate <T, U> {
    boolean test(T t, U u);
}

这是一个用法示例.