Exercise 11.3.1

Suppose we wish to search a linked list of length $n$, where each element contains a key $k$ along with a hash value $h(k)$. Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key?

We can compute the hash of the key we search for, and then compare with a string in the list only if the hash value matches. We know that the same key hashes to the same hash value, so if the hash values are different, we can infer the strings are different.

It will have an effect when the strings in the list have particularly bad comparison performance against the string we search for. For example, the comparison algorithm checks the first characters, and if they differ, the second characters, etc, and the strings have a very long common prefix.