A hash table is a mechanism for the storage and quick retrieval of large amounts of data. The table itself is simply an array of m locations, T[0..m-1], stored in the computer's memory. Each data record to be stored in this array is identified by its own key k. As an example, a data record may contain a name and a phone number, with the name comprising the key. The location in which a record of data is to be stored is determined by a hash function H which maps the set of possible keys k to an integer H(k) in the range 0 to m-1. The record is then stored in the memory location T[H(k)], as long as that location is not already used. If that location is already used then a collision has occured in which the hash function has mapped...