Assume we have two tables (think as in SQL tables), where the primary key in one of them is the foreign key in the other. I'm supposed to write a simple algorithm that would imitate the joining of these two tables. I thought about iterating over each element in the primary key column in the first table, having a second loop where it checks if the foreign key matches, then store it in an external array or list. However, this would take O(N*M) and I need to find something better. There is a hint in the textbook that it involves hashing, however, I'm not sure how hashing could be implemented here or how it would make it better?
Editing to add an example:
Table Employees
|ID (Primary Key)| Name | Department|
|:---------------|:----:|----------:|
| 1 | Jack | IT |
| 2 | Amy | Finance |
Table Transactions
|Sold Product| Sold By(Foreign Key)| Sold To|
|:-----------|:-------------------:|-------:|
| TV | 1 | Mary |
| Radio | 1 | Bob |
| Mobile | 2 | Lisa |
What I want to do is write an algorithm that joins these two tables using hashing, and not anything complex, just a simple idea on how to do that.