Hash tables revision notes

Core idea

A hash table is a data structure that creates a mapping between keys and values. A key identifies a value, while a hashing algorithm calculates a hash from the key. The hash can be used to identify a position in the table where the value is stored or where it can be searched for.

For example, suppose a simple hashing algorithm is:

text hash(key) = key mod 5

For the key 12:

text 12 mod 5 = 2

The hash is 2, so the value associated with key 12 is assigned to position 2 of the hash table. The same hashing calculation can be applied when looking up the key.

Keys and values

The key is the input used by the hashing algorithm. The value is the data mapped to that key. The key and value are distinct: the key is used to identify the stored data, whereas the value is the data being mapped.

A hash table therefore represents relationships such as:

text key -> value 12 -> "record A"

The exact value is not itself the hash. The hash is calculated from the key and is used to determine a table position.

Collisions

A collision occurs when two key values compute the same hash. Using hash(key) = key mod 5:

text 12 mod 5 = 2 17 mod 5 = 2

The keys 12 and 17 are different, but both compute the hash 2. They therefore collide because they identify the same hash position.

A collision does not mean that the keys are equal, and it does not mean that their values are equal. It means only that the hashing calculation has produced the same hash for both keys.

Rehashing

Collisions are handled using rehashing. When a key produces a position already associated with another key, the key is processed using a further hashing calculation according to the rehashing rule. This produces another position to try, allowing the distinct key and its value to be placed or found without treating the two keys as identical.

An exam answer should make the sequence clear: calculate the initial hash, identify the collision if another key has the same hash, then apply rehashing to the key involved in the collision. The precise rehashing calculation must be stated if a question supplies one.

Common errors

• Saying that a collision happens when two values are the same. A collision happens when two key values compute the same hash.
• Confusing the key with the value. The key is input to the hash calculation; the value is the data mapped to the key.
• Assuming that different keys must always produce different hashes. The possibility of a collision is part of using a hash table.
• Giving a new table position without showing the hashing or rehashing calculation.
• Treating rehashing as changing the key. Rehashing applies another hashing calculation to deal with the collision; the key remains the identifier of the value.