As it can be seen in Figure 7.1,
the efficiency gain of a hash table with respect to a linked list containing
all elements is based on the fact that the length of the collision list
should be significantly shorter than the total number
of elements. If a table has all collision chains with identical length, the
search time is greatly reduced. However, the opposite extreme case where
all elements are contained in one single collision
chain the performance is similar to the implementation using a
linked list.
This observation suggests that the hash function not only
computes an index for the table, but, for a large number of elements
it must produce these index as uniformly distributed as possible
. The hash function specification is very simple. In the case
considered in this problem is a function that given a passport number
returns an index within the correct table range, and this index must be
identical for identical strings. The computation performed by this function
must be as efficient as possible because it is needed for every table
access.
