UC3M

The required structure needs to store an undetermined number of pairs, and therefore, needs to be dynamically created. The first solution we might consider is a linked list of pairs. Inserting a new pair is easy. Given a passport number and a string, a new element is created and inserted in the list. The search operation needs to traverse the list until, either the given key (passport number) or the end of the list is reached (the key is not in the list). When the number of pairs is large, this search is inefficient because a large number of elements needs to be processed.

A second option to perform quick searches would be to store all the data in an array and use the passport number as the index. In this case, check if a number is in the table would simply require to check if it has a string stored. Inserting a new pair (passport, message) would also be very fast because it would simply require to store the string in the corresponding array position. But the problem with this solution is that the passport number can be a large integer, and therefore the size of the table goes beyond what is acceptable.

The hash table offers a compromise for this situation. The (key, value) pairs are still stored in a table, but the size is less than the ideal. In our example, a table is used but the size is not the maximum number of passports, but a smaller dimension.