Practice question · Multiple choice
A hash function maps a large key space into a small one, so collisions are guaranteed. Which mathematical fact makes that inevitable?
Hints
- Count the possible strings and the available buckets. Which is larger?
- Ask whether any function from a larger set to a smaller one could be injective.
Show the answer
C. The pigeonhole principle, more keys than buckets
Why
Infinitely many possible strings and finitely many buckets means no function can be injective, collisions are a theorem, not a defect. That is why every hash table ships with a resolution strategy, and why the design goal is spreading keys evenly rather than the impossible one of avoiding collisions.
Practise Functions
The app has 4 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Functions
- Each option lists a set of ordered pairs from {1, 2, 3} to {a, b}. Select every one that is a function on the…
- Order the steps of evaluating the composition h after g after f, applied to an input x.
- A function has an inverse exactly when it is bijective. Why do both injectivity and surjectivity turn out to…
- Sort each description by the property of a function it is describing.