Hashing

The essentials

Hashing lets us find an element in (ideally) a single step, no matter how large the collection. A hash function takes a key and calculates an index (position) in a hash table where the element is stored. To search, the same function is applied to the key and only that position is checked.

Key points

• A common hash function is the remainder method: h(key) = key % size of table. With a table of size 10, key 47 goes to position 47 % 10 = 7.
• Searching by hashing takes a constant number of steps when there are no collisions, independent of the number of elements; this is written as O(1).
• Collision: two different keys produce the same hash value. With size 10, keys 23 and 43 both give position 3.
• Collision resolution: the method of finding a place for the second and later keys that collide.
• Linear probing (open addressing): if the computed slot is full, try the next slot, and so on (wrapping round to the start). Inserting 23, 43 and 13 into a size-10 table places them at 3, 4 and 5.
• Chaining: each slot holds a list of all keys that hash to it.
• A good hash function is quick to compute and spreads keys evenly across the table, reducing collisions.
• In Python, dictionaries and sets are implemented using hashing, which is why looking up a key is fast.

Exam tips

• Compute hash values carefully and then apply the collision rule described in the question.
• A perfect hash function maps every key to a different slot, so there are no collisions.

Common mistakes

• Forgetting to wrap round to slot 0 after the last slot in linear probing.
• Assuming hashing needs sorted data; it does not.