29. Hashing and Collision Resolution

We learned that Hash Tables provide O(1) average time complexity. This efficiency depends entirely on handling collisions—situations where the hash function maps two different keys to the same array index.

Collision Resolution Strategy 1: Chaining

• Concept: Instead of storing a single item at an index, the index stores a reference to a linked list (or dynamic array).
• How it Works: When a collision occurs, the new key/value pair is simply added to the linked list at that index.
• Trade-off: Lookup time remains O(1) on average, but if too many collisions occur, the linked list gets long, degrading performance toward O(N) (linear search within the list).

Strategy 2: Open Addressing (Probing)

• Concept: If a collision occurs, search for the next available open slot in the main array.
  • Linear Probing: Check the next index (index + 1, index + 2, etc.).
  • Quadratic Probing: Use a quadratic step (index + 1, index + 4, index + 9, etc.).
• Trade-off: Requires careful handling of deletions, and can lead to 'clustering' if not implemented well.