When O(1) hashing collapses to O(n)

Lesson notes

Key points

• The O(1) guarantee is only average case, assuming the hash function spreads keys uniformly across slots.
• If every key lands in the same slot, chaining builds one long list and each lookup becomes a linear scan.
• A classic exam mistake is hashing by first letter: names like Kwame, Kofi and Kojo all collide.
• Good hash functions mix every part of the key, and a prime table size helps spread patterned keys.

Definitions

Simple uniform hashing

Assumption that each key is equally likely to land in any of the m slots, independently.

Takeaway: Hashing is O(1) only on average; a bad hash function makes it O(n).

Uniform hashingWorst case O(n)Clustered keysGood hash design