Hashing

• Simple and powerful load balancing

• Constant time to find bucket for item

• Example map to n buckets. Pick a,b:

  y=ax+b (mod n)
  

• Intuition: hash maps each item to one random bucket

  • no bucket gets many items

Previous slide

Next slide

Back to first slide

View graphic version