Hash tables study guide

A method for solving hash-table questions

When given a hash table problem, separate the information into three parts: the key, the hashing algorithm, and the value mapped to the key. First apply the stated hashing algorithm to the key. Next use the resulting hash to identify the relevant table position. Finally check whether another key has already produced that same hash.

For a simple algorithm such as hash(key) = key mod 5, calculate the remainder after division by 5. For key 23, the result is 3, because 23 mod 5 = 3. If key 8 is also considered, 8 mod 5 = 3. These are different key values with the same hash, so they create a collision.

Reasoning about a collision

Do not decide that a collision exists merely because two keys look similar or because two values are similar. Perform the hashing calculation for each key and compare the results. A collision exists precisely when the two key values compute the same hash.

A strong explanation can be written as a chain:

1. Apply the given hashing algorithm to the first key.
2. Apply the same algorithm to the second key.
3. Compare the two hash results.
4. If the results are equal, state that a collision has occurred.
5. Apply the specified rehashing process to handle the collision.

For example, with hash(key) = key mod 5, keys 12 and 17 both produce 2. The conclusion is not that 12 and 17 are the same key. The conclusion is that both keys initially identify hash position 2, so the second placement or lookup requires rehashing according to the rule given in the question.

Explaining rehashing precisely

Rehashing is the collision-handling mechanism in this topic. It means carrying out a further hashing calculation when the original calculation leads to a position already associated with another key. In an exam, use the rehashing formula or procedure supplied by the question. Show each calculation and identify the resulting position rather than writing only that the item is moved.

The purpose of rehashing is to preserve the mapping between distinct keys and their values even when the initial hash is identical. A rehashed position is not evidence that the keys have become equal; it is the result of resolving their shared initial hash.

Exam application checklist

Before finalising an answer, check that you have:

• identified which data is the key and which is the value;
• written or used the simple hashing algorithm correctly;
• shown the arithmetic for each relevant key;
• stated the resulting hash or table position;
• identified a collision only when two key values have the same hash;
• described rehashing as the response to that collision;
• used the supplied rehashing rule rather than inventing an unsupported one.

Self-check questions

1. What is the difference between a key, a value and a hash?
2. If two different keys produce the same hash, what is this called?
3. Why is comparing the original keys important before claiming that a collision exists?
4. What calculation is performed after an initial position is unavailable because of a collision?
5. Given hash(key) = key mod 5, calculate the hashes for 11 and 16, then explain whether a collision occurs.

For the last question, 11 mod 5 = 1 and 16 mod 5 = 1, so the keys collide. A complete answer should then state that rehashing is applied to handle the collision. If a particular rehashing calculation is not supplied, explain the mechanism without claiming a specific unsupported formula.