[prev] [index] [next]

Hashing Summary

Collision resolution approaches:
  • chaining: easy to implement, allows α > 1
  • linear probing: fast if α << 1, complex deletion
  • double hashing: faster than linear probing, esp for α ≅ 1
Only chaining allows α > 1, but performance degrades once α > 1

Once M exceeds initial choice of N,

  • need to expand size of array (N)
  • problem: hash function relies on N,
    so changing array size potentially requires rebuiling whole table
  • dynamic hashing methods exist to avoid this