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
|