Quadratic Probing in Hashing

Introduction

• Quadratic probing is a collision resolution method in hashing.
• It is an alternative to other methods such as chaining and linear probing.
• This lecture uses the same example as the chaining and linear probing methods.

Hashing Example

• Keys: Various keys to be stored in a hash table.
• Hash Table Size: 10
• Hash Function: 2k + 3
• Method: Division method to store elements.
• Collision Resolution: Quadratic probing.

Quadratic Probing Method

• Insert key ( K_i ) at the first free location using the formula:
  • [ u + i^2 \mod M ]
• Range of i: 0 to m-1
• Linear Probing Comparison:
  • Linear probing uses ( u + i \mod M )
  • Linear probing can cause clustering issues.

Example Walkthrough

• Key 3:
  • Apply hash function: ( 2 \times 3 + 3 \mod 10 = 9 )
  • Place 3 at index 9.
• Key 2:
  • ( 2 \times 2 + 3 \mod 10 = 7 )
  • Place 2 at index 7.
• Key 9:
  • ( 2 \times 9 + 3 \mod 10 = 1 )
  • Place 9 at index 1.
• Key 6:
  • ( 2 \times 6 + 3 \mod 10 = 5 )
  • Place 6 at index 5.
• Key 11 (Collision):
  • ( 2 \times 11 + 3 \mod 10 = 5 )
  • Collision occurs at index 5.
  • Use quadratic probing to resolve:
    • Check subsequent quadratic places until a free slot is found.
    • Place 11 at the first free index found through probing.
• Additional Keys:
  • Similar process applied for other keys (13, 7, 12) using the quadratic formula.

Probing Analysis

• Probes: Refers to checking slots for availability.
• Count the number of probes needed for each key:
  • Example: Key 11 required two probes.
• Efficiency: Quadratic probing reduces number of probes in certain scenarios compared to linear probing.

Order of Elements

• Elements order after insertion:
  • [13, 9, -, 12, -, 6, 11, 2, 7, 3]
• Compared to linear probing, where the order differs.

Conclusion

• Quadratic probing is effective in resolving collisions by reducing clustering.
• Next topic: Double hashing technique.