Practice question · Multiple choice
In a room of 23 people the chance two share a birthday is about 50%. Why does that matter for hash functions and IDs?
Hints
- You are not looking for a match with one specific person. How many pairs are there among 23 people?
- Ask how many items you can insert into a space of size N before a collision is likely.
Show the answer
C. Because collisions become likely near the square root of the space
Why
There are 253 pairs among 23 people, not 23 comparisons, and the same counting says collisions arrive near √N. A 64-bit random ID collides around four billion items, which is why UUIDs are 128 bits and why 'the space is huge' is not by itself an argument.
Practise Counting and Combinatorics
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.