An [[wp:Join_(SQL)#Inner_join|inner join]] is an operation that combines two data tables into one table, based on matching column values. The simplest way of implementing this operation is the [[wp:Nested loop join|nested loop join]] algorithm, but a more scalable alternative is the [[wp:hash join|hash join]] algorithm.
{{task heading}}
Implement the "hash join" algorithm, and demonstrate that it passes the test-case listed below.
You should represent the tables as data structures that feel natural in your programming language.
{{task heading|Guidance}}
The "hash join" algorithm consists of two steps:
# '''Hash phase:''' Create a [[wp:Multimap|multimap]] from one of the two tables, mapping from each join column value to all the rows that contain it.<br>
#* The multimap must support hash-based lookup which scales better than a simple linear search, because that's the whole point of this algorithm.
#* Ideally we should create the multimap for the ''smaller'' table, thus minimizing its creation time and memory size.
# '''Join phase:''' Scan the other table, and find matching rows by looking in the multimap created before.
<br>
In pseudo-code, the algorithm could be expressed as follows:
'''let''' ''A'' = the first input table (or ideally, the larger one)
'''let''' ''B'' = the second input table (or ideally, the smaller one)
'''let''' ''j<sub>A</sub>'' = the join column ID of table ''A''
'''let''' ''j<sub>B</sub>'' = the join column ID of table ''B''
'''let''' ''M<sub>B</sub>'' = a multimap for mapping from single values to multiple rows of table ''B'' (starts out empty)
'''let''' ''C'' = the output table (starts out empty)
The order of the rows in the output table is not significant.<br>
If you're using numerically indexed arrays to represent table rows (rather than referring to columns by name), you could represent the output rows in the form <code style="white-space:nowrap">[[27, "Jonah"], ["Jonah", "Whales"]]</code>.
