1. Hash

• Hash table
  • Hash function - DISPERSE the keys !
    • Hash code (h1) : keys → integers
      • Ex) Memory address, Integer cast, Component sum, polynomial accumulation...
    • Compression function (h2) : integers → [0, N -1]
      • Ex) Division, MAD
    • Hash function h(x) = h2(h1(x)) → hash value
  • Array of size N
    • Item (k, o) will be stored at index i = h(k)

2. Operation

3. Collision Handling

Separate Chaining

• Additioinal memory required

Open addressing - Linear Probing

Linear Probe

• Place the colliding one in the next available table cell
• **Colliding items lump together → causing FUTURE COLLISIONS again
• DEFUNCT : A marker showing that it was occupied but now it's available

Search

• Start at cell h(k)
• Probe till you find the key / the available cell
• N cells have been probed → No such key

Put