Efficient way to equiJoin Collections of objects

Say we have 2 Collections (that fit into memory) with elements that can be tested for equality (not necessarily overriding equals()), e.g.

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

And some non-parallel method equiJoin(c1, c2) that gives you a Collection<Tuple<Integer, Integer>> of elements in both lists that are equal ((2,2), (3,3), (5,5)). See 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. And let's assume, the equality boils down to simple types and doesn't create a whole lot of complexity on its own.

Joins have been chewed on to death in the area of relational databases, but not so much in general programming as it seems.

What we often see (like 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 it also does nested loops (it actually allows for arbitrary functions, not just equality, that's a reason for nested loop).

    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));
            }
        }
    }

If you want to do better you go for a hash join with much nicer 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));
        }
    }

Are there aspects in the problem that can be utilized to improve which I didn't see, or are there existing algorithms/implementations that do better? Like some exotic binary encoding or reduction of search space while matching, things like that. Everything I can think of isn't really promising or likely introduces more work than it eliminates. Perhaps there's even consensus or proof that you can't do better than hash join, then that's also an answer.