Turn each key into a number (its hash), and use hash mod m to pick one of m buckets. A lookup only searches that one bucket, so finding a key takes about the same time however many keys are stored.
- Typical operation
- O(1)
- Space
- O(n)
Turn each key into a number (its hash), and use hash mod m to pick one of m buckets. A lookup only searches that one bucket, so finding a key takes about the same time however many keys are stored.