How it works
A hash function maps a key to a bucket. A good one spreads keys evenly, which is exactly the assumption behind constant average lookup.
State the even-distribution assumption whenever you quote constant-time behavior.
Common error
Quoting constant time as if unconditional. With every key colliding, lookup is linear.
Worked example
Java snippets run inside a main method. Add import java.util.*; when collection types are used.
Java
int capacity = 7;
System.out.println(Math.floorMod(17, capacity));
System.out.println(Math.floorMod(24, capacity));Output
3
3Different keys can map to the same bucket. Hashing supports efficient placement when distribution and load are suitable, but equality checks remain necessary to distinguish colliding keys.
Exercises
5.2.1 · Explain
Do equal hash values prove two keys are equal?
Show solution
No. Collisions are possible. A hash-based collection must use its equality rule as well as the hash.
5.2.2 · Explain
Why must a key equality rule and its hash calculation agree?
Show solution
Equal keys must produce compatible hashes so lookups search the correct location. Mutating a stored key in a way that changes those properties can break retrieval.