equiJoin 对象集合的有效方法

Question

假设我们有 2 个集合（适合内存），其中的元素可以进行相等性测试（不一定覆盖 equals()），例如

Collection<Integer> c1 = List.of(1,2,3,4,5);
Collection<Integer> c2 = List.of(0,2,3,5,9);

还有一些非并行方法 equiJoin(c1, c2) 可以让您在两个列表中得到 Collection<Tuple<Integer, Integer>> 个相等 ((2,2), (3,3), (5,5)) 的元素。参见 this for its treatment in the RDBMS context. Creating pairs of equal integers is pretty useless, but think of of any case where lists of records, say one from a db and one from a web service call need to be matched like in this post。让我们假设，等式归结为简单的类型，并不会自行产生很多复杂性。

联接在 relational databases 领域已被反复使用，但在一般编程中并没有看起来那么多。

我们经常看到的（像here) is the nested loop approach with a not so nice run time complexity of O(M*N). I know only of one framework that incorporates equiJoin in Java streams, but it looks like它也做嵌套循环（它实际上允许任意函数，而不仅仅是相等，这是嵌套循环的原因）。

    List<Tuple<Integer, Integer>> joined = new ArrayList<>();
    for (Integer i : c1) {
        for (Integer j : c2) {
            if (i.equals(j)) {
                joined.add(new Tuple<>(i, j));
            }
        }
    }

如果你想做得更好，你可以使用更好的散列连接 O(M+N):

    List<Tuple<Integer, Integer>> joined = new ArrayList<>();

    HashMap<Integer, Integer> C1 = new HashMap<>();
    // imagine its not Integer but e.g. bank accounts and a Map<Key, Account>
    c1.forEach(i -> C1.put(i, i));

    for (Integer i : c2) {
        Integer j = C1.get(i);
        if (j != null) {
            joined.add(new Tuple<>(i, j));
        }
    }

问题中是否有我没有看到的可以用来改进的方面，或者是否有 algorithms/implementations 做得更好的现有方面？就像一些奇异的二进制编码或匹配时搜索 space 的减少，诸如此类。我能想到的一切都不是真正有希望的，或者可能引入的工作多于它消除的工作。也许甚至有共识或证明你不能比散列连接做得更好，那么这也是一个答案。

Answer 1

看起来在这种情况下，散列连接无法被击败，因为 this, this, this, this, this, this and the comments to the OP. But it can be matched, sort-merge-join（需要可比较的对象，而不仅仅是相等或不相等的对象）具有相同的运行时间复杂度，但是它无法击败散列连接实现的简单性。

还有一罐tweak the Hashmap as such, go into parallel algorithms and consider hardware related aspects (see the references here).

equiJoin 对象集合的有效方法

Efficient way to equiJoin Collections of objects

java

algorithm

collections

inner-join