---

Handling collision in hashing

---

• Collisions
  • When will a collision occur:

    Keys: k1 ≠ k2 Collision occurs when their hash indices are equal:             h(k1) = h(k2)

    Example:

    Keys 16 and 7 have collided....

  ---

  ---

• Handling collisions
  • Commonly used methods:

    Separate chaining Each bucket can store multiple entries (E.g., each bucket is a list) Colliding entries are stored as a chain (list) in the same bucket Open addressing Each bucket can store at most one entry A entry that hashes into an occupied bucket initiates a search procedure to find the next empty bucket