<p>Looks like in this scenario hash join can't be beaten having seen <a href="https://cs-people.bu.edu/mathan/reading-groups/papers-classics/join.pdf" rel="nofollow noreferrer">this</a>, <a href="https://people.eecs.berkeley.edu/%7Efox/summaries/database/join.html" rel="nofollow noreferrer">this</a>, <a href="https://docs.teradata.com/reader/Ws7YT1jvRK2vEr1LpVURug/chrMh_r4k9OgT9J6rWagsA" rel="nofollow noreferrer">this</a>, <a href="https://databricks.com/de/session_na20/on-improving-broadcast-joins-in-apache-spark-sql" rel="nofollow noreferrer">this</a>, <a href="https://kafka.apache.org/23/documentation/streams/developer-guide/dsl-api.html#streams-developer-guide-dsl-joins" rel="nofollow noreferrer">this</a>, <a href="https://arxiv.org/pdf/1805.05874.pdf" rel="nofollow noreferrer">this</a> and the comments to the OP. But it can be matched, <a href="https://en.wikipedia.org/wiki/Sort-merge_join" rel="nofollow noreferrer">sort-merge-join</a> (which needs objects that are comparable, not just equal or not) has the same run time complexity, yet it can't beat the simplicity of the hash join implementation.</p>
<p>Still one can <a href="http://www.vldb.org/pvldb/vol8/p353-barber.pdf" rel="nofollow noreferrer">tweak the Hashmap</a> as such, go into parallel algorithms and consider hardware related aspects (see the references <a href="http://www.vldb.org/pvldb/vol8/p353-barber.pdf" rel="nofollow noreferrer">here</a>).</p>
Efficient way to equiJoin Collections of objects
<p>Say we have 2 Collections (that fit into memory) with elements that can be tested for equality (not necessarily overriding <code>equals()</code>), e.g.</p>
<pre><code>Collection&lt;Integer&gt; c1 = List.of(1,2,3,4,5);
Collection&lt;Integer&gt; c2 = List.of(0,2,3,5,9);
</code></pre>
<p>And some non-parallel method <code>equiJoin(c1, c2)</code> that gives you a <code>Collection&lt;Tuple&lt;Integer, Integer&gt;&gt;</code> of elements in both lists that are equal <code>((2,2), (3,3), (5,5))</code>. See <a href="https://de.wikibooks.org/wiki/Relationenalgebra_und_SQL:_Equi-Join" rel="nofollow noreferrer">this</a> 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 <a href="https://stackoverflow.com/questions/64731157/optimizing-nested-loops-for-joining-lists-while-reading-json/64731681#64731681">this post</a>. And let's assume, the equality boils down to simple types and doesn't create a whole lot of complexity on its own.</p>
<p>Joins have been chewed on to death in the area of <a href="https://en.wikipedia.org/wiki/Category:Join_algorithms" rel="nofollow noreferrer">relational databases</a>, but not so much in general programming as it seems.</p>
<p>What we often see (like <a href="https://stackoverflow.com/questions/64731157/optimizing-nested-loops-for-joining-lists-while-reading-json/64731681#64731681">here</a>) is the nested loop approach with a not so nice run time complexity of <strong>O(M*N)</strong>. I know only of one <a href="https://github.com/jOOQ/jOOL" rel="nofollow noreferrer">framework</a> that incorporates equiJoin in Java streams, but it <a href="https://github.com/jOOQ/jOOL/blob/main/jOOL/src/main/java/org/jooq/lambda/SeqImpl.java" rel="nofollow noreferrer">looks like</a> it also does nested loops (it actually allows for arbitrary functions, not just equality, that's a reason for nested loop).</p>
<pre><code>    List&lt;Tuple&lt;Integer, Integer&gt;&gt; joined = new ArrayList&lt;&gt;();
    for (Integer i : c1) {
        for (Integer j : c2) {
            if (i.equals(j)) {
                joined.add(new Tuple&lt;&gt;(i, j));
            }
        }
    }
</code></pre>
<p>If you want to do better you go for a hash join with much nicer <strong>O(M+N)</strong>:</p>
<pre><code>    List&lt;Tuple&lt;Integer, Integer&gt;&gt; joined = new ArrayList&lt;&gt;();

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

    for (Integer i : c2) {
        Integer j = C1.get(i);
        if (j != null) {
            joined.add(new Tuple&lt;&gt;(i, j));
        }
    }
</code></pre>
<p>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.</p>